Useful code snippets

Code Snippets

Placeholder file to provide title for Gist.

basic-hash-table.py

def MyHashTable(object):
    def __init__(self, size):
        self.table = [None] * size
        self.size = size

    def _find_index(self, value):
        hash = value % self.size
        counter = 1

        while self.table[hash] is not None:
            if self.table[hash] == value:
                hash = (hash + counter**2) % self.size  # Quadratic probing
            counter += 1

        return hash

    def add(self, value):
        self.table[self._find_index(value)] = value

    def remove(self, value):
        self.table[self._find_index(value)] = None

    def contains(self, value):
        return self.table[self._find_index(value)] is not None

fast_exponentiation.py

from time import time
from functools import partial

def fast_exp(a, b):
    if b < 0:
        return 1 / fast_exp(a, -b)

    ans = 1
    cumulative = a
    counter = 1

    while counter <= b:
        if b & counter > 0:
            ans *= cumulative
        
        cumulative *= cumulative
        counter <<= 1
    
    return ans
    
def naive(a, b):
    total = a
    for i in range(b-1):
        total *= a
    return total
    
def timer(function):
    start = time()
    function()
    return time() - start

a = 999
b = 999
naive = partial(naive, a, b)
ours = partial(fast_exp, a, b)
theirs = partial(pow, a, b)
print(timer(naive))
print(timer(ours))
print(timer(theirs))

graph-search.py

def dfs(graph, start):
    stack = [(None, start)]
    visited = {start}

    while len(stack) > 0:
        parent, current = stack.pop()
        yield parent, current
        new_children = graph[current] - visited
        stack += ((current, child) for child in new_children)
        visited |= new_children


def bfs(graph, start):
    queue = [(None, start)]
    visited = {start}

    while len(queue) > 0:
        parent, current = queue.pop(0)
        yield parent, current
        new_children = graph[current] - visited
        queue += ((current, child) for child in new_children)
        visited |= new_children


def shortest_path(graph, start, end):
    paths = {None: []}  # {destination: [path]}

    for parent, child in bfs(graph, start):
        paths[child] = paths[parent] + [child]

        if child == end:
            return paths[child]

    return None # or raise appropriate exception


graph = {'A': {'B', 'C',’E'},
         'B': {'A','C', ‘D'},
         'C': {‘D'},
         'D': {‘C'},
         'E': {'F', ‘D'},
         'F': {‘C'}}

knapsack.py

from memoize import memoize

@memoize
def knapsack(items, max_weight):
    if len(items) == 0 or max_weight <= 0:
        return 0

    first = items[0]
    rest = items[1:]

    # Don’t include the first item
    value_without_first = knapsack(rest, max_weight)

    # Include the first item
    if first.weight <= max_weight:
        value_with_first = knapsack(rest, max_weight - first.weight) + first.value
        return max(value_with_first, value_without_first)
    else:
        return value_without_first

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

items = (Item(12, 4), Item(2, 2), Item(1, 2), Item(1, 1), Item(4, 10)) # Solution: Value=15
max_weight = 15
print(knapsack(items, max_weight))

memoize.py

class memoize(dict):
    def __init__(self, func):
        self.func = func

    def __call__(self, *args):
        return self[args]

    def __missing__(self, args):
        result = self[args] = self.func(*args)
        return result

quicksort.py

def qs(items):
	pivot = items[0]

	smaller = []
	equal = []
	larger = []

	for item in items:
		if item < pivot:
			smaller.append(item)
		elif item > pivot:
			larger.append(item)
		else:  # item == pivot
			equal.append(item)
	
	return qs(smaller) + equal + qs(larger)
	
	
def qs_in_place(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    
    if begin >= end:
        return
    
    pivot = partition(array, begin, end)
    qs_in_place(array, begin, pivot-1)
    qs_in_place(array, pivot+1, end)
    
    
def partition(array, start, end):
    pivot = start
    
    for i in range(start+1, end+1):
        if array[i] <= array[start]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    
    array[pivot], array[start] = array[start], array[pivot]
    
    return pivot

tree-traversals.py

def preorder(root):
    if root is not None:
        print(root.data)
        preorder(root.left)
        preorder(root.right)

def inorder(root):
    if root is not None:
        inorder(root.left)
        print(root.data)
        inorder(root.right)

def postorder(root):
    if root is not None:
        postorder(left)
        postorder(right)
        print(root.data)