~/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.

Intervals

Intervals / sweep line

Sort by start, merge; sweep events for overlaps.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: merging ranges, overlaps, meeting rooms, coverage, sweep line.

out = []
for s, e in sorted(intervals):
    if out and s <= out[-1][1]:      # <= merges touching intervals
        out[-1][1] = max(out[-1][1], e)
    else:
        out.append([s, e])
  • Insert into a sorted list: three phases (before, overlapping, after), O(n).
  • Max concurrent (meeting rooms): sweep events (s, +1) and (e, -1), sorted so an end comes before a start at the same time.

Gotchas: decide whether [1, 3] and [3, 5] overlap before writing any code.

14 problems

Interview roadmap

Intervals Merge, insert and sweep over ranges.

esc