1. Input goes from 1,000 to 1,000,000. An O(log n) step count roughly...
- Triples
- Grows 1000x
- Grows by ~10 steps
- Doubles
Show answer
Answer: Grows by ~10 steps
log2(1e6) - log2(1e3) is about 20 - 10 = 10 extra steps.
Lesson: Big-O & Complexity
22 questions from the Data Structures and Algorithms: Patterns for Interviews course, each with the correct answer and an explanation. Try to answer before you open the answer.
Answer: Grows by ~10 steps
log2(1e6) - log2(1e3) is about 20 - 10 = 10 extra steps.
Lesson: Big-O & Complexity
Answer: Compare character counts
Counting each character is O(n); permutations are O(n!).
Lesson: Strings
Answer: Hash map
Hash map is average O(1) per lookup; binary search is O(log n) and needs sorting.
Lesson: Hash Map
Answer: O(n)
Sorted inserts create a right-leaning chain — effectively a linked list. Balanced trees (AVL, red-black) fix this.
Lesson: Binary Search Tree
Answer: O(log n)
Both walk up/down the index by flipping the lowest set bit, taking O(log n) steps.
Lesson: Fenwick Tree (BIT)
Answer: All edge weights are non-negative
Negative weights can invalidate the greedy 'closest node is final' assumption — use Bellman-Ford instead.
Lesson: Dijkstra's Algorithm
Answer: Nearly O(1) (inverse-Ackermann)
The amortized complexity is O(α(n)), the inverse Ackermann function, which is effectively constant for any realistic n.
Lesson: Union-Find / Disjoint Set
Answer: Sorted (or monotonic on the predicate)
Discarding half only works if one side is guaranteed to not contain the target — that needs order.
Lesson: Binary Search
Answer: O(n log n)
The split is always balanced, so it's O(n log n) in every case — unlike quicksort.
Lesson: Merge Sort
Answer: Sorted
Sorted order is what lets you decide which pointer to move from the current sum.
Lesson: Two Pointers
Answer: BFS
BFS explores in order of distance, so the first time it reaches the target is a shortest path. DFS gives no such guarantee.
Lesson: Depth-First Search
Answer: 2 coins (3 + 3)
3+3 = 6 uses two coins. Greedy fails here — coin change needs DP in general.
Lesson: Greedy
Answer: O(n + m)
The LPS array is built in O(m), and the search itself is O(n) since the text pointer never backtracks.
Lesson: String Matching
Answer: It allows O(1) removal of a node given only a pointer to it
With a prev pointer, a node can unlink itself in O(1); a singly linked list would need O(n) to find the previous node.
Lesson: LRU Cache Design
Answer: O(log n)
Each step halves the search range.
Lesson: K-way Merge
Answer: Hash map
A hash function maps keys to buckets.
Lesson: K-way Merge
Answer: Stack
Push openings, pop on closings.
Lesson: K-way Merge
Answer: BFS
BFS explores level by level.
Lesson: K-way Merge
Answer: All edge weights are non-negative
Negative edges need Bellman-Ford.
Lesson: K-way Merge
Answer: O(n log n)
It always splits and merges evenly.
Lesson: K-way Merge
Answer: Sliding window
Expand right, shrink left as needed.
Lesson: K-way Merge
Answer: Overlapping subproblems and optimal substructure
Store subproblem answers to avoid recomputation.
Lesson: K-way Merge