DSA: Interview Problem-Solving Strategies
Systematic techniques for clarifying problems, optimizing solutions, handling edge cases, and acing coding interviews.
Problem Understanding and Clarification
Before writing a single line of code, spend 2-3 minutes clarifying the problem. Assumptions you skip here become bugs later. Interviewers reward candidates who ask the right questions.
Clarification Checklist
Ask these before coding. Each answer can completely change the approach.
- Input size: n up to 10³, 10⁵, or 10⁹? Determines acceptable complexity
- Edge cases: empty array, single element, all same, negative numbers?
- Duplicates: are duplicate values allowed in input / output?
- Return type: index, value, count, boolean, or modified array?
- Space constraints: O(1) extra space required or is O(n) acceptable?
Two Sum: Clarification Drives Approach
C++Unsorted + index return = hash map O(n). Sorted + boolean = two-pointer O(n).
Brute Force to Optimized Approach
Always state the brute force first, it proves you understand the problem. Then identify the bottleneck (usually a nested loop) and eliminate it with a better data structure or algorithm.
Optimization Patterns
The inner loop in O(n²) almost always corresponds to a lookup. Replace that lookup with a hash map, prefix sum, or sorted structure.
- Nested loop O(n²) → hash map O(n): eliminate inner search with O(1) lookup
- Repeated subarray scan → prefix sum: precompute cumulative sums
- Re-sorting each step → heap/sorted set: maintain order incrementally
- Recomputing recursion → memoization/DP: cache overlapping subproblems
- Linear scan per query → binary search: requires sorted data
Longest Consecutive Sequence
C++O(n²) brute force to O(n) by only starting chains from sequence beginnings.
Time and Space Complexity Estimation
Knowing which complexity is acceptable for a given input size prevents writing solutions that time out. Use this table before choosing your algorithm.
Complexity Budget
Assume ~10⁸ operations per second. Match your algorithm's complexity to the input size constraints.
- n up to 10³: O(n²) or even O(n³) acceptable
- n up to 10⁵: O(n log n) required; O(n²) too slow
- n up to 10⁶: O(n) or O(n log n) at best
- n up to 10⁹: O(log n) or O(1) only
- Space: O(n) extra usually fine; O(n²) only if n is small
Majority Element: Boyer-Moore Voting
C++O(n) time O(1) space: candidate + count, cancel non-matching pairs.
LRU Cache (Classic Design Problem)
LRU Cache requires O(1) get and put. A hash map gives O(1) key lookup; a doubly linked list maintains access order so the least recently used node is always at the tail.
LRU Cache
Hash map maps key to list node. On access/insert, move node to front. On capacity, evict tail node.
- Hash map: key to doubly-linked-list node pointer
- List front = most recent, list tail = least recent
- get(key): move to front, return value; return -1 if absent
- put(key, val): move to front if exists; else insert front; if over capacity, remove tail
- Both operations O(1), list pointer manipulation + hash map update
LRU Cache
C++Hash map to node + doubly linked list: O(1) get and put via splice.
Min Stack (O(1) getMin)
Design a stack that supports push, pop, top, and getMin all in O(1). Maintain an auxiliary min-stack that stores the current minimum at each level of the main stack.
Min Stack
Two stacks: main stack and min-stack. Min-stack top always holds the minimum of the current main stack state.
- Push: push to main stack; push min(val, minStack.top()) to min-stack
- Pop: pop both stacks simultaneously
- getMin: return minStack.top() in O(1)
- Space: O(n) extra for the min-stack (worth it for O(1) getMin)
Min Stack
C++Parallel min-stack records running minimum at each stack depth.
Array Rotation: Multiple Approaches
Rotate an array of n elements right by k positions. Compare approaches to see how data structure choice and algorithmic insight reduce time and space complexity.
Array Rotation Approaches
Three reversal trick: O(n) time, O(1) space, reverse all, reverse first k, reverse the rest.
- Brute force: rotate one step at a time, k times, O(n*k), O(1) space
- Extra array: place each element at (i+k)%n, O(n) time, O(n) space
- Three reversals: reverse[0..n-1], reverse[0..k-1], reverse[k..n-1], O(n) time, O(1) space
- Normalize k: k = k % n (handle k > n)
Array Rotation: Three Reversals
C++O(n) time, O(1) space via three in-place reverse operations.
Edge Case Handling and Testing
Interviewers specifically test edge cases. Run through this checklist mentally before declaring your solution correct.
Edge Case Checklist
Most interview bugs live in edge cases, not the main logic. Test these before submitting.
- Empty input: empty array, empty string, null pointer
- Single element: array of size 1, tree with one node
- All same elements: [5,5,5,5], breaks many two-pointer / sliding window solutions
- Already sorted / reverse sorted: worst case for naive quick sort
- Negative numbers: affects sum comparisons and modular arithmetic
- Integer overflow: use long long when multiplying or summing large values
- k = 0 or k = n: rotation, window size, top-k boundary conditions
Maximum Product Subarray
C++Track both max and min products: negatives flip them, zeros reset both.
Common Mistakes to Avoid
These mistakes appear in almost every interview. Knowing them in advance eliminates avoidable bugs.
| Mistake | Example | Fix |
|---|---|---|
| Integer overflow | int a = 1e9; a * a overflows | Use long long for products |
| Off-by-one in binary search | lo <= hi vs lo < hi | Decide: inclusive or exclusive hi |
| Modifying array while iterating | Erase in a range-for loop | Use index loop or collect indices first |
| Not normalizing k | Rotate by k > n | k = k % n before rotating |
| Forgetting null check | node->next when node is nullptr | Check node && node->next |
| Hash map default value | map[key] creates 0 entry | Use map.count(key) to check existence |
| Stack overflow in recursion | No base case or too deep | Add base case; convert to iterative if n > 10⁴ |
| Floating point comparison | if (a == b) for doubles | Use if (abs(a - b) < 1e-9) |
Interview Process: Step-by-Step
Follow this sequence in every coding interview to maximize your score regardless of the problem.
| Step | Action | Time |
|---|---|---|
| 1. Clarify | Ask about constraints, edge cases, return type | 2-3 min |
| 2. Examples | Walk through 2 examples including an edge case | 2 min |
| 3. Brute force | State O(n²) or naive solution, explain why it works | 2 min |
| 4. Optimize | Identify bottleneck, apply pattern, state new complexity | 3-5 min |
| 5. Code | Write clean code, narrate what each part does | 10-15 min |
| 6. Dry run | Trace through your example manually on the code | 3 min |
| 7. Edge cases | Test empty, single, all-same, overflow scenarios | 2 min |
| 8. Complexity | State final time and space complexity clearly | 1 min |
Knowledge Check
1. What is the first step when you receive a coding interview problem?
2. An O(n²) nested loop solution can often be optimized to O(n) by:
3. LRU Cache requires O(1) get and put. The correct data structure combination is:
4. When estimating if O(n²) is fast enough, a rough rule is:
5. Which edge cases should always be tested?
6. The "brute force first" interview strategy is valuable because:
7. Min Stack (getMin in O(1)) is implemented by:
8. Array rotation by k positions in O(1) space uses: