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.
EasyTechnical
74 practiced
Implement a function to reverse a singly linked list in-place and return the new head. Provide Python code or clear pseudocode. Analyze time and space complexity and consider edge cases: empty list, single node, and very long lists (stack considerations).
Sample Answer
To reverse a singly linked list in-place, iterate through the list and flip each node's next pointer to the previous node. This is O(n) time and O(1) extra space and avoids recursion (so safe for very long lists).
python
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
"""
Reverse a singly linked list in-place.
Returns new head (formerly tail).
"""
prev = None
curr = head
while curr:
nxt = curr.next # save next
curr.next = prev # reverse pointer
prev = curr # move prev forward
curr = nxt # move curr forward
return prev # new head
Key points:- Iterative approach avoids recursion depth limits for very long lists.- Works for empty list (head is None -> returns None) and single-node list (returns same node).Time Complexity: O(n) — one pass through n nodes.Space Complexity: O(1) extra — only a few pointers.Edge cases: empty list, single node, lists with cycles (function will loop indefinitely if cycle exists — detect cycle beforehand if needed).
HardTechnical
71 practiced
Design a streaming service that maintains the top-k scoring items over a sliding time window (e.g., last 24 hours). Items can receive score updates and expire when older than the window. Propose data structures/algorithms for efficient updates, top-k retrieval, and expirations at scale. Discuss memory complexity, update/query time, and how to shard across machines.
Sample Answer
Requirements & constraints:- Maintain top-k items by score over a sliding window (e.g., 24h).- Frequent score updates (increments/decrements), items expire after window.- Need low-latency updates & queries at large scale; can be exact or approximate.High-level approach:- Shard items by item_id hash across worker nodes. Each shard maintains its local state (per-item score for the window) and a local top-k. Global top-k is computed by merging shard results periodically or on-demand.Per-shard data structures & algorithms (exact):1. Time-bucketed deltas: - Break window into B fixed buckets (e.g., 144 buckets of 10 min or 1440 of 1 min depending on accuracy/throughput). - Each bucket holds a hashmap: item_id -> delta_score received during that bucket. - Also maintain a per-item running_total map: item_id -> total_score_in_window.2. Top-k maintenance: - A min-heap of size k (heap node references include item_id and pointer to running_total). Also keep an index map item_id -> heap node (or position). - On update: write delta into current bucket's map (O(1) amortized). Update running_total[item] += delta. If item is in heap, adjust its key and sift (O(log k)). If not and running_total > heap.min, pop heap.min and insert new item (O(log k)).3. Expiration: - When a bucket expires (time advance), iterate its hashmap entries and for each item subtract that bucket's delta from running_total. If running_total becomes ≤0 remove from maps and heap; if decreased and item is in heap, sift-down/up (O(#unique_in_bucket * log k) per bucket expiry). To avoid spikes, spread bucket size to amortize cost.Complexity (per shard):- Memory: O(U + B * U_b) where U = number of active unique items in window, U_b = average unique items per bucket. With small buckets U_b << U. Top-k heap: O(k).- Update time: write to bucket O(1); heap update O(log k) only when running_total crosses into top-k or item already in heap.- Expiration cost: amortized O(U_b * log k) per bucket interval.Scaling & global top-k:- Each shard independently maintains local top-(k+m) (m slack to avoid misses). A central aggregator pulls local lists periodically (or subscribes) and merges them using a min-heap of size k: O(S * (k+m) log k) where S = #shards. For lower latency, use push-based updates when local top changes.- To reduce network: only send deltas for items that changed and are in local top-(k+m).Approximate variants (lower memory):- Space-Saving (lossy counting/heavy-hitters) or Count-Min Sketch + top-k estimator per shard: much smaller memory, probabilistic error bounds.- Use Sliding-window variants: exponential decay or bucketed CMS.Operational concerns:- Use a distributed stream processor (Kafka + Flink/Beam/Samza). Worker state stored in embedded state store with checkpointing for fault tolerance.- Clock/watermark handling for late updates: buffer or apply with timestamps; assign to appropriate bucket by event time, with allowed lateness.- Rebalancing: when shards move, transfer item state for affected key ranges (hash-range or consistent-hash based transfer).- Hot keys: heavy items may concentrate; further shard hot key by sub-hashing or keep a dedicated shard.Trade-offs:- More buckets -> finer expiry accuracy but higher memory and more bucket maps; larger buckets -> less CPU on expiry but coarser window semantics.- Exact top-k: more memory & CPU but precise. Approximate: much cheaper at scale with bounded error.- k small -> cheap heap ops; very large k may need different datastore (sorted sets in Redis, or secondary index).This design provides O(1) amortized updates to bucketed state, O(log k) for top-k maintenance, controlled expiration cost, and a straightforward sharding strategy that composes to global top-k with merge.
HardTechnical
94 practiced
You maintain a tokenizer implemented using a trie for longest-prefix matching on CPU, but you must port it to GPU for faster tokenization or batched tokenization. Propose data structures or hybrid approaches that provide fast longest-prefix lookup, compact memory footprint, and efficient serialization to GPU memory. Compare double-array trie, radix tree, perfect hash with fallback, and finite-state transducers (FST); analyze lookup complexity and memory trade-offs.
Sample Answer
Situation: You need longest-prefix tokenization (LPM) moved from CPU trie to GPU for throughput and batched tokenization while keeping memory small and fast lookups.Proposal (hybrid approaches):- Chunked double-array trie (DAT) on GPU: serialize base/check arrays (compact, cache-friendly), split into shards per GPU thread block to maximize coalesced reads. Use 16/32-bit indices for vocabularies <65k to reduce footprint. Fallback small local probe (radix) for collisions.- Radix tree (compact prefix tree with path compression): store edges as (label, start, length) and a contiguous suffix buffer. Good for variable-length UTF-8 tokens; fewer nodes than classic trie, but pointer-heavy—serialize as flat arrays (edge-array, child-index). Use GPU threads to compare whole labels via 64-bit loads.- Perfect hash + fallback: minimal perfect hash (MPH) for full tokens (not prefixes) provides O(1) exact matches and tiny memory. For LPM, combine MPH with a small prefix Bloom/FP-trie to detect candidate prefix lengths, then verify via suffix buffer. This minimizes memory and supports SIMD lookup.- Finite-State Transducer (FST): compresses common suffixes; stores transitions as sorted arcs with binary-searchable offsets; excellent compression and can store outputs (token ids). Lookup is O(L log σ) or O(L) with direct-mapped transition tables; very GPU-serializable as flat arrays and perfect for large vocab.Lookup complexity & memory trade-offs:- Double-Array Trie: Lookup O(L) with few memory accesses per char; very fast, array-only (good for GPU coalescing). Memory: moderate; base/check arrays can be sparse but compact compared to pointers. Harder to modify.- Radix Tree: Lookup O(k) where k = number of edges (often << L due to compression). Memory smaller than pointer tries but needs label storage. Serialization needs label buffer + index arrays.- Perfect Hash + Fallback: Exact token lookup O(1); LPM requires checking multiple suffixes — amortized small if you probe decreasing lengths via MPH plus Bloom filter to avoid misses. Very compact for large static vocabs.- FST: Lookup O(L) with fewer states/arcs; best compression (can be 5–10x smaller). Slightly higher CPU/GPU branching due to binary searches or variable arc counts. Excellent for static vocab and stores outputs compactly.GPU serialization tips:- Flatten all structures: arrays of uint32/16 and contiguous label/suffix buffers.- Align and pack to 64-bit words for coalesced loads; prefer 32/64-bit indices.- Precompute per-token maximum match length and per-block offsets to reduce divergence.- Use warp-level parallelism: each thread processes a start position; use warp-synchronous scan to perform longest-prefix longest-match efficiently.- Provide a tiny on-GPU fallback SSA for very long tokens or dynamic updates (keep dynamic parts on CPU).Recommendation:- For static, large vocab with max compression -> FST.- For extremely low-latency per-char matching and GPU-friendly array accesses -> double-array trie (with 16/32-bit indices).- For minimal memory with mostly whole-token matches -> MPH + small prefix-trie fallback.- Radix tree sits between DAT and FST: good when tokens have long shared labels (UTF-8), implement as flat label buffer + edge index.This hybridizes MPH for whole-token fast-path, DAT or FST for LPM core, and radix compressed labels for reducing node count; all serialized as flat arrays for efficient GPU transfer and coalesced access.
MediumTechnical
94 practiced
Implement topological sort for a directed acyclic graph using Kahn's algorithm (BFS) and provide the DFS-based algorithm as well. Provide code or pseudocode, analyze complexity, explain how you detect cycles (i.e., when topological ordering is impossible), and discuss use-cases in ML pipelines (scheduling the order of data transforms).
Sample Answer
To compute a topological ordering of a DAG you can use Kahn’s algorithm (BFS using in-degrees) or a DFS postorder approach. Both detect cycles when the ordering cannot include all nodes.Kahn’s algorithm (BFS):- Compute in-degree for each node.- Start with all nodes with in-degree 0 in a queue.- Repeatedly pop, append to order, decrement neighbors’ in-degree and enqueue those that drop to 0.- If resulting order contains all nodes → success; otherwise a cycle exists.
python
from collections import deque, defaultdict
def topo_kahn(nodes, edges):
# nodes: iterable of node ids
# edges: iterable of (u,v) directed edges u->v
g = defaultdict(list)
indeg = {n:0 for n in nodes}
for u,v in edges:
g[u].append(v)
indeg[v] += 1
q = deque([n for n,d in indeg.items() if d==0])
order = []
while q:
u = q.popleft()
order.append(u)
for v in g[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if len(order) != len(nodes):
raise ValueError("Graph has a cycle")
return order
DFS-based algorithm:- Do DFS, track visited and recursion stack.- On finishing a node (postorder), push it onto a stack/list.- Reverse the list to get topological order.- If during DFS you revisit a node on the current recursion stack → cycle.
python
def topo_dfs(nodes, edges):
g = defaultdict(list)
for u,v in edges:
g[u].append(v)
visited = set()
onstack = set()
order = []
def dfs(u):
if u in onstack:
return False # cycle
if u in visited:
return True
visited.add(u)
onstack.add(u)
for v in g[u]:
if not dfs(v):
return False
onstack.remove(u)
order.append(u) # postorder
return True
for n in nodes:
if n not in visited:
if not dfs(n):
raise ValueError("Graph has a cycle")
return order[::-1]
Complexity:- Time: O(V + E) for both algorithms.- Space: O(V + E) to store graph; plus O(V) auxiliary (queue/stack/recursion).Cycle detection:- Kahn: if the output order length < V → cycle.- DFS: encounter a back-edge to a node currently in recursion stack → cycle.Edge cases:- Disconnected graph: both handle it by processing all nodes.- Nodes with no outgoing/incoming edges included explicitly.Use-cases in ML pipelines:- Represent transforms/steps as nodes and dependencies (data or artifact producers) as edges.- Topological order schedules data preprocessing, feature engineering, model training, and validation so producers run before consumers.- Kahn is good for building execution plans and supports incremental scheduling and parallelism: all in-degree-0 nodes can run concurrently.- DFS is simple for static DAGs and for detecting cyclic dependency bugs in pipeline definitions (e.g., two transforms depending on each other).- Combine with resource constraints to form task scheduling (priority queues, worker pools) for real-world pipeline orchestration.
MediumSystem Design
69 practiced
Design an in-memory dataset index for training deep learning models that must support: (1) random access by sample index, (2) efficient minibatch sampling (random and stratified), (3) fast epoch shuffling, and (4) low CPU overhead to avoid GPU starvation. Describe data structures, memory layout (contiguous arrays, mmap, metadata), sharding, and trade-offs when the dataset is hundreds of GB and cannot fully fit into RAM.
Sample Answer
Requirements & constraints:- Random O(1) access by global sample index- Fast minibatch sampling (uniform random + stratified)- Efficient epoch shuffling- Low CPU overhead to keep GPUs fed- Dataset size hundreds of GB (may not fit in RAM)High-level design:- Store raw tensors on disk as contiguous blobs and memory-map them; keep compact in-RAM metadata and index arrays for addresses/offsets and labels.- Metadata layout (in RAM): contiguous arrays (numpy/torch tensors) of sample offsets, lengths (if variable), labels/classes, and a per-sample shard id. These arrays are small (O(num_samples) integers) and fit in RAM.- On-disk: shard files (e.g., per-100k samples) storing serialized fixed-size records or concatenated compressed tensors. Use mmap-able files (POSIX mmap or torch.memmap) so reads are zero-copy when possible.Data structures & sampling:- Global index array: int32 array [0..N-1] mapping logical sample id -> (shard_id, offset). O(1) random access.- Class buckets: for stratified sampling keep per-class index lists as contiguous int arrays; sampling a stratified minibatch selects required counts from these arrays.- Shuffling: maintain a permutation array (int32) for epoch order; to shuffle an epoch, just permute that array (Fisher–Yates or numpy.random.permutation) — very cheap compared to data movement.- Minibatch formation: fetch K indices from the permuted array or class buckets; group by shard_id to issue batched read requests to minimize syscalls.Sharding & IO optimization:- Shard dataset into many moderately-sized files (~100MB–2GB) to trade off mmap granularity and IO locality.- When sampling, coalesce reads per shard and use async prefetch worker threads/processes to load batches into a pinned-memory batch cache (CPU pinned -> faster CPU->GPU memcpy).- For distributed training, shard round-robin across workers; maintain local index subset per worker to reduce cross-node IO.Memory & CPU trade-offs when dataset >RAM:- Keep only metadata and index arrays in RAM; rely on OS page cache + mmap for data. If OS cache misses, latency rises.- Optionally maintain a small LRU in-memory cache of hot shards or recent batches (size tuned) to lower latency at cost of RAM.- Use compression on disk to reduce IO at cost of CPU decompress — balance: use lightweight compression (LZ4) or hardware-accelerated decompression, or store pre-extracted fixed-size tensors for zero-decode.- If CPU decompression is a bottleneck, offload to dedicated IO workers or use GPU decompression kernels.Concurrency & GPU starvation mitigation:- Use a pool of worker processes performing mmap reads + optional decompression into pinned memory; main training process consumes ready batches from a lock-free queue.- Pre-fetch multiple batches ahead (configurable prefetch depth) and maintain batch readiness stats; adapt worker count to keep GPU utilization high.- Minimize Python GIL contention by doing IO and decoding in separate processes (multiprocessing) and using shared memory for batch buffers.Trade-offs:- Larger shard size improves compression and sequential IO but increases memory waste and latency for random reads.- Keeping more cached data reduces IO & latency but increases RAM footprint.- Compression saves storage/IO but consumes CPU; use lightweight codecs or hardware acceleration if CPU-bound.- Full in-RAM dataset yields best performance but is often infeasible; mmap + smart prefetch + pinned-memory pipeline is practical compromise.Example flow:1. At init load index arrays and per-class buckets.2. Build epoch permutation or stratified selection.3. Worker processes read needed shards via mmap, decode into pinned buffers, push batches to queue.4. Trainer pops ready batches with minimal CPU per-batch orchestration.This design gives O(1) random access, efficient stratified/uniform minibatch sampling, cheap epoch shuffling (permute int array), and low CPU overhead via async IO, pinned-memory, and careful trade-offs between caching/compression and RAM usage.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
