Skill in selecting appropriate data structures and algorithmic approaches for practical problems and performance constraints. Candidates should demonstrate how to choose between arrays lists maps sets trees heaps and specialized structures based on access patterns memory and CPU requirements and concurrency considerations. Coverage includes case based selection for domain specific systems such as games inventory or spatial indexing where structures like quadtrees or spatial hashing are appropriate, and language specific considerations such as value versus reference types or object pooling. Emphasis is on explaining rationale trade offs and expected performance implications in concrete scenarios.
HardSystem Design
67 practiced
Build an autocomplete backend that must serve millisecond-latency suggestions for 100k terms with ranking. Compare compressed trie/radix tree, finite-state transducer (FST), inverted index, and prefix precomputation. Discuss memory footprint, on-disk compactness, update cost, and how to serve queries from multiple machines in a distributed setup.
Sample Answer
**Clarify requirements / constraints**- 100k terms, need millisecond read latency, ranked suggestions, low memory on servers, frequent reads, occasional writes/updates, multi-machine serving.**High-level options (summary)**- Compressed trie / Radix tree - Memory: moderate (nodes merged) — O(total chars) but pointer overhead matters in RAM. - On-disk: straightforward to serialize. - Update cost: cheap incremental inserts/deletes. - Ranking: store score at terminal nodes and maintain top-k children caches. - Good when you need online updates.- Finite-State Transducer (FST) - Memory: very compact in RAM due to shared suffixes/prefixes; best for static datasets. - On-disk: extremely compact; can memory-map file. - Update cost: expensive (usually full or batched rebuild). - Ranking: store output weights; supports deterministic top-k traversal. - Best for read-heavy, mostly-static autocomplete.- Inverted index (term -> postings of prefixes/ngrams) - Memory: larger; stores many prefix entries or n-grams. - On-disk: OK with compression; seeks needed. - Update cost: moderate (append and merge segments like Lucene). - Ranking: natural (score & boost), supports fuzzy/autocorrect well. - Good when you need fuzzy matching, scoring, analytics.- Prefix precomputation (precompute top-k per prefix) - Memory: highest (store top-k per prefix); for 100k terms with avg 10 chars and k=10 might explode. - On-disk: large but fast to serve. - Update cost: expensive (must update many prefix entries). - Latency: optimal (O(1) read).**Recommendation for this role**- Use an FST for the primary in-memory serving layer to achieve millisecond latency and small footprint; back it with a fast secondary write path (radix tree or inverted index) for incremental updates.- Workflow: accept writes -> append to write-ahead store -> apply to an in-memory mutable radix tree used for newest items -> periodically rebuild FST offline (or do incremental compaction) and swap atomically.**Distributed serving**- Sharding: shard by prefix hash (first N chars) or consistent hashing on term buckets so each node holds disjoint prefix ranges; ensures lookup hits single node.- Replication: 2-3 replicas per shard for availability; use leader for updates to coordinate rebuilds.- Consistency: serve reads from replicas; writes go to leader, update WAL and mutable tree, then async propagate.- Cache: edge caches (CDN or app-level LRU) for very hot prefixes; local precomputed top-k for top prefixes.- Deployment: memory-map FST files on each replica for zero-copy cold start; use rolling swaps for FST updates to avoid downtime.**Trade-offs**- FST: best read density and compactness, poor update agility.- Radix: good updates, slightly larger RAM.- Inverted index: flexible scoring & fuzzy features, heavier memory.- Precompute: lowest latency, highest memory and update cost.**Operational notes**- Monitor QPS per prefix, evict/migrate hot shards.- Bench: measure P95 latency under realistic workloads; tune shard-sizing and cache TTL.
MediumTechnical
74 practiced
You must maintain a dynamic top-k list where elements are frequently updated and arbitrary elements may be deleted. Compare using a binary heap (priority queue), a balanced BST (e.g., TreeSet), and an indexed skip list. Discuss operation complexity for insert, arbitrary delete, update-key, memory overhead, and practical implementation concerns.
Sample Answer
**Overview & goal**We need a data structure that supports frequent inserts, arbitrary deletions, and key updates while efficiently retrieving top‑k. I'll compare binary heap, balanced BST (TreeSet), and indexed skip list across operations, memory, and practical concerns for a full‑stack developer.**Binary heap (priority queue)**- Insert: O(log n)- Arbitrary delete: O(n) unless you store index map → O(log n) for delete with map- Update-key: O(log n) if index map present (decrease/increase then sift)- Memory: O(n) + O(n) for index map (extra array/hash)- Practical: Simple, fast constants, ideal when deletes/updates are rare or you maintain index map (must update map on swaps). Not stable for order ties unless augmented.**Balanced BST (TreeSet / TreeMap)**- Insert: O(log n)- Arbitrary delete: O(log n)- Update-key: O(log n) (delete + insert or tree supports key-change with rebalancing)- Memory: O(n) with per-node pointers and parent/color bits (higher overhead than heap)- Practical: Good when you need ordered iteration, find top-k by walking from max; supports duplicates via multiset or storing (key, id). Simpler correctness for deletions than heap + map.**Indexed skip list**- Insert: O(log n) expected- Arbitrary delete: O(log n) expected- Update-key: O(log n) expected- Memory: O(n) with extra level pointers (configurable)- Practical: Easier to implement lock‑free or concurrent versions, predictable average behavior, less rigid invariants than balanced trees. Good compromise if you prefer probabilistic structure and want index/rank operations.**Recommendation for full‑stack use**- If top‑k queries are frequent and updates/deletes are common: use balanced BST or indexed skip list for deterministic O(log n).- If performance and low memory constant matter and you can maintain an index map reliably: heap + index map is fast.- Consider using existing libraries (TreeMap/multiset) or a database sorted-set (Redis ZSET) for persistence and concurrency instead of hand-rolling.
MediumTechnical
70 practiced
You must implement graph algorithms on graphs up to 10 million nodes with average degree 3 (sparse). Compare adjacency list, adjacency matrix, edge list, and compressed sparse row (CSR) representations for memory, traversal speed for BFS and Dijkstra, and how to support dynamic edge updates efficiently.
Sample Answer
**Short framing (role view)** As a full‑stack developer implementing large sparse graphs (10M nodes, avg degree 3), focus on memory-efficiency, traversal throughput (BFS, Dijkstra), and feasible dynamic updates for backend services (APIs, in‑memory caches).**Representation comparison**- **Adjacency list** - Memory: O(N + E) ~ 10M + 30M entries → very compact. - BFS/Dijkstra: good cache locality per node; BFS O(N+E), Dijkstra using binary heap O((N+E) log N). - Dynamic updates: cheap (O(1) amortized insert to list; O(deg) delete). Good for frequent local changes.- **Adjacency matrix** - Memory: O(N^2) — impossible (10M^2). Not usable.- **Edge list** - Memory: O(E), minimal per-edge storage but no direct neighbor lookup. - BFS/Dijkstra: slow for traversals (must scan edges to find neighbors) — inefficient. - Dynamic updates: easy append; deletions require costly scans or auxiliary index.- **CSR (Compressed Sparse Row)** - Memory: O(N + E) but contiguous arrays for neighbors and offsets → better cache and lower overhead than pointer lists. - BFS/Dijkstra: fastest traversal throughput (sequential memory), Dijkstra compatible. - Dynamic updates: poor — arrays are static; support via rebuilds or overprovisioned buffers, or hybrid approach (CSR + small adjacency buffers for recent deltas).**Recommendation for role**Use CSR for read-heavy workloads (fast BFS/Dijkstra, low memory). For APIs requiring frequent updates, use adjacency lists or a hybrid: CSR snapshot for analytics and a write buffer (hash map of recent edge inserts/deletes) merged periodically. For weighted Dijkstra, store weights in parallel CSR array.
EasyTechnical
64 practiced
Explain the trade-offs between using a dynamic array (e.g., JavaScript Array or Java ArrayList) and a singly/doubly linked list for storing a collection of items in a web application. Consider access time, insertion and deletion costs, memory overhead per element, cache locality, and typical frontend/back-end use cases such as maintaining UI lists, server-side job queues, and serialization.
Sample Answer
**Brief summary**For a full-stack developer, choose a dynamic array (JS Array / Java ArrayList) when you need fast random access and compact memory; choose a linked list when you need cheap splicing/ordered insertion/deletion at known positions and predictable iterator validity.**Access time**- Dynamic array: O(1) random access — ideal for indexing UI lists, pagination.- Linked list: O(n) random access (must traverse) — poor for index-based rendering.**Insertion / deletion**- Dynamic array: O(1) amortized append; O(n) for middle insert/delete due to shifts.- Singly/doubly linked list: O(1) insert/delete given node reference; O(n) to find node.**Memory overhead & cache locality**- Dynamic array: low per-element overhead, contiguous memory → excellent CPU cache locality → faster iteration (crucial for rendering, JSON serialization).- Linked list: higher overhead (next/prev pointers), scattered memory → poor cache locality → slower traversal and higher GC pressure in managed runtimes.**Typical use cases**- Frontend UI lists: dynamic arrays (virtualized lists, diffing) are standard for fast rendering and serialization.- Server-side job queues: linked lists or deque structures can be useful for O(1) push/pop; but often arrays or specialized queue implementations (ring buffer, concurrent queue) are preferred for performance and lower memory overhead.- Serialization / network: arrays serialize compactly; linked lists require pointer traversal and produce larger payloads.**Trade-offs / rule of thumb**- Prefer dynamic arrays for most web app work (rendering, storage, APIs). Use linked lists only when you have frequent middle insertions/deletions with node references and can tolerate memory and traversal costs.
MediumTechnical
64 practiced
Design an undo/redo system for a collaborative editor where edits are small operations (inserts/deletes) and multiple users can edit concurrently. Compare command stacks, persistent immutable trees, operational transform (OT), and CRDTs. Discuss memory overhead, merge semantics, latency, and ease of implementation for a full-stack developer.
Sample Answer
**Approach summary**Design: model edits as small operations (insert/delete with position + id). Keep per-client local history for undo/redo plus a global replication layer to merge concurrent operations. Two undo styles: local (revert only your own ops) and global (group-aware undo using tombstones/intent tracking).**Comparison (command stacks, persistent trees, OT, CRDTs)**- Command stacks - Memory: minimal (linear history). - Merge semantics: poor — concurrent edits conflict; requires locking or manual merges. - Latency: low locally; high when synchronizing. - Ease: easiest to implement on single-user; fragile for collaboration.- Persistent immutable trees (Rope/CRDT-like persistent structures) - Memory: higher (structural sharing reduces cost). - Merge: deterministic if combined with operation model; needs reconciliation layer. - Latency: fast local edits; moderate to merge. - Ease: moderate — requires immutable data structures and diff/patch logic.- Operational Transform (OT) - Memory: moderate (store history and transformation metadata). - Merge: transforms concurrent ops to preserve intention; complex to get correct (TP1/TP2). - Latency: low with client-side optimistic updates; server coordinates transforms. - Ease: hard — nontrivial algorithms and edge cases.- CRDTs (sequence CRDTs like RGA/WOOT/Logoot) - Memory: higher (per-character identifiers, tombstones unless compacted). - Merge: strong eventual consistency; automatic merge without central server. - Latency: low (local ops applied immediately). - Ease: moderate — concepts simpler than OT, but implementing efficient sequence CRDT and undo semantics is tricky.**Practical recommendation for a Full-Stack Developer**- If you need correctness with minimal server complexity: choose a sequence CRDT with tombstone compaction and per-user undo (store inverse ops referencing unique IDs). Use immutable data structures on client for UI diffing.- If you already have a server-authoritative model and need lower memory: OT with server transform is viable but more brittle.- For prototypes or small teams: combine command stacks locally + server merge using CRDT identifiers for conflict resolution.**Example undo strategy (CRDT)**- Each insert assigns a unique position id. Undo = issue a delete referencing that id (logical delete). Redo = re-insert with same metadata. Garbage-collect tombstones when all replicas ack.This balances low-latency UX, clear merge semantics, and implementability across frontend (React immutable state) and backend (replicated store or message broker).
Unlock Full Question Bank
Get access to hundreds of Data Structure Selection and Trade Offs interview questions and detailed answers.
