Jethro's Braindump

Coding Interview Cheatsheet


Dutch Flag Partition

RED, WHITE, BLUE = range(3)

# Time: O(n)
# Space: O(1)
def dutch_flag_partition(pivot_index, A):
    pivot = A[pivot_index]
    # First pass: group elements smaller than pivot

    smaller = 0
    for i in range(len(A)):
        if A[i] < pivot:
            A[i], A[smaller] = A[smaller], A[i]
            smaller += 1

    # Second pass: group elements larger than pivot
    larger = len(A) - 1
    for i in range(len(A)):
        if A[i] < pivot:
        elif A[i] > pivot:
            A[i], A[larger] = A[larger], A[i]
            larger -= 1

Linked List

class ListNode(object):
    def __init__(self, data=0, next_node=None): = data = next_node
def search_list(L, key):
    while L and != key:
        L =
    return L
def insert_after(node, new_node): = = new_node
def delete_after(node):
    # Need to make sure there is something after to delete
    if =

Reverse Sublist

def reverse_sublist(L, start, finish):
    dummy_head = sublist_head = ListNode(0, L)
    for _ in range(1, start):
        sublist_head =

    sublist_iter =
    for _ in range(finish - start):
        temp =,, = (
  ,, temp


Test Cycle

def has_cycle(head):
    def cycle_len(end):
        start, step = end, 0
        while True:
            step += 1
            start =
            if start is end:
                return step

    fast = slow = head

    while fast and and
        slow, fast =,
        if slow is fast:
            it = head
            for _ in range(cycle_len(slow)):
                it =

            it2 = head

            while it is not it2:
                it =
                it2 =
            return it

    return None


stack = []

Building with Sunset View

def examine_buildings_with_sunset(it):
    BuildingWithHeight = collections.namedtuple("BuildingWithHeight", ("id", "height"))

    candidates = []

    for idx, building_height in enumerate(it):
        while candidates and building_height >= candidates[-1].height:
        candidates.append(BuildingWithHeight(idx, building_height))

    return [ for candidate in reversed(candidates)]


Queue supports 2 operations, enqueue and dequeue. Queues can be implemented with a linked list. Doubled ended queues support insertions and deletions from both ends (doubly-linked list).



Binary Trees


def traverse(tree):
    if tree:
        print(f"preorder {}")
        print(f"inorder {}")
        print(f"{postorder {}}")

Height Balanced

def is_balanced(tree):
    BalanceStatus = collections.namedtuple("BalanceStatus", ("balanced", "height"))

    def check_balanced(tree):
        if not tree:
            return BalanceStatus(True, -1) # Base case

        left = check_balanced(tree.left)
        if not left.balanced:
            return BalanceStatus(False, 0)

        right = check_balanced(tree.right)
        if not right.balanced:
            return BalanceStatus(False, 0)

        is_balanced = abs(left.height - right.height) <= 1
        height = max(left.height, right.height) + 1
        return BalanceStatus(is_balanced, height)

    return check_balanced(tree).balanced

Find Successor

Successor is leftmost element in node’s right subtree.

def successor(node):
    if node.right:
        node = node.right:
        while node.left:
            node = node.left
        return node

    while node.parent and node.parent.right is node:
        node = node.parent

    return node.parent


Python provides min-heap via heapq.

  • \(O(\log n)\) insertions
  • \(O(1)\) min element
  • \(O(\log n)\) deletion of min element
heapq.heapify(L)                # elements in L to heap in-place
heapq.nlargest(k, L)
heapq.nsmallest(k, L)           # k largest (smallest) elements in L
heapq.heappush(h, e)            # pushes new element onto heap
heapq.heappop(h)                # pops smallest element from heap
heapq.heappushpop(h, a)         # pushes a on heap and pops and returns smallest element
e = h[0]                        # return min element

Merge k sorted arrays

min_heap = []
sorted_array_iters = [iter(x) for x in sorted_arrays]

for i, it in enumerate(sorted_arrays_iters):
    first_element = next(it, None)
    if first_element is not None:
        heapq.heappush(min_heap, (first_element, i))

result = []

while min_heap:
    smallest, smallest_i = heapq.heappop(min_heap)
    smallest_iter = sorted_array_iters[smallest_i]
    next_element = next(smallest_iter, None)
    if next_element is not none:
        heapq.heappush(min_heap, (next_element, smallest_i))
return result


def binary_search(t, A):
    L, R = 0, len(A) - 1
    while L <= R:
        M = (L + R) // 2
        if A[M] < t:
            L = M + 1
        elif A[M] = t:
            return M
            R = M - 1
    return -1


class Student(object):
    def __init__(self, name, gpa): = name
        self.gpa = gpa

    def __lt__(self, other):
        return <

students_by_name = sorted(students)
students.sort(key = lambda: student: student.gpa) # in-place

Binary Search Trees

  • \(O(\log n)\) insertion
  • \(O(\log n)\) deletion
  • \(O(\log n)\) lookup
  • \(O(\log n)\) find


def dfs(node):
    seen = {}
    stack = [node]
    while stack:
        n = stack.pop()
        for x in n.neighbours:
            if x not in seen:

Icon by Laymik from The Noun Project. Website built with ♥ with Org-mode, Hugo, and Netlify.