~/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.
Prefix sums + binary search
Weighted sampling: bisect into cumulative weights.
Notes
Recognise it when: weighted random choice, "which bucket does x fall in", cumulative ranges, range sums.
prefix = list(itertools.accumulate(weights))
target = rng() * prefix[-1] # [0, total)
return bisect.bisect_right(prefix, target)
Index i owns [prefix[i-1], prefix[i]). bisect_right returns the first prefix that is strictly greater than the target, which also skips zero-weight buckets.
Range sums: sum(a[l:r]) == P[r] - P[l] with P[0] = 0.
5 problems
Interview roadmap
Binary search Sorted lookups, rotations, searching the answer.
Prefix sums + binary search guide
- Basics: which bucket holds position x basics py · c++ · java easy
- How far does the ticket money go? py · c++ · java easy
- Random Pick with Weight py · c++ · java medium
- Generate Random NFT Coinbase medium
- How many items fit the budget Uber py · c++ · java easy