Data structures & algorithms

Still asking algorithm questions:
  large technology companies
  AI infrastructure and platform roles
  established enterprises hiring AI engineers

Often not:
  AI-native product companies
  forward deployed and applied roles
  small teams hiring for shipping speed

Phrase in the question                          Reach for
"how many", "count", "duplicate", "anagram"     hash map
"pair that sums", "sorted array", "palindrome"  two pointers
"substring", "subarray", "window", "longest"    sliding window
"sorted", "minimum value that works", "k-th"    binary search
"next greater", "previous smaller", "nesting"   stack
"top k", "k largest", "stream"                  heap

# Two sum: for each number, has its complement already been seen?
def two_sum(nums, target):
    seen = {}                       # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:      # check first
            return [seen[target - n], i]
        seen[n] = i                 # then insert
    return []

# O(n) time, O(n) space. The brute force is two nested loops, O(n^2).

from collections import Counter, defaultdict

Counter(words).most_common(3)          # [('the', 12), ('a', 9), ('of', 7)]

# Group anagrams: the sorted letters are the identity of the group.
groups = defaultdict(list)
for word in words:
    groups["".join(sorted(word))].append(word)
list(groups.values())                  # [['eat','tea','ate'], ['tan','nat']]

def two_sum_sorted(nums, target):
    """The sorted version. No extra memory, unlike the hash map above."""
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1               # only the left end can raise the sum
        else:
            right -= 1              # only the right end can lower it
    return []

# O(n) time, O(1) space. This is the template; most variants change the
# comparison, not the shape.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:            # identity, not equality
            return True
    return False

def longest_unique(s):
    """Longest substring with no repeated character."""
    last_seen = {}
    start = best = 0
    for i, ch in enumerate(s):
        # If we have seen it inside the current window, jump past it.
        if ch in last_seen and last_seen[ch] >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        best = max(best, i - start + 1)
    return best

longest_unique("abcabcbb")          # 3, "abc"

def min_window_sum(nums, target):
    """Shortest subarray summing to at least target. The while, not an if."""
    start = total = 0
    best = float("inf")
    for end, n in enumerate(nums):
        total += n
        while total >= target:          # shrink while valid, not once
            best = min(best, end - start + 1)
            total -= nums[start]
            start += 1
    return 0 if best == float("inf") else best

def lower_bound(nums, target):
    """First index whose value is >= target. Returns len(nums) if none is."""
    lo, hi = 0, len(nums)            # hi is exclusive
    while lo < hi:                   # ends when the range is empty
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1             # mid is ruled out
        else:
            hi = mid                 # mid might be the answer, so keep it
    return lo

def min_capacity(weights, days):
    """Smallest ship capacity that moves all packages within days trips."""
    def fits(capacity):
        used, load = 1, 0
        for w in weights:
            if load + w > capacity:
                used, load = used + 1, 0
            load += w
        return used <= days

    lo, hi = max(weights), sum(weights)      # must fit the largest; one trip
    while lo < hi:
        mid = (lo + hi) // 2
        if fits(mid):
            hi = mid                          # this works, try smaller
        else:
            lo = mid + 1
    return lo

def next_greater(nums):
    """For each element, the next element to its right that is larger."""
    answer = [-1] * len(nums)
    stack = []                       # indices, values decreasing
    for i, n in enumerate(nums):
        # Anything smaller than n has just found its answer.
        while stack and nums[stack[-1]] < n:
            answer[stack.pop()] = n
        stack.append(i)
    return answer

next_greater([2, 1, 2, 4, 3])        # [4, 2, 4, -1, -1]

Pattern          Time      Space     Worth drilling
hash map         O(n)      O(n)      two sum, group anagrams, top-k frequent
two pointers     O(n)      O(1)      sorted pair, palindrome, remove duplicates
fast and slow    O(n)      O(1)      cycle detection, middle node, n-th from end
sliding window   O(n)      O(k)      longest unique, min window, max sum of size k
binary search    O(log n)  O(1)      lower bound, rotated array, on the answer
monotonic stack  O(n)      O(n)      next greater, daily temperatures, valid parens

def depth(node):
    """Depth-first. The recursion is the stack."""
    if node is None:
        return 0
    return 1 + max(depth(node.left), depth(node.right))

from collections import deque

def levels(root):
    """Breadth-first, one list per level. The len(queue) snapshot is the trick:
    it fixes how many nodes belong to this level before any are added."""
    if root is None:
        return []
    out, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):        # exactly this level
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        out.append(level)
    return out

