# 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

``````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:
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()
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']]
``````

``````def bfs(graph, start):
visited, queue = set(), [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
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.tail = 0
self.maxSize = 8

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!")
return data

#Calculating the size of the queue
def size(self):
``````

``````class Deque:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

self.items.append(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

##### 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)
``````
``````# 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

self.graph[u].append(v)

def isCyclicUtil(self, v, visited, recStack):
# Mark current node as visited and
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
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
``````

Devamını oku