- Signal: You need a dynamic, ordered set with O(log n) search/insert/delete and want to avoid balanced-tree rotation logic -- especially under concurrent access, where 'only touch local nodes' is a real design requirement.
- Approach: Stack sparser and sparser sorted linked lists on top of a full base list; promote each new node to additional levels via independent coin flips (p=0.5 per level). Search from the top level, walking right until the next node would overshoot, then drop down a level -- repeat to the bottom.
- Watch out for: Forgetting to splice a new/removed node into every level it appears on, not just the base list -- this breaks the 'each level is independently sorted' invariant that search correctness depends on.
- Complexity: Expected O(log n) search, insert, and delete; O(n) expected space (each element promotes to ~2 levels on average at p=0.5).
def search(self, target):
node = self.head
for i in range(self.level, -1, -1):
while node.forward[i] and node.forward[i].val < target:
node = node.forward[i]
node = node.forward[0]
return node is not None and node.val == target
- Signal: The problem interleaves point updates to an array with repeated range-aggregate queries (sum/min/max) — or, while scanning, asks 'how many previously-seen values are smaller/larger/within a range,' which is a coordinate-compression + Fenwick tree tell.
- Approach: Use a Fenwick tree (BIT) for sum/XOR-style aggregates — index by `i & -i` (lowest set bit) to update/query in O(log n); use a segment tree instead for min/max/gcd or when you need range updates. Coordinate-compress values to dense ranks first whenever you need to index by value instead of array position.
- Watch out for: Off-by-one between 0-indexed input and the Fenwick tree's required 1-indexing — index 0 is deliberately unused because `0 & -0 == 0` would infinite-loop the traversal.
- Complexity: O(log n) per update and per query, O(n log n) to build from scratch (or O(n) with the linear-time build trick); O(n) space.
class FenwickTree:
def __init__(self, n):
self.tree = [0] * (n + 1) # 1-indexed; tree[0] unused
def update(self, i, delta):
while i < len(self.tree):
self.tree[i] += delta
i += i & (-i)
def prefix_sum(self, i):
total = 0
while i > 0:
total += self.tree[i]
i -= i & (-i)
return total
- Signal: You're parsing a nested/recursive grammar (arithmetic expressions, parentheses, a mini-language) rather than searching a fixed combinatorial structure, or a backtracking search space is so large that even correct pruning can't make it finish in time.
- Approach: Parsing: one function per precedence level, lower precedence in the outer function, recurse back to the top-level function on '('. Regex/wildcard matching: backtrack on '*' by trying zero-occurrences and one-more-occurrence, then memoize on (text index, pattern index) once you notice repeated subproblems. Intractable search: switch from exhaustive backtracking to beam search -- expand every current candidate, score, keep only the top-k, discard the rest permanently.
- Watch out for: Shipping a backtracking regex matcher against untrusted input without a step budget or automaton-based engine -- nested/adjacent quantifiers can trigger exponential-time catastrophic backtracking (ReDoS), a real, named production vulnerability class.
- Complexity: Recursive descent parsing O(n) time; naive backtracking regex match O(2^n) worst case, O(n*m) once memoized; beam search O(depth * k * branching factor) time, O(k) space.
def is_match(text, pattern):
if not pattern:
return not text
first_matches = bool(text) and pattern[0] in (text[0], ".")
if len(pattern) >= 2 and pattern[1] == "*":
return is_match(text, pattern[2:]) or (
first_matches and is_match(text[1:], pattern)
)
return first_matches and is_match(text[1:], pattern[1:])
- Signal: You need to connect every vertex as cheaply as possible in total (not point-to-point shortest paths) — 'wire up all the nodes for minimum total cost'.
- Approach: Kruskal's: sort all edges ascending, accept an edge with Union-Find if and only if its endpoints aren't already connected. Prim's: grow one tree from a min-heap frontier, always pulling in the cheapest edge crossing into an unvisited vertex — same skeleton as Dijkstra, but the heap key is just the single edge weight, not cumulative distance from a source.
- Watch out for: Confusing MST with shortest path: a vertex can be cheap to attach to the tree via one light edge while still being many hops and a large cumulative distance from an arbitrary source — MST minimizes total connection cost, not point-to-point distance.
- Complexity: Kruskal's O(E log E) (sort-dominated); Prim's O(E log V) with a binary heap.
def kruskal_mst(n, edges):
# edges = list of (weight, u, v)
edges.sort()
uf = UnionFind(n)
total_weight = 0
edges_used = 0
for weight, u, v in edges:
if uf.union(u, v):
total_weight += weight
edges_used += 1
return total_weight if edges_used == n - 1 else -1
- Signal: You're optimizing over contiguous ranges and the natural recursion is "pick a split point, solve both halves, combine" — or, when left-to-right processing creates sub-ranges that still interact, reframe as "decide what happens last in this range."
- Approach: Define dp[i][j] over the range [i, j], try every split point k, and iterate by increasing interval LENGTH first (then start index), since dp[i][j] depends on shorter sub-intervals with no fixed relationship to smaller i or j.
- Watch out for: Filling the table row-major/column-major like grid DP — dp[i][j]'s dependencies are shorter intervals, not cells strictly above or to the left, so you'll read uncomputed cells.
- Complexity: O(n²) states × O(n) split points per state = O(n³) time, O(n²) space (Knuth's optimization can bring specific recurrences down to O(n²)).
dp = [[0] * n for _ in range(n)]
# base case: dp[i][i] for length-1 intervals
for length in range(2, n + 1): # outer: interval length
for i in range(0, n - length + 1): # inner: start index
j = i + length - 1
dp[i][j] = float("inf")
for k in range(i, j): # split point
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost(i, k, j))
- Signal: You're repeatedly combining the two 'smallest' remaining items (by frequency, weight, or cost) and paying a cost proportional to what you combine — or you're asked to justify why a cache eviction policy is or isn't optimal.
- Approach: For Huffman-shaped problems: push every item into a min-heap, then repeatedly pop the two smallest, merge them (sum the weight, cost += sum), and push the merged item back until one remains. For caching questions: name Bélády's MIN (evict what's needed furthest in the future) as the theoretical optimum, then explain that it's unimplementable online because it needs the future — which is why LRU/LFU/ARC exist as heuristics instead.
- Watch out for: Re-sorting from scratch after every merge instead of using a heap (O(n^2 log n) instead of O(n log n)) — or claiming LRU is 'the optimal caching algorithm' rather than a heuristic approximation of Bélády's MIN.
- Complexity: O(n log n) time, O(n) space for Huffman-style heap merging.
import heapq
def min_merge_cost(weights):
heapq.heapify(weights)
total = 0
while len(weights) > 1:
a, b = heapq.heappop(weights), heapq.heappop(weights)
total += a + b
heapq.heappush(weights, a + b)
return total
- Signal: You're asked to find the two nearest points among a set (collision/proximity detection), or the minimal boundary/polygon enclosing a set of points -- and n is large enough that the O(n^2) brute-force pairwise check is explicitly called out as too slow.
- Approach: Closest pair: sort by x, split in half, recurse on each half, then only check cross-boundary pairs within a y-sorted strip of width 2d (each point needs at most ~6-7 comparisons there). Convex hull: sort points lexicographically, then build the lower and upper hull independently with a stack, popping any point that makes a non-left turn (cross product <= 0) with the two points before it.
- Watch out for: Closest pair: comparing every point in the left half against every point in the right half instead of restricting to the narrow y-sorted strip -- this silently degrades back to O(n^2). Convex hull: using the wrong cross-product sign convention (<= 0 vs < 0) for whether collinear boundary points should be included.
- Complexity: O(n log n) time, O(n) space for both algorithms (dominated by the initial sort).
def cross(o, a, b):
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
def half_hull(pts):
hull = []
for p in pts:
while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
return hull
- Signal: You need substring/pattern search with a guaranteed O(n) worst case (not just average case), or you need prefix-match-length information at every position — periodicity, "is this string a rotation of that one", or "does a length-k window repeat".
- Approach: KMP: precompute the LPS (longest proper prefix-that's-also-a-suffix) array so a mismatch falls the pattern pointer back instead of ever moving the text pointer backward, giving O(n+m) worst-case; Rabin-Karp: roll a hash across every window and compare hashes (always verifying a hit with a direct comparison) for O(n+m) average case, which shines for multi-pattern search; Z-function: generalizes the LPS idea to "longest prefix of the whole string matching at position i", for every i.
- Watch out for: Skipping the direct-comparison verification after a Rabin-Karp hash match — a collision without verification silently produces wrong answers on exactly the inputs that matter.
- Complexity: KMP / Z-function: O(n+m) time worst-case, O(m) or O(n) space. Rabin-Karp: O(n+m) time average case (O(n·m) worst case), O(1) space beyond the rolling hash.
def build_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0 # length of current matched prefix/suffix
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1] # reuse, don't advance i
else:
lps[i] = 0
i += 1
return lps
- Signal: An interviewer explicitly asks for a guaranteed-linear-time palindromic-substring algorithm instead of the O(n²) expand-around-center default.
- Approach: Interleave the string with '#' separators so every palindrome becomes odd-length, then for each position reuse the mirror position's already-verified radius (capped at the current right boundary) before attempting to expand further — never re-examine a character that symmetry already told you about.
- Watch out for: Reaching for Manacher's by default instead of leading with expand-around-center — given the difficulty-to-frequency ratio, that instinct reads as over-engineering far more often than it reads as impressive.
- Complexity: O(n) time, O(n) space (the transformed string and the radius array).
def manacher(s):
t = '#' + '#'.join(s) + '#'
n = len(t)
radius = [0] * n
center = right = 0
for i in range(n):
if i < right:
mirror = 2 * center - i
radius[i] = min(right - i, radius[mirror])
while (i - radius[i] - 1 >= 0 and i + radius[i] + 1 < n
and t[i - radius[i] - 1] == t[i + radius[i] + 1]):
radius[i] += 1
if i + radius[i] > right:
center, right = i, i + radius[i]
return radius, t