def inorder(node, out=None):
    """Left, self, right. On a BST this emits the values in sorted order."""
    out = [] if out is None else out
    if node:
        inorder(node.left, out)
        out.append(node.val)
        inorder(node.right, out)
    return out

def is_bst(node, low=float("-inf"), high=float("inf")):
    """Every node must fit a range, not merely beat its parent."""
    if node is None:
        return True
    if not low < node.val < high:
        return False
    return (is_bst(node.left, low, node.val)
            and is_bst(node.right, node.val, high))

from collections import deque

def shortest_path(grid, start, goal):
    """Fewest steps through a grid of open cells. BFS, because every step
    costs the same. Dijkstra is for when they do not."""
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, 0)])
    seen = {start}                          # mark on push, not on pop
    while queue:
        (r, c), dist = queue.popleft()
        if (r, c) == goal:
            return dist
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and grid[nr][nc] != "#" and (nr, nc) not in seen):
                seen.add((nr, nc))
                queue.append(((nr, nc), dist + 1))
    return -1

def topo_sort(nodes, edges):
    """edges are (before, after) pairs. Returns [] if there is a cycle."""
    incoming = {n: 0 for n in nodes}
    out = {n: [] for n in nodes}
    for before, after in edges:
        out[before].append(after)
        incoming[after] += 1

    ready = deque(n for n in nodes if incoming[n] == 0)
    order = []
    while ready:
        n = ready.popleft()
        order.append(n)
        for nxt in out[n]:
            incoming[nxt] -= 1
            if incoming[nxt] == 0:
                ready.append(nxt)
    return order if len(order) == len(nodes) else []

topo_sort("abcd", [("a", "b"), ("a", "c"), ("b", "d"), ("c", "d")])
# ['a', 'b', 'c', 'd']

import heapq

def top_k(nums, k):
    """Python's heapq is a min-heap, which is what you want here: the
    smallest of the current best k sits at the top, ready to be evicted."""
    heap = []
    for n in nums:
        if len(heap) < k:
            heapq.heappush(heap, n)
        elif n > heap[0]:
            heapq.heapreplace(heap, n)      # push and pop in one operation
    return sorted(heap, reverse=True)

top_k([5, 1, 9, 3, 7, 8], 3)                # [9, 8, 7]

# heapq.nlargest(k, nums) does the same thing and is the right answer in
# production. Interviewers usually want the loop.

from collections import Counter

def top_k_stream(stream, k):
    """Exact top-k by frequency, holding k items rather than the stream."""
    counts = Counter()
    heap = []                       # min-heap of (count, item), size <= k
    in_heap = set()

    for item in stream:
        counts[item] += 1
        if item in in_heap:
            # Rebuild lazily: its count moved, so the heap order is stale.
            heap = [(counts[i], i) for _, i in heap]
            heapq.heapify(heap)
        elif len(heap) < k:
            heapq.heappush(heap, (counts[item], item))
            in_heap.add(item)
        elif counts[item] > heap[0][0]:
            _, evicted = heapq.heapreplace(heap, (counts[item], item))
            in_heap.discard(evicted)
            in_heap.add(item)

    return sorted(heap, reverse=True)

def merge(intervals):
    """Overlapping ranges collapsed into one. O(n log n), the sort dominates."""
    if not intervals:
        return []
    intervals = sorted(intervals)           # by start
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:          # touches the one being built
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

merge([(1, 3), (2, 6), (8, 10), (15, 18)])  # [[1, 6], [8, 10], [15, 18]]

def max_rooms(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))
    # An end at time t is processed before a start at time t: a room frees up
    # exactly as the next meeting begins. -1 sorts before 1, which does it.
    events.sort()
    current = best = 0
    for _, delta in events:
        current += delta
        best = max(best, current)
    return best

max_rooms([(0, 30), (5, 10), (15, 20)])      # 2

def permutations(items):
    result, current, used = [], [], [False] * len(items)

    def backtrack():
        if len(current) == len(items):
            result.append(current[:])       # copy, or every entry aliases
            return
        for i, item in enumerate(items):
            if used[i]:
                continue
            used[i] = True                  # choose
            current.append(item)
            backtrack()                     # explore
            current.pop()                   # undo
            used[i] = False                 # undo
        return

    backtrack()
    return result

permutations([1, 2, 3])   # [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

def climb_stairs(n):
    """dp[i] = the number of distinct ways to reach step i.
    You arrive from one step below or two, so the ways add."""
    if n <= 2:
        return n
    a, b = 1, 2                              # ways to reach steps 1 and 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b

