Cheatography

# Algos Cheat Sheet by dkarp

List of common algorithms in python

### Binary search - on sorted list - LogN

 ``````def bsearch(arr, target):     left, right = 0, len(arr) - 1     while left <= right:         mid = (left + right) // 2         val = arr[mid]         if val == target:             return mid         elif val > target:             right = mid - 1         else:             left = mid + 1     return -1``````

### Heap - LogN

 ``````import heapq def heap_min(arr):     heapq.heapify(arr)     return arr[0] def heap_max(arr):     heaparr = []     for val in arr:         heapq.heappush(heaparr, -1 * val)     return -1 * heaparr[0]``````

### DFS - preorder - N

 ``````def dfs(root, target):     def search(node):         if not node:             return         if node.val == target:             return node         left = search(node.left)         if left:             return left         right = search(node.right)         if right:             return right     return search(root)``````

### Collec­tions

 defaul­tdict defaul­tdi­ct(­def­aul­t_f­act­ory­=None) namedtuple namedt­upl­e('­Point', ['x', 'y']) deque deque(­[it­era­ble[, maxlen]]) append(x) append­left(x) pop() popleft() Counter Counte­r([­ite­rab­le-­or-­map­ping]) most_c­omm­on(n) subtra­ct(­[it­era­ble­-or­-ma­pping])

### BFS - N

 ``````def bfs(root, target):     queue = [root]     while queue:         node = queue.pop()         if not node:             continue         if node.val == target:             return node         queue.append(node.left)         queue.append(node.right)     return None``````

### Python Slices

 Slice a[star­t:s­top­:step] Elements after X a[x:] First X elements a[:x] Last X elements a[-x] Elements from X to Y not inclusive of Y a[x:y] Reverse List a[::-1]