~/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.
Binary search
lo/hi invariants, lower vs upper bound, rotated arrays, bisect.
Notes
Recognise it when: the input is sorted, or a condition flips from False to True exactly once (it's monotone).
def lower_bound(a, x): # first index with a[i] >= x
lo, hi = 0, len(a) # half-open [lo, hi)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < x: lo = mid + 1
else: hi = mid
return lo
- Upper bound: change
<to<=.bisect_leftandbisect_rightare the built-ins. - Rotated array: one half is always sorted. Check whether the target lies in the sorted half.
- Invariant thinking: decide what
loandhimean before writing the loop, and the ±1s follow from that.
Gotchas: an infinite loop when lo = mid with mid = (lo + hi) // 2 (use (lo + hi + 1) // 2 in that case), and empty arrays.
15 problems
Interview roadmap
Binary search Sorted lookups, rotations, searching the answer.
Binary search guide
- Basics: write lower bound yourself basics py · c++ · java easy
- Log entries in a time range py · c++ · java easy
- Binary Search py · c++ · java easy
- Find First and Last Position of Element in Sorted Array py · c++ · java medium
- Search in Rotated Sorted Array py · c++ · java medium
- Find Minimum in Rotated Sorted Array py · c++ · java medium
- Earliest supported version and install order 4 levels OpenAI medium
- Upper bound: first index past a value py · c++ · java easy
- Guess the number when answers arrive one call late OpenAISnowflake hard
- OA: Violation Log Analyzer 2 levels Pinterest medium
- Search a 2D Matrix py · c++ · java medium
- Median of Two Sorted Arrays py · c++ · java hard
- Find K Closest Elements py · c++ · java medium
- Search Insert Position py · c++ · java easy
- Find in Mountain Array hard