Show Menu
Cheatography

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]
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          EECS 203 Final Exam Cheat Sheet Cheat Sheet