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.
HardSystem Design
150 practiced
Design a lock manager for distributed transactions in a multi-shard data system. Describe how you would implement locking primitives, detect deadlocks (for example using a wait-for graph), and analyze the complexity of deadlock detection and resolution. Discuss scalability considerations and how to avoid global coordination where possible.
Sample Answer
Requirements & constraints:- Support distributed transactions spanning multiple shards; low-latency lock acquisition; avoid single global coordinator; detect and resolve deadlocks correctly; scale to many shards and concurrent transactions.High-level architecture:- Partitioned Lock Managers (PLMs): one lock manager process per shard (co-located with data node). Each PLM manages locks for keys/partitions it owns.- Transaction Coordinator (TC): per-transaction ephemeral coordinator that orchestrates lock acquisition across relevant PLMs.- Lease-based locks with versions: locks granted with short leases to bound failure detection; optional renewal.Locking primitives:- AcquireShared(key, txnID, intentID) and AcquireExclusive(key, txnID, intentID) implemented at owning PLM.- PLM maintains lock table entries: holder set, wait-queue (ordered by arrival/timestamp), and wait-for edges (local view).- Use two-phase locking (2PL) semantics: acquire before use, release at commit/abort.Deadlock detection:- Local detection: PLM builds local wait-for edges for transactions that both hold and wait on local resources.- Distributed detection via edge-chasing (Chandy-Misra-Haas probe): when txn A at PLM1 waits for B at PLM2, PLM1 sends a probe (A→B) to PLM2; probes propagate along waits to detect cycles when a probe returns to origin.- Optimization: run proactive local detector periodically and only invoke distributed probe when local edges cross partitions.- Alternative policy: timestamp ordering with wound-wait or wait-die to avoid many cycles (preemptive deadlock avoidance).Deadlock resolution:- On cycle detection, select victim by policy: abort youngest or largest rollback cost; prefer aborting transactions that hold few locks (minimal work lost) or ones with low priority.- Use TC to notify all PLMs to release locks and clean up; use exponential backoff before retry.Complexity analysis:- Local detection: building local wait-for graph O(n_local + e_local) where n_local transactions and e_local edges.- Distributed probe (edge-chasing): message complexity O(E_cycle) per detection where E_cycle is number of cross-shard wait-for edges in the cycle; worst-case O(N+E) across system if many probes run, but probes are targeted.- Periodic global scan (if used): O(total_txns + total_edges), expensive—avoid at scale.- Space: lock tables store O(L) entries where L is number of distinct locked keys.Scalability & avoiding global coordination:- Partition lock state by ownership; most waits and detections stay local.- Use consistent hashing or data locality to minimize cross-shard transactions (application design / transaction routing).- Prefer optimistic concurrency for read-heavy workloads (MVCC) to reduce locking.- Use hierarchical locking: coarse-grained locks for coordination, fine-grained for contention hotspots.- Use lease timeouts and txn heartbeat to detect failures without global consensus.- Apply conservative techniques (wound-wait) to reduce need for distributed detection.Example flow:1. TC requests exclusive lock on k1 at PLM1, granted.2. TC then requests exclusive k2 at PLM2; if k2 held by txn B that waits on k1 at PLM1, PLM2 sends probe to PLM1 (B→A).3. Probe finds A waiting on B → cycle detected → choose victim (abort younger), notify PLMs to release locks; TC aborts and retries with backoff.Trade-offs:- Proactive avoidance (timestamp) reduces detection cost but increases aborts.- Edge-chasing minimizes global state but has message overhead on cross-shard contention.- Periodic global detection is simplest but not scalable.This design balances correctness and scalability by localizing lock state, using targeted distributed detection (probe edge-chasing), preemptive deadlock avoidance policies to reduce cycles, and pragmatic resolution rules to minimize wasted work.
HardSystem Design
75 practiced
You are designing a memory-efficient radix tree (compressed trie) to store 50 million short strings (avg length 16) under a 64 GB memory limit. Propose a node layout (fields and types), explain how to pack data to reduce overhead per node, describe how to handle variable-length edges, and discuss lookup time and memory trade-offs.
Sample Answer
Requirements & constraints- Store 50M short strings (avg length 16) within 64 GB RAM. That gives ~1.28 KB budget per string overall, but we must minimize per-node overhead because tries can create many nodes if naively represented.- Goal: memory-efficient compressed trie (radix tree) with fast lookup (near O(length)) and good cache locality.Node layout (compact, fixed-size header + variable-length edge data in pools)- Node header (packed, 16 bytes typical): - uint32 children_index_or_bitmap_offset (4 bytes) — index into child-structures pool or offset to child-bitmap - uint32 edge_data_offset (4 bytes) — offset into a shared edge-char pool - uint16 edge_length (2 bytes) — length of the edge label - uint8 flags (1 byte) — bits: is_terminal, has_payload, child_representation_type(2 bits), reserved - uint8 child_count_or_bitmap_len (1 byte) — number of children or bitmap length code - uint32 payload_index (4 bytes) — index into payload/values pool (0 = none) [can be reused as union with other fields]- Child representation (two mutually exclusive forms to save space): 1. Dense small-alphabet: bitmap + contiguous child indices - Child bitmap stored in pool: for ASCII subset use 32-bit or 64-bit masks; for general bytes use variable-length bitmaps (e.g., 16 or 32 bytes). Child pointers stored as contiguous uint32 indices (4 bytes each). 2. Sorted sibling array: for low-degree nodes, store sorted list of (byte, child_index) pairs in the child pool, encoded as pairs of (uint8, varint32).- Edge labels are variable-length strings stored in one or more shared read-only pools (concatenated UTF-8 or bytes). Store offset+length in node header. Pools packed back-to-back to reduce per-edge header overhead. Use a separate pool for frequently occurring short labels to improve locality.Packing strategies to reduce overhead- Use indices (32-bit) instead of 64-bit pointers to address pools and nodes (fits within 4B if node/edge pools < 4GB; use 40-bit if needed). This saves half the pointer cost.- Align node header to 8 bytes but keep it small (~12–20 bytes). Use unions to reuse fields (e.g., payload_index reused for child base index when child_count>0).- Use varint encoding for child indices in sparse arrays; delta-encode indices in monotonic arrays.- Use bitfields (uint8 flags) to avoid separate booleans.- Store payloads separately in a packed value pool; nodes hold payload_index. If values are small (e.g., 32-bit IDs), store inline as varints only for terminal nodes.- Deduplicate edge strings using content-addressable pool (hash-consing) or front-coding for many similar prefixes.Handling variable-length edges (radix compression)- On insertion/build: compress chains of single-child nodes into one edge string (standard radix tree). Store label in edge pool and set edge_length/offset.- When splitting (during updates), create new short label entries and place them in the pool; reuse freed slots via a free list to avoid fragmentation.- For extreme memory pressure, use front-coding for groups of edges from the same parent: store a shared common prefix and then suffixes with lengths—saves space when many edges share prefixes.- Keep edge pool as contiguous byte arrays with a separate small metadata table (offset->length). To avoid expensive per-edge metadata, store length in node header and only keep offset in node.Lookup algorithm and complexity- Lookup follows nodes consuming entire edge labels at each step: at node, compare edge label with substring of key (memcmp). If fully matches, advance; if partial match, fail. If node is terminal, check payload.- Time complexity: O(m) where m = length of key in bytes, with small constant due to edge-label comparisons. In practice fewer node hops than a char-by-char trie because edges are compressed.- Use memcmp against packed edge pool to exploit vectorized comparisons; short edges are common so comparisons are fast and cache-friendly.Memory vs performance trade-offs- Indexes (32-bit) vs pointers (64-bit): indices reduce memory but add base-address arithmetic. Prefer indices when total memory < 4GB per pool.- Child representation: bitmap + array gives O(1) child lookup (bit-test + index) but higher memory per node; sibling arrays are very compact for low-degree nodes but require binary search (log k) or linear scan (k small). Use hybrid: switch representation based on degree threshold (e.g., <=4 use array, >4 use bitmap).- Pre-computing hash for child lookup speeds variable-arity nodes but increases memory.- Storing payloads inline reduces pointer indirections at cost of larger nodes; external payload pool keeps node size down and improves sharing.- Cache locality: pack nodes densely by level or by subtree to reduce cache misses. A flat memory pool and node indices help locality over scattered heap allocations.Capacity estimate & target per-node budget- If avg string length 16 and heavy compression reduces total distinct edges/nodes significantly, aim for average ~20 bytes/node header + average edge bytes (shared across nodes). With pointer/index compression and pooling, practical implementations achieve ~200–800 bytes per stored string equivalent depending on redundancy. Fine-tune via profiling: measure average node count and adjust representation thresholds.Operational considerations- Build offline with bulk insertion and compaction (merge identical edges, front-code). For dynamic workloads, use batched updates + background compaction to keep structure compact.- Expose read-only snapshot for queries (memory-mapped edge pools) and apply incremental mutable layers for writes (L0 memtable + periodic compaction into read-only trie).- Monitor memory usage per pool; expose metrics to tune thresholds (bitmap size, index width).This design balances compactness (small headers, pooled edges, varint indices, compressed edges) with predictable lookup performance (few memcmp operations). Tune the child-representation threshold and index width according to measured node degrees and total pool sizes to fit under 64 GB.
MediumTechnical
86 practiced
Design a system to track approximate distinct counts (unique users) per day across 1000+ partitions using limited memory. Compare HyperLogLog and exact counting alternatives, explain error bounds, memory trade-offs, how to merge sketches across partitions, and the complexity implications for real-time dashboards.
Sample Answer
Approach summary:- Use HyperLogLog (HLL) sketches per partition/day to estimate unique users with tiny memory; fall back to exact counting (hash sets) only for small partitions or auditing.Why HLL:- Memory-efficient probabilistic cardinality estimator based on max leading-zero counts of hashed values.- Typical error: ~1.04 / sqrt(m) where m = 2^p (p = precision bits). Example: p=14 (m=16384) → ≈0.81% relative error.- Fixed small footprint: e.g., p=14 → ~16 KB per sketch (implementation-dependent, some use 6–12 KB compressed).Memory trade-offs:- Increase p → lower error, linear increase in memory. Choose p to meet SLO (e.g., ≤1% error across 1000+ partitions).- For 1000 partitions × 16 KB ≈ 16 MB per day — very modest.- Exact counting: stores one hash per distinct user → O(U) memory, infeasible at high cardinality.Merging sketches:- HLL is mergeable: element-wise max of registers (or canonical merge operation). Merge complexity O(m) per merge. To get per-day global counts, merge all partition sketches for that day.- For hierarchical aggregation (shards → region → day), merge intermediate sketches to avoid large all-to-one merges.Error bounds and cold-start:- Error is unbiased with known standard error; union/merge preserves estimator properties but variance does not worsen beyond theoretical formula.- For small cardinalities (<~5m where m is small), HLL bias correction or switching to exact counting gives better accuracy.Real-time dashboard implications:- Ingest: update partition-local HLL sketches in streaming (per-event hash + register update) — O(1) per event.- Query: dashboard can show per-partition or merged-day estimates. Merging on read (merge ~1000 sketches) is O(m * partitions) — e.g., 16384*1000 ops — feasible but can add latency.- Optimizations: - Pre-aggregate merges on a rolling basis (hourly intermediate merges). - Cache merged daily sketches; maintain incremental merges for new partitions. - Use compressed HLL representations and parallel merges.- Exact counts for dashboard: expensive to compute and store; use for SLAs/audits only.Recommendations:- Choose p based on acceptable error (p=12–16 common). Maintain per-partition HLLs, perform scheduled merges for dashboards, keep selective exact counts for small/high-priority partitions or cold starts, and expose error bounds on dashboard.
HardTechnical
81 practiced
You must compute strongly connected components (SCCs) in a very large directed graph stored across multiple machines. Compare algorithms (Tarjan, Kosaraju) for single-machine use and outline a distributed approach (for example Pregel/Bulk Synchronous Parallel) for SCC detection. Discuss data representation, communication cost, and complexity.
Sample Answer
Clarify requirements & constraints:- Graph is very large (doesn't fit on one machine), directed, need SCCs exactly (not approximate), minimize network I/O and memory per worker, tolerate failures.Single-machine comparison (Tarjan vs Kosaraju):- Tarjan: single DFS pass, O(V+E) time, O(V) stack, finds SCCs in one traversal — faster and memory-efficient on a single machine; sensitive to recursion depth (can be made iterative).- Kosaraju: two passes (DFS on original to get finish order, reverse graph DFS by order), also O(V+E) time but requires materializing reverse graph or expensive edge-direction access; conceptually simpler and easier to parallelize parts but doubles I/O/edge-access cost.- For large single-machine in-memory graphs prefer Tarjan for lower I/O; if reverse graph already available or streaming edges twice is cheap, Kosaraju is fine.Distributed approach (Pregel / BSP style) — high level:- Use label-propagation style algorithm adapted for SCC (e.g., two-phase reachability / forward-backward reach): 1. Choose a pivot vertex (or batch of pivots per superstep). 2. Run forward BFS from pivot to mark reachable set R_f (Pregel messages propagate “forward”). 3. Run backward BFS on reversed edges to get R_b (propagate on reversed adjacency stored or via separate stage). 4. SCC = intersection R_f ∩ R_b; remove its vertices and repeat on remaining graph (can process many pivots in parallel to amortize cost).- Alternative fully-distributed algorithm: Kosaraju-style in BSP using partitioned reverse graph or use distributed Tarjan variants (hard to do due to DFS dependency).Data representation:- Partition vertices across workers; store each vertex’s outgoing adjacency list locally; to support backward BFS either: - store incoming adjacency lists too (duplicate edges, doubles storage), or - maintain a separate reversed-edge partition or materialize reverse edges on demand (costly).- Vertex state: id, current label/visited flag, active flag; use bitsets to represent reachability sets for many pivots to compress messages.Communication cost and complexity:- Each BFS (forward or backward) requires one superstep per hop; total messages ~ O(#edges_queried) per BFS. For full Kosaraju-like method across k pivots: O(k*(V+E)/P) messages roughly, P = #workers.- Worst-case complexity: could approach O(V*(V+E)) if pivots are poorly chosen and SCCs are tiny — practical algorithms choose many pivots or probabilistic seeds to reduce iterations.- Memory: storing reverse edges doubles edge storage; storing bitsets for many pivots increases per-vertex memory but reduces repeated traversals.Practical optimizations & trade-offs:- Process batches of pivots concurrently to amortize traversal cost; compress messages with delta-encoding / bloom filters or bit-packed vectors.- Use heuristics to pick high-degree pivots to peel large components early.- Use GraphX/Giraph/GraphFrames implementations: GraphX supports Pregel API and can do iterative label propagation; Giraph and Apache Flink Gelly implement BSP directly.- Fault tolerance: leverage platform checkpointing between supersteps; design to recompute only active partitions.- If exact SCCs are too expensive, consider approximate SCC or community-detection techniques for downstream use-cases.Recommendation for Data Engineer:- If exact SCCs are critical, implement BSP forward-backward (pivot-batching) with stored incoming edges and bitset batching; run on Spark GraphX or Giraph, monitor network I/O and memory, tune pivot batch size and partitioning.- If storage cost for reverse edges is prohibitive, precompute reversed partitions offline (ETL) as part of pipeline so runtime traversals are efficient.
EasyTechnical
88 practiced
Compare adjacency list and adjacency matrix graph representations. For a graph with n vertices and m edges, give space and time complexity for common operations (iterate neighbors, check edge existence). For a directed web-graph with n=100M and m=10B, which representation would you choose and why?
Sample Answer
Definition: adjacency matrix stores an n×n boolean/weight table A where A[u][v] is set if edge (u→v) exists. Adjacency list stores for each vertex v a list (or set) of its outgoing neighbors.Complexity (n vertices, m edges):- Space: - Matrix: O(n^2) entries (can be n^2 bits if packed, or n^2 bytes/words otherwise). - List: O(n + m) (n for head pointers + m for edge entries).- Iterate neighbors of v: - Matrix: O(n) (scan row v). - List: O(deg(v)) (optimal).- Check edge (u,v) existence: - Matrix: O(1) (direct index). - List: O(deg(u)) if using an array/list; O(1) average if neighbors stored in a hash set; O(log deg(u)) if sorted + binary search.Practical numbers for web-graph (n=100M, m=10B):- Matrix space (bits): n^2 = 1e16 bits ≈ 1.25×10^15 bytes ≈ 1.25 PB — impractical.- Adjacency list space (raw 64-bit IDs): m × 8B = 80 GB; with per-edge overhead and indexing expect a few ×100 GB—feasible across cluster and compressible (CSR, delta/VByte compression, run-length, or WebGraph techniques), and supports distributed processing.Recommendation: Choose adjacency list (compressed/CSR) stored across a cluster. Reasons: vastly smaller storage, iteration over neighbors is efficient for typical graph algorithms (BFS, PageRank), allows streaming/partitioning and compression, and common graph-processing systems (Spark GraphX, Pregel-style engines) assume list-like representations. Use adjacency-matrix only for small/dense graphs or algorithms needing constant-time edge checks on small n.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
