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.
HardTechnical
122 practiced
Design a compact approximate-count data structure to track per-feature heavy hitters across millions of users with bounded memory, e.g., Count-Min Sketch. Explain update and query complexity, the probabilistic error bounds, and how you'd combine sketches from multiple workers to get global estimates.
Sample Answer
Design:- Use a Count-Min Sketch (CMS) keyed by (feature_id, user_id) to track counts of interactions per (feature, user). CMS is a d×w integer array with d pairwise-independent hash functions h1..hd. To reduce memory and still retrieve per-feature heavy users, either: - Maintain one global CMS over composite keys (feature||user) and post-filter candidate heavy users per feature; or - Maintain one CMS per feature for very hot features, and a global CMS for the long tail.- Complement CMS with a small Space-Saving top-k (or reservoir) per feature to keep exact candidates; use CMS to estimate counts and prune false positives.Update and query:- Update(key, Δ): for i in 1..d, increment table[i][hi(key)] += Δ. Complexity O(d).- Query(key): estimate = min_i table[i][hi(key)]. Complexity O(d).- For heavy-hitter extraction per feature, iterate candidate user_ids (from Space-Saving or external candidate list) and query CMS for each, or for rare features scan a user id space if small.Probabilistic error bounds:- CMS provides an additive one-sided error: estimated_count >= true_count, and with parameters w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, Pr[estimate ≥ true_count + ε·||f||1] ≤ δ, where ||f||1 is the total sum of updates (global L1). So error is at most ε·total_count with probability 1−δ. Overestimates come from collisions with other keys hashing to same column. Using conservative updates (increment only the minimal counters) reduces overestimation in practice.Merging across workers (distributed):- CMS is linear: two sketches with identical d,w and hash functions can be merged by element-wise addition of their tables. That yields the same error guarantees as a single monolithic CMS built from combined stream. Important: workers must use the same hash seeds, same w & d; ensure counters have sufficient width (avoid overflow).- For streaming aggregation: periodically push local CMS to aggregator, sum matrices, and run heavy-hitter extraction on the global sketch. To reduce network cost, transmit only nonzero buckets or use compressed integer deltas.Practical tips and trade-offs:- If unbiased estimates and symmetric error are needed, consider Count Sketch (uses signed hashes and median) — better for l2-heavy signals.- Use Space-Saving or Frequent algorithm per feature to get exact top-k with bounded memory; validate candidates with CMS to filter false positives.- Choose ε relative to acceptable absolute error (e.g., 0.1% of total traffic). Set δ small (e.g., 1e-6) so d≈14.- Guard against adversarial keys by using cryptographic hash seeds if needed.- Monitor load: very skewed distributions may need adaptive allocation (more memory for top features).This design gives bounded-memory, mergeable sketches with O(d) per-update/query, additive ε·||f||1 error with probability δ, and straightforward distributed aggregation by summing matrices.
HardTechnical
100 practiced
Design a data structure and implement the algorithm to maintain the median (or k-th quantile) of a sliding window of size k over a stream. The structure must support insert and remove for window updates and return median in O(1) or O(log k) time per update. Describe your approach and complexity.
Sample Answer
Approach (brief): maintain two heaps — max-heap for lower half (lo) and min-heap for upper half (hi) — plus hash maps for lazy deletions to allow arbitrary removes when the sliding window evicts an element. Keep sizes balanced so |len(lo) - len(hi)| ≤ 1. Median is O(1) to read; insert/remove cost O(log k) amortized due to heap pushes/pops and lazy-cleaning.
python
import heapq
from collections import defaultdict
class SlidingMedian:
def __init__(self):
self.lo = [] # max-heap via negatives
self.hi = [] # min-heap
self.del_lo = defaultdict(int) # lazy delete counts for lo
self.del_hi = defaultdict(int) # for hi
self.size_lo = 0
self.size_hi = 0
def _clean_top(self, heap, del_map):
# remove logically deleted elements from heap top
while heap and del_map[heap[0]]:
val = heap[0]
del_map[val] -= 1
if del_map[val] == 0:
del del_map[val]
heapq.heappop(heap)
def _balance(self):
# ensure sizes differ by at most 1
if self.size_lo > self.size_hi + 1:
self._clean_top(self.lo, self.del_lo)
val = -heapq.heappop(self.lo)
self.size_lo -= 1
heapq.heappush(self.hi, val)
self.size_hi += 1
elif self.size_hi > self.size_lo + 1:
self._clean_top(self.hi, self.del_hi)
val = heapq.heappop(self.hi)
self.size_hi -= 1
heapq.heappush(self.lo, -val)
self.size_lo += 1
def insert(self, x):
# push into appropriate heap
if not self.lo or x <= -self.lo[0]:
heapq.heappush(self.lo, -x); self.size_lo += 1
else:
heapq.heappush(self.hi, x); self.size_hi += 1
self._balance()
def remove(self, x):
# lazy-delete x from correct heap
if self.lo and x <= -self.lo[0]:
self.del_lo[-x] += 1
self.size_lo -= 1
# if it's at top, clean immediately
self._clean_top(self.lo, self.del_lo)
else:
self.del_hi[x] += 1
self.size_hi -= 1
self._clean_top(self.hi, self.del_hi)
self._balance()
def median(self):
# clean tops before reading
self._clean_top(self.lo, self.del_lo)
self._clean_top(self.hi, self.del_hi)
if self.size_lo == self.size_hi:
if not self.lo or not self.hi: return None
return (-self.lo[0] + self.hi[0]) / 2.0
elif self.size_lo > self.size_hi:
return float(-self.lo[0])
else:
return float(self.hi[0])
Key points:- Lazy deletions avoid O(k) heap removal; deletions are recorded and purged when that value reaches heap top.- Insert/remove: O(log k) amortized (push/pop). median(): O(1) after any necessary clean (amortized).- Space: O(k).Edge cases: duplicates, all elements equal, evicting element not present (ensure caller only removes existing window element). Alternatives: balanced BST (multiset) for true deletions in O(log k) if language supports (e.g., C++ multiset).
HardSystem Design
91 practiced
Explain complexity and data-structure choices for implementing a publish-subscribe (pub/sub) subscription registry where subscribers match prefixes or attribute filters; discuss how tries, inverted indices, and bloom-filter-based pre-filters help performance and memory usage in high-throughput ML event systems.
Sample Answer
Requirements & constraints:- High-throughput event stream (100k–M events/s), low-match latency (<ms), many subscribers (10k–100k) with prefix or attribute filters, memory bounded, support dynamic subscribe/unsubscribe.High-level approach:- Use a hybrid registry: a trie for prefix/topic matching, inverted indices for attribute filters, and Bloom-filter-based pre-filters to reduce work per event.Core components and data-structures:1. Prefix trie (radix/compressed trie):- Stores topics/prefixes; leaf nodes hold subscriber sets or pointers to subscriber IDs.- Time: O(L) to traverse (L = prefix length in tokens/characters). Memory: compacted by radix/trie compression; sharing common prefixes reduces state for hierarchical topics.- Good for hierarchical topic namespaces used in ML pipelines (e.g., model/serve/<model_id>/pred).2. Inverted index for attribute filters:- For each attribute=value (or range bucket), maintain posting lists of subscriber IDs.- Matching an event translates into intersecting posting lists for attributes present. Use sorted arrays + skip pointers or Roaring bitmaps for fast intersections.- Complexity: reading k postings and intersecting — cost depends on posting sizes; choose ordering by smallest list first.3. Bloom-filter pre-filters:- Per-trie-node or per-shard Bloom filters summarize attributes subscribers on that node.- On event arrival, consult Bloom filters to quickly rule out nodes/subscribers before expensive posting-list intersections.- False positives tolerated (lead to extra work), false negatives avoided.Data flow:- Event → traverse trie to candidate nodes (O(L)) → consult Bloom pre-filter to filter unlikely nodes (O(1) checks) → fetch posting lists for attributes → intersect → notify subscribers.Scalability & optimizations:- Shard registry by topic hash to parallelize, colocate hot prefixes to balance load.- Use Roaring bitmaps for dense subscriber sets: fast bitwise AND, low memory.- Cache recent intersection results for common attribute combinations.- Background compaction and lazy updates for subscription churn.- Use vectorized CPU instructions / GPU for very high-rate bitmap ops in ML infra.Trade-offs:- Tries optimize prefix lookup but add memory; compress to reduce cost.- Inverted index gives flexible attribute matching but can be heavy for high-cardinality attributes — mitigate with hashing/bucketing or bloom pre-filters.- Bloom filters reduce CPU but introduce false positives; tune size/FP rate to workload.Example numbers:- With 100k subscribers and Roaring bitmaps, a posting bitmap ~100k bits (~12.5 KB) per high-cardinality attribute; intersecting 3 attributes is a few memory reads and bit-ANDs — sub-ms.Conclusion:- Combined trie + inverted index + Bloom pre-filters gives a practical balance: fast prefix routing, efficient attribute matching via set operations, and low wasted work using probabilistic filters — suitable for ML event systems needing low latency and high throughput.
MediumTechnical
87 practiced
Write a function in Python to detect a cycle in a directed graph given as adjacency lists. Use depth-first search with coloring or recursion stack method, analyze time/space complexity, and explain how you'd adapt it to detect cycles in extremely large graphs that don't fit in memory (external or streaming algorithms).
Sample Answer
Approach: use DFS with 3-color marking (0=unvisited, 1=visiting, 2=visited). If during DFS we reach a node marked 1, we found a back edge → cycle.
python
def has_cycle(adj):
"""
adj: dict[node] -> list of neighbors
Returns True if directed cycle exists, else False.
"""
WHITE, GREY, BLACK = 0, 1, 2
color = {u: WHITE for u in adj}
def dfs(u):
color[u] = GREY
for v in adj.get(u, []):
if color.get(v, WHITE) == GREY:
return True # back edge -> cycle
if color.get(v, WHITE) == WHITE and dfs(v):
return True
color[u] = BLACK
return False
for node in adj:
if color[node] == WHITE:
if dfs(node):
return True
return False
Key points:- Coloring avoids extra recursion-stack data structures and clearly distinguishes states.- Works for disconnected graphs by iterating all nodes.Complexity:- Time: O(V + E) — each node and edge processed once.- Space: O(V) for color map + O(H) recursion stack (H = max path length).Edge cases:- Nodes with no outgoing edges; isolated nodes; nodes referenced as neighbors but missing in adj keys (use get with default).- Deep recursion may overflow for very deep graphs — iterative DFS or increase recursion limit.Adapting for very large graphs (external/streaming):- Use external memory / graph databases (Neo4j, Bigtable) and run distributed algorithms like Tarjan or parallel DFS variants via Pregel/Giraph or GraphX to process partitions.- For streaming or out-of-core detection, use cycle detection via incremental topological ordering: maintain in-degree for Kahn's algorithm; stream edges and apply external-memory Kahn — if after removing all zero-indegree nodes edges remain, a cycle exists.- Use probabilistic sketches (e.g., hashing-based reachability) for quick heuristics, but they may have false positives/negatives.- Practical approach: partition graph, detect intra-partition cycles locally, track cross-partition edges, and run staged graph trimming (remove zero indegree nodes iteratively) using disk-backed queues; leverage cloud-managed distributed graph processing when scale demands.
EasyTechnical
94 practiced
Explain what a trie (prefix tree) is and when it is preferable to a hash table. Include complexity (time and space) for insert, search, and delete, and discuss memory trade-offs and compression techniques (e.g., radix trees) for large vocabularies used in autocomplete or token indexing in NLP pipelines.
Sample Answer
A trie (prefix tree) is a tree data structure where each edge/child represents a character (or token) and each path from the root spells a prefix. Nodes can mark word/token terminations and store metadata (counts, frequencies, IDs). Tries make prefix queries trivial: enumerating all entries with a given prefix is O(length(prefix) + number_of_results).When preferable to a hash table:- Prefix/predictive queries (autocomplete, longest-prefix match) — tries return all matches by walking once to the prefix node and traversing subtree.- Ordered iteration by lexicographic order.- Avoids need to store full keys for some applications (shared prefixes reduce duplication).Complexities (n = length of key, |Σ| = alphabet size):- Insert: O(n) time, O(n) additional nodes in worst-case; average can be less due to shared prefixes.- Search (exact): O(n) time.- Delete: O(n) time (may require pruning unused nodes).Space:- Worst-case O(total_chars) = O(sum of lengths of all keys), plus per-node overhead (children pointers/map).- Memory overhead can be large for sparse alphabets because each node may hold up to |Σ| pointers.Memory trade-offs and compression:- Use maps/dictionaries at nodes (sparse) vs fixed arrays (fast but high memory).- Store compact pointers (integers, bit-packed) and pool nodes to reduce overhead.- Compression techniques: - Radix tree / compressed trie: collapse single-child chains into a single edge labelled with a string segment — reduces depth and memory, improves cache locality. - LOUDS / succinct tries: bit-level representations for very large vocabularies to minimize memory at cost of more complex access. - Finite State Transducers (FSTs): compact, disk-friendly structures that store outputs (IDs/frequencies) and are used in NLP token indexing and large-scale autocomplete (e.g., Lucene, OpenFST).Practical notes for ML/NLP:- For small-medium vocabularies, a trie with hash maps per node is simple and fast for autocomplete.- For large vocabularies (millions of tokens), prefer radix trees, FSTs, or compressed tries to reduce memory and improve I/O; they also allow storing scores or payloads for ranking suggestions.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