def coin_change(coins, amount):
    """dp[i] = fewest coins summing to exactly i, or infinity if impossible."""
    dp = [0] + [float("inf")] * amount
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return -1 if dp[amount] == float("inf") else dp[amount]

coin_change([1, 5, 6, 9], 11)                # 2, using 5 + 6

Worth drilling                        Rarely worth it
tree traversal, both kinds            red-black and AVL rotations
BFS on a grid                         Dijkstra, unless the job is routing
topological sort                      minimum spanning trees
heap for top-k                        Fibonacci heaps
interval merge and room counting      segment trees, Fenwick trees
backtracking skeleton                 bitmask dynamic programming
one-dimensional dynamic programming   two-dimensional, except edit distance

00:00  INTERVIEWER  Given a list of integers and a target, return the
                    indices of the two numbers that add to the target.

00:20  YOU   So: one list, one target, and I return two positions —
             not the values themselves. Is there always exactly one
             answer, or do I need to handle none and handle several?
             [asks before assuming — first thing on the rubric]

00:35  INT   Assume exactly one.

00:40  YOU   And how big does the list get? Are the numbers bounded,
             can they be negative, can the same element be used twice?

00:55  INT   Up to a million. Negatives are fine. Each element once.

01:05  YOU   Then a million rules out anything quadratic — that's 10^12
             operations. Let me still say the brute force so we agree
             on correctness: two nested loops, check every pair, O(n²)
             time and O(1) space. It's right, it's just too slow here.
             [brute force stated as a baseline, not offered as the answer]

01:30  INT   Agreed. What's better?

01:35  YOU   The waste is that for each element I rescan the whole list
             looking for target minus that element. That's a lookup, so
             it should be a hash map. One pass: for each number, check
             whether its complement has already been seen; if so I have
             my pair, and if not I record where this number is. O(n)
             time, O(n) space — I'm trading memory for the rescan.

02:10  INT   Go ahead.

02:15  YOU   [writes, narrating] I'll keep a dict from value to index.
             Checking the complement before inserting the current value
             is what stops it pairing an element with itself...

def two_sum(nums, target):
    seen = {}                            # value -> index
    for i, n in enumerate(nums):
        if target - n in seen:           # check BEFORE inserting
            return [seen[target - n], i]
        seen[n] = i
    return []

04:30  YOU   Let me run it. nums = [2, 7, 11, 15], target = 9.
             i=0, n=2: is 7 in seen? No, seen is empty. Store 2 -> 0.
             i=1, n=7: is 2 in seen? Yes, at 0. Return [0, 1]. Correct.

             Edge cases: [3, 3] with target 6 — i=0 stores 3 -> 0,
             i=1 finds 3 in seen and returns [0, 1], so duplicates work
             because I check before I insert. Empty list returns [].
             Negatives are fine, the arithmetic doesn't care.
             [tests unprompted — the candidate most interviewers remember]

05:10  INT   Good. Now suppose the list doesn't fit in memory.

05:15  YOU   Then I can't hold the map...

Question                          What it changes
How large is the input?           whether O(n log n) is acceptable at all
Sorted already?                   unlocks two pointers or binary search
Duplicates allowed?               set vs counter; changes the answer's shape
Negatives? zero? empty?           breaks prefix-sum and sliding-window tricks
One answer or all of them?        return-early vs collect
Can I mutate the input?           in-place saves the O(n) space
Streaming or in memory?           heap and sketches instead of a full scan
What should invalid input do?     raise, return empty, or clamp

"Brute force is O(n²) time, O(1) space. The repeated work is
scanning for the complement, so a hash map removes it: O(n)
time, O(n) space. I'll do that unless memory is constrained."

"I'm stuck. Brute force is O(n²) and I need better. Sorting
doesn't help because I need the original indices. I think I want
something that remembers what I've seen, so let me try a hash map
keyed on the value."

What happens                        What it reads as     Instead
Silent thinking for 3+ minutes      cannot communicate   narrate the dead ends
Coding before agreeing an approach  does not plan        two minutes of talking
Recognising and reciting a memo     memorised, untested  derive it out loud
Arguing when given a hint           hard to work with    take it, say thanks
Waving at complexity ("fast")       cannot analyse       give both, every time
Saying "done" without testing       ships untested code  walk an example first
Freezing after a requirement change rigid                restate what changed
Hiding a bug you have noticed       not trustworthy      name it, then fix it