~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

1-D dynamic programming

Longest increasing subsequence

O(n log n) with tails[] + bisect; rebuild via parent pointers.

Visual guide Quiz (9) Spot the pattern
Notes

Recognise it when: you need the longest increasing chain, nesting (envelopes, after sorting), or the minimum number of decreasing sequences.

tails = []                     # tails[k] = smallest tail of an increasing subsequence of length k+1
for x in a:
    i = bisect.bisect_left(tails, x)   # bisect_right for non-decreasing
    if i == len(tails): tails.append(x)
    else: tails[i] = x
return len(tails)

O(n log n). To rebuild the sequence, store the index of the tail at each length plus a parent array.

Russian dolls: sort by (width ascending, height descending), then take the LIS on heights.

6 problems

Interview roadmap

1-D dynamic programming One index of state: stairs, robbers, subsequences.

Longest increasing subsequence guide

esc