Toolbox: pattern recognition in code
Read four code sketches, recognise which technique each implements (or should), and pick the right data structure or the highest-leverage fix.
In an interview or a code review you rarely get a labelled problem — you get a snippet and a constraint. The skill is reading the loop and naming the technique it implements, or spotting that the chosen structure is the wrong one. Read each sketch, then answer.
Practise the recognition half of the toolbox: given code, identify the pattern, judge whether the data structure fits the dominant operation, and choose the change that actually moves the complexity.
Snippet 1 — the nested loop on sorted data
def has_pair_with_sum(a, target): # a is sorted ascending
n = len(a)
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return True
return FalseThe input is sorted but this is O(n^2). What pattern does the sorted input call for, and what is the resulting complexity?
Snippet 2 — the recursion that recomputes
def ways(n, coins):
if n == 0: return 1
if n < 0 or not coins: return 0
# use coins[0] again, or drop it
return ways(n - coins[0], coins) + ways(n, coins[1:])This is correct but exponential on large n. What is the precise diagnosis and the standard fix?
Snippet 3 — the running k-th element
import heapq
def stream_kth_largest(stream, k):
h = [] # what kind of heap?
for x in stream:
heapq.heappush(h, x) # Python heapq is a MIN-heap
if len(h) > k:
heapq.heappop(h) # pops the smallest
return h[0] # the k-th largest seen so farThis keeps a running k-th largest with a size-k min-heap. Why is a MIN-heap (not a max-heap) the correct structure here?
Snippet 4 — the unbounded window
def longest_unique_substring(s):
seen = set()
best = 0
for r in range(len(s)):
while s[r] in seen:
seen.add(s[r]) # BUG: should shrink from the left
seen.add(s[r])
best = max(best, len(seen))
return bestThe intended technique is a sliding window over the string. The window never shrinks, so the loop is broken. What is the correct mechanism?
Reading code for its pattern is the same flow run in reverse: a nested loop over sorted data should be two pointers (O(n)); a recursion that recomputes identical states is screaming for memoisation or tabulation (DP); a running k-th element forces a specific heap orientation by which element must be cheaply evicted; and ‘longest contiguous range satisfying a condition’ is a sliding window whose left pointer only moves forward. Name the pattern, check the data structure against the dominant operation, then change the one thing that moves the complexity.
Something unclear?
Ask a question about this lesson. Questions are anonymous and go straight to the author to make the lesson better.