Assess the ability to analyze, compare, and optimize algorithmic solutions with respect to time and space resources. Candidates should be fluent in Big O notation and able to identify dominant operations, reason about worst case, average case, and amortized complexity, and calculate precise time and space bounds for algorithms and data structure operations. The topic includes recognizing complexity classes such as constant time, logarithmic time, linear time, linearithmic time, quadratic time, and exponential time, and understanding when constant factors and lower order terms affect practical performance. Candidates should know and apply common algorithmic patterns and techniques, including two pointers, sliding window, divide and conquer, recursion, binary search, dynamic programming, greedy strategies, and common graph algorithms, and demonstrate how to transform brute force approaches into efficient implementations. Coverage also includes trade offs between time and space and when to trade memory for speed, amortized analysis, optimization tactics such as memoization, caching, pruning, iterative versus recursive approaches, and data layout considerations. Candidates must be able to reason about correctness, invariants, and edge cases, identify performance bottlenecks, and explain practical implications such as cache behavior and memory access patterns. For senior roles, be prepared to justify precise complexity claims and discuss optimization choices in system level and constrained environment contexts.
MediumTechnical
74 practiced
Implement the Minimum Window Substring problem in JavaScript: given strings s and t, return the smallest substring of s that contains all characters of t (including multiplicity). Your solution should aim for O(n) average time using a sliding-window and character counts. Provide code and analyze time and space complexity; mention edge cases and how your window becomes 'valid' and how you shrink it.
Sample Answer
**Approach (brief)** Use a sliding-window with two pointers, a hashmap for required character counts from t, and a running count of how many required characters are currently satisfied. Expand right to include chars, and when window is valid (all required counts met) try to shrink from left to find the minimal window.**Code (JavaScript)**
javascript
function minWindow(s, t) {
if (!s || !t || s.length < t.length) return "";
const need = new Map();
for (const ch of t) need.set(ch, (need.get(ch) || 0) + 1);
let left = 0, formed = 0, required = need.size;
const windowCounts = new Map();
let minLen = Infinity, minLeft = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
windowCounts.set(c, (windowCounts.get(c) || 0) + 1);
if (need.has(c) && windowCounts.get(c) === need.get(c)) {
formed++;
}
// When window is valid, try to shrink
while (left <= right && formed === required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
minLeft = left;
}
const cl = s[left];
windowCounts.set(cl, windowCounts.get(cl) - 1);
if (need.has(cl) && windowCounts.get(cl) < need.get(cl)) {
formed--;
}
left++;
}
}
return minLen === Infinity ? "" : s.slice(minLeft, minLeft + minLen);
}
**Why it’s valid / how shrinking works** - The window is "valid" when for every char in need, windowCounts >= need (tracked via formed === required). - Shrinking increments left while keeping validity; when removing a char breaks a required count, formed decrements and window becomes invalid, so we stop shrinking.**Complexity** - Time: O(n) average — each character is visited by right once and left at most once. Map operations are O(1) average. - Space: O(k + m) where k is alphabet distinct chars in s and m is distinct chars in t (maps), worst-case O(n).**Edge cases** - t empty -> return "" (or could define behavior) - s shorter than t -> "" - characters with multiplicity (handled by counts) - Unicode: code treats JS string code units; for full Unicode grapheme correctness, preprocess if needed.
HardSystem Design
71 practiced
Design an autocomplete system for low-latency prefix queries across millions of distinct words. Compare data structures: trie (compressed/trie/DAWG), sorted arrays with binary search, prefix B-tree, and discuss memory/time trade-offs. Include how you'd support frequency-based ranking, sharding across machines, caching hot prefixes, and handling fuzzy matches (typos). For each approach give expected lookup complexity and memory implications.
Sample Answer
**Clarify requirements**- Millisecond latency for prefix queries across millions of distinct words, support ranking by frequency, fuzzy matches, horizontal scale, and caching.**High-level trade-offs (summary)**- Trie family: very low-latency prefix lookup, high pointer overhead; compressed trie / DAWG reduces memory; good for in-memory hot shards.- Sorted array + binary search: compact (contiguous strings), binary-search to find prefix range, then scan — cpu-friendly, cache-locality, but scanning many matches costs time.- Prefix B-tree: disk/SSD-friendly, good for persistent store, moderate latency.- DAWG: smallest memory for static dictionary, O(|prefix|) lookup.**Per-approach details**1) Compressed Trie / Radix Tree / DAWG- Lookup: O(k) where k = prefix length.- Memory: tries store edges/pointers — naive tries high (O(sum lengths)), compressed/DAWG much less; DAWG best for static sets.- Ranking: store top-N suggestions at each node (precomputed frequencies).- Fuzzy: traverse neighbors with edit-distance DP; cost grows with edit budget — use beam/pruning.2) Sorted array (strings)- Lookup: O(k log N) for comparison-based binary search (string compare O(k)), then scan M matches.- Memory: O(total chars) + index.- Ranking: maintain parallel frequency array; after range found, partial sort/top-k.- Fuzzy: filter candidates with edit-distance; expensive unless narrowed by prefix-first.3) Prefix B-tree- Lookup: O(log_b N) disk I/O + O(k) per compare; tuned for SSDs.- Memory: small on server, good for persistence.- Ranking: store frequency in leaf or cache top-N per node.- Fuzzy: same as sorted array with additional I/O.**Sharding & scaling**- Shard by hash of prefix or by first N chars (prefix-range). Use consistent hashing for hot prefix spread.- Keep per-shard in-memory trie/DAWG for hot partitions; fallback to B-tree/DB for cold shards.- Replicate shards for read-scaling and availability.**Caching & hot prefixes**- LRU cache for full query -> suggestions.- Cache top-N lists at trie nodes; CDN or edge cache for very hot prefixes.- Precompute and refresh top suggestions asynchronously.**Fuzzy matching**- Use BK-tree or metric-tree on tokens for pure typo search, or apply trie + bounded edit-distance A* / beam search.- Combine phonetic normalization, n-gram filtering, and candidate scoring to reduce cost.**Complexities recap**- Compressed Trie/DAWG: lookup O(k), memory high->moderate (DAWG best).- Sorted array + binary search: O(k log N + R) where R = results scanned, memory minimal.- Prefix B-tree: O(log_b N * k + R) I/O-sensitive, memory modest.Choice: for low-latency at scale use shardable in-memory compressed trie/DAWG with per-node top-N, edge caching, and fallback persistent index (B-tree) for cold data; use fuzzy candidate pruning (n-gram / BK-tree) to limit edit-distance cost.
HardSystem Design
70 practiced
Design a concurrent LRU cache for a multi-core server that supports O(1) get and put in the common case and scales under contention. Discuss data structures (linked list + hash map), locking strategies (global lock, per-shard locks), lock-free options, memory overhead per entry, and eviction correctness under concurrency. Explain how sharding affects hit ratio and eviction order and propose metrics to monitor.
Sample Answer
**Clarify requirements & goals**- O(1) common-case get/put, good multi-core scaling, bounded memory, correct LRU semantics (or best-effort under sharding).**High-level design**- Classic: doubly linked list (LRU order) + hash map(key → node) for O(1).- For concurrency use sharding: partition key-space into N independent shards (power of two). Each shard has its own map + list + lock. This gives parallelism and O(1) per shard.**Locking strategies**- Global lock: simple but serializes all ops — bad for multi-core.- Per-shard locks (recommended): a mutex per shard; get can be fully under shard lock. Use optimistic reads (read-copy-update or RW-lock) for reads if needed.- Fine-grained per-node locks / lock-free linked list: complex and higher overhead; consider only for extreme throughput needs (use hazard pointers or epoch GC).- Use try-lock + backoff for eviction hot-spots.**Eviction & correctness**- Within a shard, eviction is exact LRU. Across shards, global LRU ordering is approximate — items are evicted per-shard independently.- To maintain stricter global LRU: maintain a global min-heap of per-shard candidates or use a central coordinator — increases contention.- Ensure atomicity: move node to head on access under shard lock; on concurrent put/update, replace node safely.**Memory overhead**- Per entry: key + value + hashmap pointer + prev/next pointers (2) + metadata (size, timestamp) ≈ 3-5 pointers + payload. For 64-bit: ~40–64 bytes overhead excluding key/value.**Sharding trade-offs**- Pros: better throughput, lower contention.- Cons: reduced hit ratio if keys skewed; eviction order becomes per-shard (not globally strict). Choose number of shards to balance concurrency vs per-shard capacity.**Monitoring metrics**- hit rate, miss rate, evictions/sec, per-shard lock contention (avg wait, try-lock failures), ops/sec, tail latency, memory usage, per-shard occupancy/skew.**When to go further**- If strict global LRU required: use global coordination (higher contention) or sampled global LRU (CLOCK, TinyLFU) for good practical trade-offs.
EasyTechnical
94 practiced
Explain the difference between Big O, Big Omega, and Big Theta notation. Provide concrete examples of functions f(n) and g(n) where f(n) is O(g(n)) but not Theta(g(n)). Describe which notation you use when communicating worst-case, best-case, and average-case complexity in an interview, and why. Give one short, real-world example (e.g., a search operation) to illustrate the notation choices.
Sample Answer
**Definitions**- Big O (O): an asymptotic upper bound: f(n) = O(g(n)) means f grows no faster than g up to constant factors for large n.- Big Omega (Ω): an asymptotic lower bound: f(n) = Ω(g(n)) means f grows at least as fast as g up to constants.- Big Theta (Θ): a tight bound: f(n) = Θ(g(n)) means f is both O(g) and Ω(g).**Concrete example**- Let f(n) = n and g(n) = n^2. - f(n) = O(g(n)) because n ≤ c·n^2 for n ≥ 1 (choose c = 1). - f(n) ≠ Θ(g(n)) because n is not Ω(n^2) (n grows slower than n^2).**Which notation to use in interviews**- Worst-case: use Big O (e.g., "worst-case time O(n log n)").- Best-case: use Big Omega (e.g., "best-case Ω(1)").- Average-case: use Big Theta when you can show a tight expected bound (e.g., "average-case Θ(n)"), otherwise state expected complexity with Big O and clarify it's expected/average.**Real-world example**- Linear search in an unsorted array: best-case Ω(1) (target at index 0), worst-case O(n) (or Θ(n) if target absent or uniformly random), average-case Θ(n) under uniform distribution.- Hash table lookup: average-case Θ(1), worst-case O(n) (pathological collisions) — state which case you're referring to.
HardTechnical
70 practiced
Compare breadth-first search using an adjacency list representation versus Compressed Sparse Row (CSR) storage for a large sparse graph. Give precise complexity in terms of V and E, analyze cache behavior and memory layout differences, and justify when CSR yields practical speedups for BFS traversals. Also discuss the cost of dynamic updates (adding/removing edges) in both representations.
Sample Answer
**Brief answer / complexity**- BFS time complexity (one traversal): - Adjacency list: visits each vertex and scans its neighbor lists ⇒
text
O(V + E)
- CSR: same work, sequentially scanning neighbor arrays ⇒
text
O(V + E)
**Memory layout & cache behavior**- Adjacency list (vector<vector<int>> or linked lists) - Per-vertex pointer/offset overhead; neighbor lists may be scattered in heap. - Poor spatial locality (especially with linked lists); pointer chasing causes many cache misses. - If implemented as vector<vector<int>> and preallocated, locality improves but outer vectors still cause indirection.- CSR (two arrays: offsets[V+1], edges[E]) - Contiguous edges array yields highly sequential memory access when scanning neighbors. - Much better L1/L2 prefetching and cache-line utilization; fewer branch mispredictions. - Lower memory overhead (no per-list allocations).**When CSR yields practical speedups**- Large sparse graphs where E >> V and neighbor scans dominate.- Read-heavy workloads with many traversals (analytics, shortest-path batches).- When memory layout can be built once and reused (static graph).- Empirically, CSR often gives 2x–10x speedups for BFS on single-threaded CPU due to cache and branch improvements.**Cost of dynamic updates**- Adjacency list: - Add/remove edge: O(1) amortized (push_back, or remove by swap/pop if order not required; otherwise O(deg(v))). - Good for frequent mutations and incremental algorithms.- CSR: - Static by design. To add/remove edges typically requires rebuilding arrays: - Full rebuild: O(V + E) time and memory to create new offsets/edges. - More complex dynamic CSR variants (gap buffers, segmented arrays) add implementation complexity and increase per-update cost. - Not suitable for workloads with frequent arbitrary updates.**Practical recommendation (Full‑Stack perspective)**- For web backend services that perform many read-only graph queries (recommendation, social-graph analytics), store graph in CSR in memory or memory-mapped file for performance.- For APIs that mutate graph often (user follows/unfollows), use adjacency lists (or hybrid: dynamic adjacency lists plus periodic CSR snapshots for analytics).
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
