Data structures
Tree
def preorder(tree):
if tree:
print(tree.getRootVal())
preorder(tree.getLeftChild())
preorder(tree.getRightChild())
def postorder(tree):
if tree != None:
postorder(tree.getLeftChild())
postorder(tree.getRightChild())
print(tree.getRootVal())
def inorder(tree):
if tree != None:
inorder(tree.getLeftChild())
print(tree.getRootVal())
inorder(tree.getRightChild())
Binary Search Tree (BST)
https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/
# Python program to demonstrate delete operation
# in binary search tree
# A Binary Tree Node
class Node:
# Constructor to create a new node
def __init__(self, key):
self.key = key
self.left = None
self.right = None
# A utility function to do inorder traversal of BST
def inorder(root):
if root is not None:
inorder(root.left)
print root.key,
inorder(root.right)
# A utility function to insert a new node with given key in BST
def insert( node, key):
# If the tree is empty, return a new node
if node is None:
return Node(key)
# Otherwise recur down the tree
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
# return the (unchanged) node pointer
return node
# Given a non-empty binary search tree, return the node
# with minum key value found in that tree. Note that the
# entire tree does not need to be searched
def minValueNode( node):
current = node
# loop down to find the leftmost leaf
while(current.left is not None):
current = current.left
return current
# Given a binary search tree and a key, this function
# delete the key and returns the new root
def deleteNode(root, key):
# Base Case
if root is None:
return root
# If the key to be deleted is smaller than the root's
# key then it lies in left subtree
if key < root.key:
root.left = deleteNode(root.left, key)
# If the kye to be delete is greater than the root's key
# then it lies in right subtree
elif(key > root.key):
root.right = deleteNode(root.right, key)
# If key is same as root's key, then this is the node
# to be deleted
else:
# Node with only one child or no child
if root.left is None :
temp = root.right
root = None
return temp
elif root.right is None :
temp = root.left
root = None
return temp
# Node with two children: Get the inorder successor
# (smallest in the right subtree)
temp = minValueNode(root.right)
# Copy the inorder successor's content to this node
root.key = temp.key
# Delete the inorder successor
root.right = deleteNode(root.right , temp.key)
return root
Graphs
https://www.python.org/doc/essays/graphs/
https://www.python-course.eu/graphs_python.php
https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
Depth First Search (DFS)
def dfs(graph, start):
visited, stack = set(), [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
dfs(graph, 'A') # {'E', 'D', 'F', 'A', 'C', 'B'}
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
dfs(graph, 'C') # {'E', 'D', 'F', 'A', 'C', 'B'}
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
stack.append((next, path + [next]))
list(dfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
def dfs_paths(graph, start, goal, path=None):
if path is None:
path = [start]
if start == goal:
yield path
for next in graph[start] - set(path):
yield from dfs_paths(graph, next, goal, path + [next])
list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
Breadth First Search (BFS)
def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited
bfs(graph, 'A') # {'B', 'C', 'A', 'F', 'D', 'E'}
def bfs_paths(graph, start, goal):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == goal:
yield path + [next]
else:
queue.append((next, path + [next]))
list(bfs_paths(graph, 'A', 'F')) # [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]
Shortest Path
def shortest_path(graph, start, goal):
try:
return next(bfs_paths(graph, start, goal))
except StopIteration:
return None
shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
Union Find (Disjoint set)
https://github.com/imressed/python-disjoint-set/blob/master/disjoint_set.py
class DisjointSet:
'''
Disjoint Set data structure (Union–Find), is a data structure that keeps track of a
set of elements partitioned into a number of disjoint (nonoverlapping) subsets.
Methods:
find: Determine which subset a particular element is in. Takes an element of any
subset as an argument and returns a subset that contains our element.
union: Join two subsets into a single subset. Takes two elements of any subsets
from disjoint_set and returns a disjoint_set with merged subsets.
get: returns current disjoint set.
'''
_disjoint_set = list()
def __init__(self, init_arr):
self._disjoint_set = []
if init_arr:
for item in list(set(init_arr)):
self._disjoint_set.append([item])
def _find_index(self, elem):
for item in self._disjoint_set:
if elem in item:
return self._disjoint_set.index(item)
return None
def find(self, elem):
for item in self._disjoint_set:
if elem in item:
return self._disjoint_set[self._disjoint_set.index(item)]
return None
def union(self,elem1, elem2):
index_elem1 = self._find_index(elem1)
index_elem2 = self._find_index(elem2)
if index_elem1 != index_elem2 and index_elem1 is not None and index_elem2 is not None:
self._disjoint_set[index_elem2] = self._disjoint_set[index_elem2]+self._disjoint_set[index_elem1]
del self._disjoint_set[index_elem1]
return self._disjoint_set
def get(self):
return self._disjoint_set
Min/Max heap (Priority Queue|Heap Queue)
http://interactivepython.org/courselib/static/pythonds/Trees/BinaryHeapImplementation.html
import heapq
heapq.heappush(h,7)
heapq.heappop(h) #returns 0
class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0
def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2
def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)
def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc
def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1
def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval
def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
Circular Queue
class CircularQueue:
#Constructor
def __init__(self):
self.queue = list()
self.head = 0
self.tail = 0
self.maxSize = 8
#Adding elements to the queue
def enqueue(self,data):
if self.size() == self.maxSize-1:
return ("Queue Full!")
self.queue.append(data)
self.tail = (self.tail + 1) % self.maxSize
return True
#Removing elements from the queue
def dequeue(self):
if self.size()==0:
return ("Queue Empty!")
data = self.queue[self.head]
self.head = (self.head + 1) % self.maxSize
return data
#Calculating the size of the queue
def size(self):
if self.tail>=self.head:
return (self.tail-self.head)
return (self.maxSize - (self.head-self.tail))
Dequeue (Double ended queue|Head tail linked list)
http://interactivepython.org/courselib/static/pythonds/BasicDS/ImplementingaDequeinPython.html
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
Queue
http://interactivepython.org/RkmcZ/courselib/static/pythonds/BasicDS/ImplementingaQueueinPython.html
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
Stack
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
Trie
http://interactivepython.org/runestone/static/pythonds/Trees/SearchTreeImplementation.html
https://www.geeksforgeeks.org/trie-insert-and-search/
Quick trie
https://github.com/kamyu104/LeetCode/blob/master/Python/word-squares.py
class TrieNode(object):
def __init__(self):
self.indices = []
self.children = [None] * 26
def insert(self, words, i):
cur = self
for c in words[i]:
if not cur.children[ord(c)-ord('a')]:
cur.children[ord(c)-ord('a')] = TrieNode()
cur = cur.children[ord(c)-ord('a')]
cur.indices.append(i)
Advanced trie
# Python program for insert and search
# operation in a Trie
class TrieNode:
# Trie node class
def __init__(self):
self.children = [None]*26
# isEndOfWord is True if node represent the end of the word
self.isEndOfWord = False
class Trie:
# Trie data structure class
def __init__(self):
self.root = self.getNode()
def getNode(self):
# Returns new trie node (initialized to NULLs)
return TrieNode()
def _charToIndex(self,ch):
# private helper function
# Converts key current character into index
# use only 'a' through 'z' and lower case
return ord(ch)-ord('a')
def insert(self,key):
# If not present, inserts key into trie
# If the key is prefix of trie node,
# just marks leaf node
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])
# if current character is not present
if not pCrawl.children[index]:
pCrawl.children[index] = self.getNode()
pCrawl = pCrawl.children[index]
# mark last node as leaf
pCrawl.isEndOfWord = True
def search(self, key):
# Search key in the trie
# Returns true if key presents
# in trie, else false
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])
if not pCrawl.children[index]:
return False
pCrawl = pCrawl.children[index]
return pCrawl != None and pCrawl.isEndOfWord
# driver function
def main():
# Input keys (use only 'a' through 'z' and lower case)
keys = ["the","a","there","anaswe","any",
"by","their"]
output = ["Not present in trie",
"Present in tire"]
# Trie object
t = Trie()
# Construct trie
for key in keys:
t.insert(key)
# Search for different keys
print("{} ---- {}".format("the",output[t.search("the")]))
print("{} ---- {}".format("these",output[t.search("these")]))
print("{} ---- {}".format("their",output[t.search("their")]))
print("{} ---- {}".format("thaw",output[t.search("thaw")]))
if __name__ == '__main__':
main()
Dynamic Programming (DP)
Dynamic Programming by Gayle Laakman
Cheat sheet
Problems
Fibonacci
Leetcode solutions: https://github.com/kamyu104/LeetCode
def F(n):
if n == 0: return 0
elif n == 1: return 1
else: return F(n-1)+F(n-2)
Skyline Problem
https://gist.github.com/jbochi/3287392
buildings = [
[1, 11, 5],
[2, 6, 7],
[3, 13, 9],
[12, 7, 16],
[14, 3, 25],
[19, 18, 22],
[23, 13, 29],
[24, 4, 28],
]
LEFT = 0
HEIGHT = 1
RIGHT = 2
def skyline(buildings):
left = min(b[LEFT] for b in buildings)
right = max(b[RIGHT] for b in buildings)
last_height = None
output = []
for i in range(left, right + 1):
heights = [b[HEIGHT] for b in buildings if b[LEFT] <= i < b[RIGHT]]
height = max(heights) if heights else 0
if height != last_height:
output += [i, height]
last_height = height
return output
if __name__ == '__main__':
assert(skyline(buildings) == [1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0])
Cycle detection in directed graph
https://www.geeksforgeeks.org/detect-cycle-in-a-graph/
from collections import defaultdict
class Graph():
def __init__(self,vertices):
self.graph = defaultdict(list)
self.V = vertices
def addEdge(self,u,v):
self.graph[u].append(v)
def isCyclicUtil(self, v, visited, recStack):
# Mark current node as visited and
# adds to recursion stack
visited[v] = True
recStack[v] = True
# Recur for all neighbours
# if any neighbour is visited and in
# recStack then graph is cyclic
for neighbour in self.graph[v]:
if visited[neighbour] == False:
if self.isCyclicUtil(neighbour, visited, recStack) == True:
return True
elif recStack[neighbour] == True:
return True
# The node needs to be poped from
# recursion stack before function ends
recStack[v] = False
return False
# Returns true if graph is cyclic else false
def isCyclic(self):
visited = [False] * self.V
recStack = [False] * self.V
for node in range(self.V):
if visited[node] == False:
if self.isCyclicUtil(node,visited,recStack) == True:
return True
return False
Cycle detection in undirected graph
https://www.geeksforgeeks.org/detect-cycle-undirected-graph/
from collections import defaultdict
#This class represents a undirected graph using adjacency list representation
class Graph:
def __init__(self,vertices):
self.V= vertices #No. of vertices
self.graph = defaultdict(list) # default dictionary to store graph
# function to add an edge to graph
def addEdge(self,v,w):
self.graph[v].append(w) #Add w to v_s list
self.graph[w].append(v) #Add v to w_s list
# A recursive function that uses visited[] and parent to detect
# cycle in subgraph reachable from vertex v.
def isCyclicUtil(self,v,visited,parent):
#Mark the current node as visited
visited[v]= True
#Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
# If the node is not visited then recurse on it
if visited[i]==False :
if(self.isCyclicUtil(i,visited,v)):
return True
# If an adjacent vertex is visited and not parent of current vertex,
# then there is a cycle
elif parent!=i:
return True
return False
#Returns true if the graph contains a cycle, else false.
def isCyclic(self):
# Mark all the vertices as not visited
visited =[False]*(self.V)
# Call the recursive helper function to detect cycle in different
#DFS trees
for i in range(self.V):
if visited[i] ==False: #Don't recur for u if it is already visited
if(self.isCyclicUtil(i,visited,-1))== True:
return True
return False