Stage 1 · Code
Interview Preparation
Complexity Analysis
Time/space analysis, amortized analysis, and explaining trade-offs.
Time Complexity
Count dominant operations as function of input size n. Drop constants and lower terms. Common: O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
| Pattern | Time | Example |
|---|---|---|
| Single loop | O(n) | Linear search |
| Nested loops | O(n²) | Bubble sort |
| Divide input by 2 | O(log n) | Binary search |
| Divide + combine | O(n log n) | Merge sort |
| Recursion (2 branches) | O(2ⁿ) | Naive Fibonacci |
| All permutations | O(n!) | N-Queens |
Space Complexity
Auxiliary space only (exclude input). Recursion uses call stack. Dynamic programming uses table. Key question: does space scale with n?
| Approach | Space | Note |
|---|---|---|
| Iterative + variables | O(1) | Two pointers, sliding window |
| Recursion | O(depth) | DFS tree height, binary search |
| DP table | O(n) or O(n²) | Can often optimize to O(n) |
| Hash map/set | O(n) | Frequency counter, seen set |
| Priority queue | O(n) | Dijkstra, heap sort |
| Output array | O(n) | Required for result |
Amortized Analysis
Average cost over sequence of operations. Dynamic array append: most O(1), occasional O(n) resize → O(1) amortized. Aggregate method: total cost / n operations. Accounting method: prepay for expensive ops.
Explaining Trade-offs
Always discuss: 'Approach A: O(n) time, O(n) space. Approach B: O(n log n) time, O(1) space. I'll use A because...' or 'Can optimize space to O(1) with two pointers but code is more complex.' Interviewers value awareness of trade-offs over just 'the right answer'.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.