Comprehensive coverage of fundamental data structures, their operations, implementation trade offs, and algorithmic uses. Candidates should know arrays and strings including dynamic array amortized behavior and memory layout differences, linked lists, stacks, queues, hash tables and collision handling, sets, trees including binary search trees and balanced trees, tries, heaps as priority queues, and graph representations such as adjacency lists and adjacency matrices. Understand typical operations and costs for access, insertion, deletion, lookup, and traversal and be able to analyze asymptotic time and auxiliary space complexity using Big O notation including constant, logarithmic, linear, linearithmic, quadratic, and exponential classes as well as average case, worst case, and amortized behaviors. Be able to read code or pseudocode and derive time and space complexity, identify performance bottlenecks, and propose alternative data structures or algorithmic approaches to improve performance. Know common algorithmic patterns that interact with these structures such as traversal strategies, searching and sorting, two pointer and sliding window techniques, divide and conquer, recursion, dynamic programming, greedy methods, and priority processing, and when to combine structures for efficiency for example using a heap with a hash map for index tracking. Implementation focused skills include writing or partially implementing core operations, discussing language specific considerations such as contiguous versus non contiguous memory and pointer or manual memory management when applicable, and explaining space time trade offs and cache or memory behavior. Interview expectations vary by level from selecting and implementing appropriate structures for routine problems at junior levels to optimizing naive solutions, designing custom structures for constraints, and reasoning about amortized, average case, and concurrency implications at senior levels.
MediumTechnical
101 practiced
Implement Quickselect in Python to find the k-th smallest element in an unsorted list with average O(n) time. Provide an in-place implementation, discuss pivot selection strategies (randomized vs median-of-medians), explain worst-case behavior, and state how to modify to guarantee linear worst-case time.
Sample Answer
To implement Quickselect in-place, we use the partition routine from Quicksort to position a pivot and recurse only into the side containing the k-th smallest. Average time is O(n); worst-case O(n^2) for poor pivots. Below is an in-place Python implementation with randomized pivot selection.
python
import random
def quickselect(arr, k):
"""
Return the k-th smallest element (0-based k) in arr in-place.
Raises IndexError for invalid k.
Average O(n) time, O(1) extra space (in-place).
"""
if not 0 <= k < len(arr):
raise IndexError("k out of range")
def partition(l, r):
# choose random pivot and move it to end
pivot_idx = random.randint(l, r)
arr[pivot_idx], arr[r] = arr[r], arr[pivot_idx]
pivot = arr[r]
store = l
for i in range(l, r):
if arr[i] < pivot:
arr[store], arr[i] = arr[i], arr[store]
store += 1
arr[store], arr[r] = arr[r], arr[store]
return store
def select(l, r, k):
while True:
if l == r:
return arr[l]
p = partition(l, r)
if k == p:
return arr[p]
elif k < p:
r = p - 1
else:
l = p + 1
return select(0, len(arr) - 1, k)
Key points:- Pivot strategies: randomized pivot (above) gives expected O(n) and avoids adversarial inputs; choosing median-of-three (arr[l], arr[mid], arr[r]) can reduce variance. Median-of-medians (BFPRT) selects an approximate median deterministically, guaranteeing O(n) worst-case but with larger constant factors.- Worst-case: always picking extreme pivots causes recursion depth O(n) and O(n^2) comparisons.- To guarantee linear worst-case time, replace partition's pivot selection with median-of-medians: group elements in groups of 5, compute medians, recursively find their median, and use that as pivot. This yields deterministic O(n) time at the cost of more work per partition.Edge cases: empty array, k out of range, duplicate values (handled).
HardTechnical
77 practiced
A batch job currently sorts all users by activity every minute to produce the top-100 active users, but this is expensive at scale. Propose algorithms and data structures to avoid full sorts each minute: incremental updates, maintaining a min-heap of size k, stream algorithms (Space-Saving/Count-Min), and approaches to implement this in a distributed environment with partial aggregators. Discuss latency, correctness, and fault tolerance trade-offs.
Sample Answer
Situation: You need top-100 active users every minute but full sort of N users is too expensive.Approach summary (algorithms & data structures)1. Incremental counters + min-heap (exact)- Maintain a hashmap user_id -> activity_count updated in streaming fashion.- Keep a size-k min-heap of (count,user_id). On each update: update hashmap; if user is in heap, adjust position; else if count > heap.min then pop and push new.- Complexity: O(log k) per update; memory O(N) for counters + O(k) for heap.- Correctness: exact top-k if counts are precise and updates applied before snapshot.2. Stream algorithms (approximate)- Space-Saving: track O(k/ε) counters for heavy hitters; provides guaranteed error bounds.- Count-Min Sketch + heap: approximate counts with CMS; maintain candidate set and rank by CMS estimates.- Tradeoff: drastically lower memory; controlled error vs false positives/negatives.3. Distributed partial aggregators- Partition stream by user_id across shards (consistent hashing). Each shard maintains local counters and local top-k.- Periodically (e.g., every 10s) emit local top-k to a central merger which merges O(m*k) lists into global top-k using a min-heap.- Use combiner pattern in MapReduce/Kafka Streams/Flink.Latency, correctness, fault tolerance trade-offs- Latency: in-memory per-update heap gives sub-ms updates; distributed merging introduces aggregation window latency (e.g., 1–10s). Choose window to balance freshness vs network load.- Correctness: exact approach yields precise top-k; distributed partials require deterministic partitioning to avoid double-counting. Approximate algorithms trade exactness for throughput.- Fault tolerance: persist counters or use changelog (Kafka) so a failed shard can rebuild state. Use checkpointing (Flink) or write incremental deltas to durable store. For eventual consistency, accept slight staleness; for strict correctness, use synchronous writes at cost of latency.Implementation notes- Use stream processing (Flink/Kafka Streams) with keyed state + RocksDB for large state; emit local top-k and do hierarchical merging.- Monitor error rates (for approx methods) and tail-latencies; provide fallback full-aggregate during anomalies.Recommendation: start with partitioned exact counters + local min-heaps and periodic global merge. If state/memory becomes limiting, move to Space-Saving/Count-Min with monitored error bounds.
HardTechnical
101 practiced
Compare a naive recursive Fibonacci function, a memoized recursive version, and an iterative bottom-up dynamic programming implementation. Derive the time and space complexity for each approach, explain why memoization reduces exponential complexity to linear, and discuss trade-offs in recursion stack usage, locality, and when to prefer iterative tabulation.
Sample Answer
Naive recursive FibonacciSituation/approach: f(n)=f(n-1)+f(n-2) with base f(0)=0,f(1)=1.Time complexity: O(φ^n) ≈ O(1.618^n) — exponential, because the recursion recomputes the same subproblems many times. Space complexity: O(n) worst-case recursion depth (stack), but extra working memory is O(1) aside from call stack.Memoized recursive (top‑down DP)Approach: store results of f(k) in a dictionary/array when first computed and reuse them.Time complexity: O(n) — each f(k) computed once and then O(1) lookup. Space complexity: O(n) for the memo + O(n) recursion stack worst case → total O(n).Why it reduces exponential to linear: memoization eliminates repeated subproblem recomputation. The recursion tree of the naive method has exponentially many repeated nodes; memoization collapses that tree into a DAG where each node is evaluated once.Iterative bottom‑up (tabulation)Approach: compute f(0), f(1), …, f(n) iteratively storing in array or just two variables.Time complexity: O(n). Space complexity: O(n) if storing entire table; O(1) if using constant rolling variables.Trade-offs and practical considerations- Recursion stack: memoized recursion uses recursion depth O(n) which risks stack overflow for large n; iterative avoids that.- Locality: iterative/tabulation has better memory locality and cache behavior—faster in practice for large n and data‑intensive workloads common to data science.- Readability vs performance: memoized recursion is concise and maps naturally to problem structure; iterative is more explicit and efficient.When to prefer iterative tabulation: for very large n, tight performance/memory constraints, or production code that must avoid recursion limits and maximize cache locality. Memoization/top‑down is preferred when only a subset of states is needed (sparse access) or for easier mapping from recursive definitions.
MediumTechnical
98 practiced
Compare tries (prefix trees), compressed tries (radix trees), and hash maps for prefix lookup/autocomplete. Discuss time complexity per operation, memory overhead, cache behavior, and practical trade-offs. Also mention ternary search trees and when they might be chosen for memory vs speed balance.
Sample Answer
High-level summary: For prefix lookup/autocomplete the choice depends on workload (read vs write), key set size, memory budget, and latency requirements. Below I compare tries (prefix trees), compressed tries/radix trees, hash maps, and mention ternary search trees (TSTs).Tries (standard prefix tree)- Complexity: Insert/search/prefix-search O(L) where L = key length; prefix autocomplete (walk to node + DFS) cost = O(L + k) where k is number of returned results (plus cost per result).- Memory: High — one node per character with pointers/children maps leads to large overhead for sparse alphabets.- Cache behavior: Poor if nodes allocate separately (pointer chasing). Wide fan-out hurts locality.- Trade-offs: Excellent for ordered prefixes, lexicographic iteration, and guaranteed worst-case lookup by character. Use when you need fast prefix iteration and can afford memory.Radix trees / compressed tries- Complexity: Same O(L) in practice but fewer nodes because paths of single-child nodes are compressed; prefix-search is O(m + k) where m is length of matched prefix segments.- Memory: Much lower than naive tries (node count reduced), stores edge-labels (strings) instead of single chars.- Cache: Better locality (fewer nodes), fewer pointer hops.- Trade-offs: Often best balance of speed and memory for large vocabularies; good for disk-backed or persistent stores.Hash maps- Complexity: Average-case lookup O(L) if hashing full key (or O(1) assuming hash computed), but pure hash maps don’t support efficient prefix queries — you must iterate over keys, or maintain additional prefixes (costly).- Memory: Lower per-key overhead than naive tries if using compact hash table, but storing full strings duplicates prefix storage.- Cache: Good (contiguous buckets) but depends on implementation.- Trade-offs: Great for exact-match lookup and very fast lookups. For autocomplete either maintain additional prefix-index (e.g., n-grams) or use ordered hash variants — otherwise inefficient.Ternary search trees (TSTs)- Complexity: O(L) average; each node has three pointers (less memory than full child map when alphabet large).- Memory: Lower than standard trie for sparse data; higher than highly compressed radix trees but much better locality.- Cache: Better than pointer-rich tries due to binary-search-like layout; nodes are more compact.- Trade-offs: Good middle-ground when you want lower memory than a trie but faster prefix operations than hash-based approaches.Practical guidance for a Data Scientist- For production autocomplete on large vocabularies: prefer radix trees or a proven library (e.g., DAWG, FST) — they compress common prefixes and support fast ranked/top-k queries.- If you only need exact lookups, use hash maps.- If memory is constrained but you still need prefix search, consider TSTs or finite-state transducers (FSTs) which are very compact and support ranked suggestions.- Also consider engineering aspects: persistence (on-disk FSTs), incremental updates (tries easier), and ML needs (storing scores/weights at nodes for ranked autocomplete).
MediumTechnical
72 practiced
When would you choose a binary search tree (BST) over a hash table for storing key-value pairs in an ML feature store? Discuss use-cases that require ordered traversal or range queries, compare average and worst-case performance, and describe balanced-tree alternatives (AVL, Red-Black, B-tree) for production systems.
Sample Answer
Choose a BST over a hash table in a feature store when you need ordered semantics or efficient range/nearest‑neighbor queries that hashes can't support directly.When to prefer BST / balanced tree:- Range queries: retrieving features for keys in [t1, t2] (e.g., time-windowed feature aggregation) — O(log n + k) with in-order traversal.- Ordered traversal: computing rolling stats, percentile-based binning, or exporting features in sorted order for join/merge operations.- Successor/predecessor queries: finding the previous version/timestamp of a feature for causal feature construction.Performance comparison:- Hash table (average): O(1) lookup/insert/delete; worst-case O(n) if many collisions or poor hash.- BST (unbalanced): average O(log n) if keys random; worst-case O(n) for degenerate trees.- Balanced BST: guarantees O(log n) worst-case for lookup/insert/delete.Balanced-tree alternatives for production:- Red‑Black Tree: good practical balance, O(log n) operations, lower constant factors.- AVL Tree: tighter balancing than RB, faster lookups, slightly more rotations on insert/delete.- B-Tree / B+Tree: used in disk-backed or SSD-backed stores (e.g., feature store index), optimized for block I/O and range scans.- Consider LSM-trees or RocksDB for write-heavy, disk-backed feature stores; they combine sorted runs with compaction and support range scans.Practical advice:- Use hash table (or KV store) for pure point-lookup, low-latency read-mostly features.- Use balanced tree or B‑Tree when you need ordering/range queries, consistent worst-case latency, or efficient on-disk indexing.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
