Advanced Data Structures and Implementation Questions

Deep and practical expertise in advanced data structures, their implementation details, performance characteristics, and selection for both algorithmic problems and production systems. Topics include arrays and dynamic arrays, strings, linked lists, stacks and queues, hash tables, heaps and priority queues, various tree forms including binary search trees and balanced trees, tries or prefix trees, segment trees and binary indexed trees or fenwick trees, union find or disjoint set union, suffix arrays, and advanced graph representations. Candidates should be able to implement core structures from first principles, demonstrate interfaces and invariants, reason about insertion deletion search traversal and iteration costs including worst case average case and amortized analysis, and discuss memory management and ownership in low level languages such as C and C plus plus as well as safe memory and reference use in managed languages. Evaluation also covers trade offs between contiguous and pointer based layouts, cache friendliness, concurrency considerations, selection of structures based on access patterns update frequency and memory constraints, handling of edge cases, testing and performance tuning for realistic inputs, and applying structures to problems such as top K queries prefix search connectivity range queries caches and union operations.

HardTechnical

68 practiced

Implement a lock-free singly linked list that supports concurrent insert and delete using atomic compare-and-swap (CAS) operations in C++. Provide code sketch and explain how you avoid ABA problems and ensure correctness under concurrency. Discuss memory reclamation strategies for removed nodes.

Sample Answer

Approach: use a lock-free singly linked list with atomic pointer+tag (version) to avoid ABA. Insert and delete use CAS on a combined struct {Node* ptr; uint64_t tag}. Deletion marks nodes logically (marked bit in pointer or separate flag) before physical removal. For memory reclamation use hazard pointers or epochs to avoid reclaiming nodes still accessed.

Code sketch (simplified — production needs more careful ABA/atomic packing and alignment):

cpp

#include <atomic>
#include <cstdint>

struct Node {
  int value;
  std::atomic<uint64_t> next; // lower bits: pointer, high bit: marked
  Node(int v): value(v), next(0) {}
};

inline uintptr_t pack(Node* p, uint64_t tag){ return (uintptr_t)p | (tag & 1); }
inline Node* ptr_of(uintptr_t x){ return (Node*)(x & ~uintptr_t(1)); }
inline bool marked_of(uintptr_t x){ return x & 1; }

class LFList {
  std::atomic<uintptr_t> head; // packed pointer+mark/tag
public:
  LFList(){ head.store(pack(nullptr,0)); }

  bool find(int val, std::atomic<uintptr_t> &pred, std::atomic<uintptr_t> &curr){
    // traverse, help removing marked nodes
    // omitted for brevity
    return false;
  }

  void insert(int val){
    Node* n = new Node(val);
    while(true){
      uintptr_t h = head.load();
      n->next.store(h);
      if(head.compare_exchange_weak(h, pack(n, (uintptr_t(h)+1)&1))) return;
    }
  }

  bool remove(int val){
    // logical mark then physical CAS from pred->next to curr->next
    // use CAS loops similar to Harris-Michael list
    return false;
  }
};

Key correctness points:- Use atomic CAS on packed (pointer, version/tag) to prevent ABA: every successful update increments tag so old pointer+tag combo never reappears.- Logical deletion: mark node first so concurrent readers know node is deleted; physical removal is attempted by any thread.- Helping: threads encountering marked nodes help unlink them to maintain progress.

Memory reclamation:- Hazard pointers: each thread announces pointers it may access; reclamation only frees nodes not protected by any hazard pointer.- Epoch-based reclamation (EBR): retire nodes into epoch buckets and free when all threads have advanced past the epoch.- Quiescent-state based GC or reference counting variants also possible; hazard pointers/EBR are preferred for lock-free lists.

Edge considerations:- ABA can still occur if tag width is small; use wide tags (64-bit combined). Ensure proper pointer alignment to use low bits for flags.- Correctness requires thorough testing under contention and formally verifying atomic sequences.

HardTechnical

74 practiced

Implement suffix array construction using a linear-time algorithm (SA-IS or skew/DC3) in C++ or explain in detail how it works and why it runs in O(n). Provide complexity analysis and discuss memory requirements and practical considerations for very long strings.

Sample Answer

Approach summary:I’ll explain SA-IS (induced sorting) — a linear-time suffix-array construction algorithm — give why it is O(n), compare to DC3 (skew), and discuss memory and practical issues for very long strings and ML use cases.

