What SDE2 DSA actually tests
Not "do you know the trick" — it's: can you recognize the pattern, state the complexity, write clean code, handle edge cases, and communicate while doing it. Talk through the brute force, name the bottleneck, then optimize. A working O(n log n) you can explain beats a buggy O(n) you can't.
Big-O you must recognize on sight
| Complexity | Name | Typical source |
|---|---|---|
| O(1) | constant | hash lookup, array index |
| O(log n) | logarithmic | binary search, balanced tree, heap push/pop |
| O(n) | linear | single pass, two pointers |
| O(n log n) | linearithmic | sorting, heap-based, divide & conquer |
| O(n²) | quadratic | nested loops, naive pair comparison |
| O(2ⁿ) | exponential | subsets, naive recursion without memo |
| O(n!) | factorial | permutations |
The input-size → complexity trick
The constraint tells you the target complexity before you've solved anything:
| n up to | Likely target |
|---|---|
| ≤ 10–12 | O(n!) / O(2ⁿ) — backtracking/brute force is fine |
| ≤ 20–25 | O(2ⁿ) bitmask DP |
| ≤ 500 | O(n³) |
| ≤ 5,000 | O(n²) |
| ≤ 10⁶ | O(n) or O(n log n) |
| ≥ 10⁸ | O(log n) or O(1) |
Use the constraints out loud
"n is up to 10⁵, so an O(n²) ~10¹⁰ won't pass — I need O(n log n) or better." Saying this signals maturity and narrows your options immediately.
Pattern recognition — signal → technique
| If you see… | Reach for |
|---|---|
| contiguous subarray/substring, "longest/at most K" | Sliding window |
| sorted array, pair/triplet summing to target | Two pointers |
| "search space", "minimum X that works", monotonic | Binary search (on answer) |
| grid/graph, shortest path (unweighted), levels | BFS |
| connectivity, all paths, cycles, components | DFS / Union-Find |
| "number of ways", "min/max cost", overlapping subproblems | DP |
| top/smallest K, streaming median, merge K lists | Heap |
| all combinations/permutations/subsets | Backtracking |
| next greater/smaller, matching brackets | Monotonic stack |
| prefix aggregates, range sum | Prefix sums |
How to communicate while coding
- Restate the problem + ask about edge cases (empty, duplicates, negatives, overflow).
- State brute force + its complexity.
- Name the bottleneck and the pattern that removes it.
- Code, narrating invariants.
- Dry-run a small example; then state final time/space.