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

Arrays & hashing

Complexity analysis

Big-O from constraints: n = 10^5 means O(n log n); know the Python constant factors.

Visual guide Quiz (11) Spot the pattern
Notes

Read the constraints first. In Python, plan on roughly 10^7 simple operations per second.

n Target
<= 20 O(2^n), bitmask or backtracking
<= 500 O(n^3)
<= 5 000 O(n^2)
<= 10^5 to 10^6 O(n log n) or O(n)
>= 10^9 O(log n) or O(1): math, binary search on the answer
  • Amortized: list append is O(1) amortized; a dict lookup is O(1) on average.
  • Hidden costs: x in list is O(n). s[i:j] copies. list.pop(0) is O(n), so use deque. sorted() is O(n log n). String += in a loop can be O(n²).
  • Space: recursion uses stack frames, and Python's default recursion limit is about 1000.

In the interview: say the complexity of your first idea out loud, then improve it.

3 problems

Interview roadmap

Arrays & hashing Counting, lookups, sorting with keys, prefix sums.

Complexity analysis guide

esc