SA-IS algorithm (high-level steps):1. Classify each position as S-type or L-type: S if suffix at i < suffix at i+1 (lexicographically) or equal and next is S; else L.2. Identify LMS (Left-most S-type) positions (positions i where i is S and i-1 is L).3. Sort LMS-substrings by induced sorting: - Place LMS suffixes into buckets by first character; perform induced L- and S-type sorts to propagate relative order to all suffixes.4. If LMS substrings names are not unique, recursively build SA for the reduced string of names; otherwise deduce order.5. Use induced sorting again to produce full SA from ordered LMS positions.

Why O(n):- Classification and bucket counting are single linear scans.- Induced sorting processes each position a constant number of times: placing into buckets and scanning buckets left-to-right or right-to-left — each scan is O(n).- Recursion is on number of LMS positions ≤ n/2; when substrings are unique the recursion ends; overall work forms a linear recurrence T(n) = T(n') + O(n) with n' ≤ n/2 ⇒ O(n).

Complexity:- Time: O(n) worst-case (linear).- Space: O(n + |Σ|) where Σ is alphabet size. Practically needs: - input string (n) - SA array (n) - type array (n bits or bytes) - bucket counts and pointers (|Σ|) - temporary name / reduced-string (≤ n)So about 4–6 × n machine words in straightforward C++; can compress type to bits to save memory.

DC3 (skew) comparison:- DC3 builds SA by recursively sorting suffixes at positions mod 3 ≠ 0, merging; also linear-time with more complicated merging. DC3 tends to be simpler to implement than SA-IS for some but has similar memory profile and constant factors.

Practical considerations for very long strings:- Alphabet reduction: map bytes to small integer alphabet first to reduce |Σ|.- Memory: use 32-bit ints if n < 2^31 to halve memory versus 64-bit. Store type as bits.- External or streaming: for strings larger than RAM, use external-memory suffix array algorithms or suffix-array-like structures (FM-index, BWT) with disk-friendly construction.- Parallelism: SA-IS is inherently sequential in induced passes, but you can parallelize bucket scanning and local sorts; DC3 offers more parallelism in recursion.- Libraries: for production prefer Battle-tested libs (libsais, sais-lite) optimized for constants and memory.

ML relevance:- Large text corpora, genomic sequences, or token sequences require scalable suffix structures for tasks like substring frequency, compression, or building suffix-based retrieval. For very long sequences, consider suffix automata, BWT+FM-index or sampled suffix arrays for lower memory and fast substring queries.

Implementation note:- Implement carefully to manage buckets and stable placements; use in-place induced steps to reduce memory. For production C++ use libsais or sais-lite unless you need a custom variant.

MediumSystem Design

82 practiced

Design a concurrent data access pattern for real-time ML feature ingestion that requires lockless reads and batched writes. Propose an approach (e.g., copy-on-write, versioned maps, or read-copy-update) that minimizes read latency while allowing safe batched updates. Discuss garbage collection of old versions and memory overhead.

Sample Answer

Requirements clarification:- Extremely low read latency (lockless reads), many concurrent readers.- Writers perform batched updates (periodic inserts/updates/deletes).- Safe visibility: readers must see a consistent feature map; writers should not block reads.

High-level approach — Read-Copy-Update (RCU) / versioned immutable maps:- Maintain an atomic pointer/reference (current_version) to an immutable feature map (e.g., persistent hash map or plain hash map treated immutably).- Readers: perform one atomic load of current_version and read from that map without any locks. Very low latency: one atomic read + lookups.- Writers (batched): create a new map by shallow-copying current_version (copy-on-write semantics) and apply the entire batch to this new map. After update, publish the new map by an atomic swap of current_version.- Optionally, use structural sharing (persistent data structures like Clojure/Scala maps or Google’s immutable collections) to reduce copy cost for large maps.

Garbage collection / safe reclamation:- After swapping, old versions must be freed only when no reader can still reference them.- Use one of: - Epoch-based reclamation: readers announce entry/exit epochs; reclaim versions once all readers are past the publish epoch. - Reference counting / shared_ptr: each reader holds a shared reference; writer’s old pointer is released and deleted when count drops to zero. - Hazard pointers for manual memory management (C++).- In managed runtimes (Java, Python), rely on GC + AtomicReference; ensure no long-lived reader threads hold references unnecessarily.

Memory overhead and tradeoffs:- Memory overhead = multiple full versions in memory while readers refer to prior versions. With structural sharing this is much lower (only modified nodes duplicated).- Batch size vs memory: larger batches reduce frequency of new versions (lower overhead), but increase latency until features appear; small batches increase churn and memory cost.- Copy cost: naive full-copy O(N) per batch; with persistent/structural sharing, amortized lower cost.- Throughput vs latency: RCU favors reads; heavy write rate with large maps may make copies expensive — consider sharded maps (per-key shard) to limit copy scope.

Practical notes / implementations:- Java: AtomicReference<Map> + immutable maps or Guava ImmutableMap; use readers that call get() and then queries.- C++: std::shared_ptr + atomic swap + epoch/hazard pointers for reclamation.- Sharding: split keyspace into K shards to perform per-shard copy-on-write, reducing per-batch copy size and GC pressure.- Monitoring: track number of outstanding versions, memory per version, and reclaim lag to tune batch frequency and shard count.

Edge cases:- Long-running readers delaying reclamation — detect and mitigate (timeouts, backpressure).- Deletes: ensure tombstones if downstream needs to know deletions until all readers moved on.

In short: RCU/versioned maps with atomic publish and epoch or ref-counted reclamation gives lockless reads, safe batched writes, and predictable read latency; mitigate memory overhead using sharding and structural sharing.

MediumSystem Design

90 practiced

You need to store and process a large graph for GNN training on GPUs: many millions of nodes and edges. Compare adjacency-list, CSR (compressed sparse row), and COO representations. Propose a memory layout and data pipeline to efficiently transfer mini-batches of neighbors to GPU for computation and explain trade-offs.

Sample Answer

Requirements and constraints:- Graph size: millions of nodes/edges (fits on CPU host but not GPU).- Workload: GNN mini-batch training that needs neighbor sampling and sparse aggregation on GPU with low CPU-GPU overhead and good memory locality.- Goals: minimize CPU-GPU transfer, enable fast random neighbor access for sampling, support multi-GPU.

Compare representations:- Adjacency-list (per-node variable-length arrays): intuitive for sampling, easy to append, but fragmented in memory (pointer-heavy) so poor locality and high overhead when copying many small buffers to GPU.- CSR (Compressed Sparse Row): stores neighbors as contiguous neighbor array + index pointer array. Excellent memory locality, compact, O(1) access to a node's neighbor slice, efficient bulk transfers. Static graph-friendly; updates expensive.- COO (edge list): two arrays (src, dst) good for constructing/transforming sparse ops and for frameworks expecting edge lists; less efficient for per-node neighbor scans and has poorer locality for neighbor blocks.

Proposed memory layout and pipeline:- Store graph on host in CSR: neighbors[] (uint32/64), offsets[] (uint64) packed, plus per-edge/ per-node features in contiguous arrays aligned to 64B.- Precompute node degrees and optional prefix-sums; store popular-node neighbor blocks in separate hot cache.- Pipeline: 1. On each batch, sample a set of seed nodes and perform neighbor sampling on CPU using CSR slices (fast pointerless access). Use vectorized/randomized sampling per slice to produce sampled node list and gathered edges. 2. Compute contiguous GPU-transfer buffers: unique node id array, edge index pairs if needed, and compacted feature tensors. Use a staging pinned-memory buffer to pack these arrays sequentially to exploit DMA. 3. Async cudaMemcpy from pinned host memory to GPU; overlap with CPU sampling of next batch using multiple streams. 4. On GPU, map node IDs to feature tensors (either transfer features or use unified memory/managed cache for very large features). Use small temporary CSR built per-batch or direct index-based gather for aggregation. 5. Return gradients by reversing mapping; apply updates to host-stored parameters or use parameter sharding across GPUs.

Optimizations & trade-offs:- CSR gives best throughput and minimal transfer size; downside: expensive updates (not an issue for static graphs).- Using pinned buffers and packing contiguous arrays minimizes PCIe overhead; cost is extra host RAM and serialization cost to pack.- Caching hot-node neighbor blocks reduces sampling latency but increases memory.- If graph is dynamic or edges change frequently, adjacency-list/COO is easier to update but will cost transfer performance.- Multi-GPU: shard CSR by node ranges or use replicated CSR with partition-aware sampling to reduce cross-GPU communication.

This design balances low transfer overhead, high locality (CSR), and asynchronous pipelining to keep GPUs saturated during GNN training.

HardSystem Design

136 practiced

Design a cache-friendly B-tree layout optimized both for SSD-backed storage (minimizing I/O) and for in-memory GPU batch processing of embeddings (maximizing coalesced reads). Discuss node size, fanout, write amplification, alignment, and choices for storing keys/values externally vs inline.

Sample Answer

Requirements & constraints:- Minimize SSD I/O latency and random reads; favor large sequential I/O and aligned transfers.- Maximize GPU throughput for batched embedding lookups: coalesced memory access (128–256B lanes), contiguous value layout, few PCIe transfers.- Support mixed small keys/index metadata and large embedding vectors.

High-level design:- Use a B+ tree on SSD with internal nodes containing keys and child pointers; leaf nodes contain keys + pointers to values (external) or inline small values.- Store large embeddings externally in an append-only value store (blob file / object store) optimized for large sequential writes; leaves store 8–16B fixed-size value references (offset+length) and small metadata.

Node size & fanout:- Choose node size as a multiple of SSD page/IO unit: 64KB or 128KB node size (balances fewer disk ops with manageable memory footprint). For 128-bit keys and 8B pointers, a 128KB internal node yields very high fanout (reduce tree height → fewer random reads).- Fanout tuned so internal node fits a single sequential read: aim for node read <= 128KB to exploit drive queueing.

Alignment & layout:- Align nodes to 4KB or NVMe optimal stripe (4096B) and to 128KB boundaries when using larger IO. Pad node headers to fixed offsets so keys/pointers are cache-line aligned.- Store keys in sorted, tightly packed arrays (key array + pointer array). Use fixed-width keys or dictionary-encoded prefixes to enable binary search/vectorized search (SIMD).

GPU coalesced reads:- For embedding batches, store embedding blobs in large contiguous blocks aligned to 256B (or 128B) boundaries. Use a columnar layout: embeddings packed sequentially; strided access avoided by reading a contiguous block of embeddings for a batch and then copying to GPU staging buffer.- On lookup path: read leaf node(s) (small set) on CPU, gather value offsets, then issue one or few large sequential reads to fetch all embedding vectors for the batch into host memory, pinned & page-locked for DMA to GPU—this yields coalesced PCIe and GPU accesses.- Optionally store hot embeddings in GPU memory or in an on-host cache for repeated access.

Write strategy & write amplification:- Use LSM-inspired append-only value store for embeddings to turn random writes into sequential writes; maintain a compacting background process to reclaim space. This reduces SSD write amplification for large values.- For index nodes, use copy-on-write B+ tree nodes with batched writes: group multiple small updates and write whole nodes atomically (e.g., via log or write-ahead buffer) to reduce small random writes. Periodic compaction/defragmentation mitigates fragmentation.

Keys/values: external vs inline trade-offs:- Inline small values (<= 64–128B) in leaf entries to avoid extra IO and pointer indirection.- External store for large embeddings (KBs): leaf stores a compact reference (offset+length + version). Benefits: smaller tree (higher fanout), lower index cache pressure, and single large IO per batch.- Consider storing very hot small embeddings inline or duplicated for hot path.

Additional optimizations:- Use bloom filters per SST-like segment to avoid unnecessary leaf reads.- Prefetch sibling leaves when scanning; use asynchronous NVMe reads with high queue depth.- Use prefix-compressed keys in nodes and full keys in leaves.- Provide GPU-friendly metadata: when preparing a batch, emit an array of 64-bit offsets aligned to 128B so GPU kernels can perform scatter/gather efficiently if embedding rows are fixed-size.- Monitor and adapt node size/fanout based on observed read/write patterns; allow smaller node size for workloads with tiny values and latency-sensitive lookups.

Trade-offs:- Larger nodes → fewer I/Os, but higher CPU + memory per node and larger write amplification if updating nodes frequently.- External blobs reduce index size but add one extra I/O unless batched. Batched reads and pinned buffers largely eliminate the extra overhead for GPU workloads.

This layout balances SSD-friendly large aligned IO for values and compact, high-fanout index nodes, while enabling batched, coalesced GPU reads by packing embeddings contiguously and staging them efficiently for DMA.

Unlock Full Question Bank

Get access to hundreds of Advanced Data Structures and Implementation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.