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.

MediumTechnical

79 practiced

Design a concurrency-safe hash map suitable for a backend service with heavy reads and moderate writes. Discuss lock striping, concurrent buckets, copy-on-write resizing, and lock-free options. Address resizing strategy, memory reclamation, and how to measure contention. Give a high-level implementation sketch.

Sample Answer

**Approach summary**Design a read-optimized concurrent map by partitioning state (lock striping / concurrent buckets), doing mostly lock-free reads, and using a copy-on-write or staged resize to avoid long pauses. Describe trade-offs vs fully lock-free designs.

**Design elements**- Lock striping / concurrent buckets - Table = volatile array of Bucket[] - Each Bucket is a small linked list or tree; lock per stripe (ReentrantLock[] or StampedLock[]) where stripe index = hash & (stripeCount-1) - Reads: optimistic (no lock) + validate; fall back to read-lock only on mutation - Writes: acquire stripe lock for affected bucket(s)

- Copy-on-write resizing - When load factor threshold exceeded, create new larger table, rehash and transfer buckets - Use a single-resize CAS: create newTable and CAS-swap the table reference so concurrent reads see either old or new table - Transfer can be done incrementally: background worker moves buckets in batches; writers help move buckets when they touch an unmigrated bucket

- Lock-free options - Full lock-free maps (compare-and-swap on nodes, atomic linked lists or treaps) reduce blocking but are complex and error-prone. Consider only for extreme low-latency requirements.

**Resizing strategy**- Trigger when size/slots > threshold (e.g., 0.75)- Double size; use incremental rehashing to avoid long stop-the-world; keep a forwarding marker in moved buckets so readers/writers can redirect- Use CAS to swap in new table reference, and let threads assist migration

**Memory reclamation**- In Java: rely on GC; avoid unsafe manual free. Use volatile/atomic references and null out old references after migration to allow GC.- In native environments: use epoch-based reclamation or hazard pointers to avoid ABA and reclaim nodes safely.

**Measuring contention**- Per-stripe counters for lock acquisition attempts and wait time- Expose metrics: lock contention rate, average lock hold time, failed CAS counts, resize frequency- Use profilers / async stack sampling to detect hotspots (jstack, async-profiler)- Alerts when average wait time exceeds threshold or retries/backs offs spike

**High-level Java sketch**

java

class ConcurrentStripedMap<K,V> {
  volatile Bucket<K,V>[] table;
  final ReentrantLock[] locks; // stripe locks
  final AtomicInteger size = new AtomicInteger();

  V get(K k) {
    int h = spread(k.hashCode());
    Bucket<K,V>[] tbl = table;
    Bucket<K,V> b = tbl[h & (tbl.length-1)];
    // optimistic read without lock
    Node node = b.find(h,k);
    if (node != null) return node.value;
    // optional: if forwarding marker -> helpTransfer(...)
    return null;
  }

  void put(K k, V v) {
    int h = spread(k.hashCode());
    int stripe = h & (locks.length-1);
    locks[stripe].lock();
    try {
      Bucket<K,V>[] tbl = table;
      Bucket<K,V> b = tbl[h & (tbl.length-1)];
      if (b.putOrReplace(h,k,v)) size.incrementAndGet();
      if (needResize()) startResizeIfNeeded();
    } finally { locks[stripe].unlock(); }
  }

  // resize and transfer logic: create new table, CAS swap, incremental transfer
}

**Trade-offs / when to choose**- Lock striping + COW resize: simple, good for heavy reads + moderate writes; predictable- Fully lock-free: more concurrency but complex and higher engineering/bug risk- Use metrics-driven tuning: stripe count ~ cores*2; resize threshold tuned to memory vs latency

This design balances read performance, moderate write throughput, safe resizing, and practical memory reclamation for a Java backend service.

HardTechnical

69 practiced

Implement a persistent (immutable) segment tree in C++ that supports point updates and range-sum queries while preserving all previous versions (versioned roots). Explain node-sharing strategy to minimize extra memory per update, and compute worst-case additional memory per update given n elements.

Sample Answer

**Approach (brief)**Use an immutable binary segment tree where each update returns a new root. Only nodes on the path from root to the updated leaf are copied; all other nodes are shared. This gives O(log n) time per update and O(log n) extra nodes (memory) in the worst case.

**C++ implementation**

cpp

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long sum;
    Node *l, *r;
    Node(long long s=0, Node* L=nullptr, Node* R=nullptr): sum(s), l(L), r(R) {}
};

// build from array [a_lo, a_hi)
Node* build(const vector<int>& a, int lo, int hi){
    if(lo+1==hi) return new Node(a[lo]);
    int mid=(lo+hi)/2;
    Node* L=build(a,lo,mid);
    Node* R=build(a,mid,hi);
    return new Node(L->sum + R->sum, L, R);
}

// persistent point update: returns new root after setting index idx to val
Node* update(Node* cur, int lo, int hi, int idx, int val){
    if(lo+1==hi) return new Node(val); // copy leaf
    int mid=(lo+hi)/2;
    if(idx < mid){
        Node* newL = update(cur->l, lo, mid, idx, val);
        return new Node(newL->sum + cur->r->sum, newL, cur->r); // share right
    } else {
        Node* newR = update(cur->r, mid, hi, idx, val);
        return new Node(cur->l->sum + newR->sum, cur->l, newR); // share left
    }
}

// range sum query on a given version (root)
long long query(Node* cur, int lo, int hi, int ql, int qh){
    if(!cur || ql>=hi || qh<=lo) return 0;
    if(ql<=lo && hi<=qh) return cur->sum;
    int mid=(lo+hi)/2;
    return query(cur->l, lo, mid, ql, qh) + query(cur->r, mid, hi, ql, qh);
}

**Key concepts / reasoning**- Node-sharing: unchanged subtrees are reused; only nodes along the update path are newly allocated.- Persistence store: keep vector<Node*> roots; each update pushes a new root representing a new version.- Time: O(log n) per update and query.- Worst-case extra memory per update: O(log n) new nodes (height of tree). Total memory over m updates: O(n + m log n).

**Edge cases**- Index out of range; single-element arrays; many versions — consider pooling/garbage collection in long-lived services.

HardTechnical

92 practiced

Design a concurrent priority queue for a multi-producer multi-consumer backend that minimizes contention. Discuss implementations: coarse-grained lock on a binary heap, lock-striping heaps per thread, skiplist-based priority queue, and lock-free approaches. Explain batching, approximate semantics, and where eventual consistency is acceptable.

Sample Answer

**Clarify requirements & constraints**- Multi-producer, multi-consumer, high throughput, low latency, minimize contention. Priority must be mostly correct; occasional reordering acceptable? Memory/CPU limits, failure modes, and hardware (NUMA) matter.

**High-level options & trade-offs**- Coarse-grained lock on binary heap - Simple and fair for low concurrency. - Bottlenecks: single lock serializes all ops; poor throughput under many threads. - Use when correctness/strict ordering is required and load is low.

- Lock-striping: many heaps (shards) with per-shard locks - Producers pick shard by hash or round-robin; consumers poll shards for best head. - Reduces contention; increases parallelism. - Approximate semantics: global top may be missed momentarily. Best when approximate ordering ok. - Need global coordination for peek/remove-min: sample k shards and pick best head to balance correctness and cost.

- Skiplist-based priority queue (concurrent skiplist) - Fine-grained locking or optimistic (Harris-Michael) algorithms allow concurrent inserts/removes. - Good for workloads with many inserts and fewer global-min removes; maintains near-strict ordering. - More complex but scales well and supports range queries.

- Lock-free approaches - True lock-free priority queues are complex (e.g., skiplist-based, weak-heap variants). They avoid blocking but are hard to implement and test. - Use when latency spikes from locks are unacceptable; otherwise cost/complexity often outweighs benefits.

**Performance techniques**- Batching: group inserts or pops (e.g., producer-side buffer that flushes multiple items into queue). Reduces synchronization frequency, increases throughput; trade-off: increased latency for first item.- Combining thread (flat-combining): designate a combiner thread to apply many ops under one lock—reduces contention at cost of possible latency.- Sampling & k-ary selection: consumers sample several shards and choose best head; k trades off correctness vs contention.

**Approximate semantics & eventual consistency**- Acceptable when priority is a heuristic (task scheduling, background jobs, retries). Use sharded queues or relaxed FIFO semantics. Document bounds (e.g., top-K guarantee).- Not acceptable for finance/strict ordering or where correctness depends on exact priority.

**Recommendation for backend developer**- If strict global ordering required but moderate concurrency: concurrent skiplist or lock-striping with careful sampling.- If max throughput with relaxed ordering acceptable: sharded heaps + batching + sampling; optionally a dedicated merger process for eventual consistency.- If extreme low-latency under contention and team can maintain complexity: consider well-tested lock-free library implementations rather than building from scratch.

**Operational notes**- Measure with realistic workload; tune shard count to threads and NUMA; observe tail latencies; prefer simpler, well-tested primitives before lock-free implementations.

HardTechnical

98 practiced

Outline how to implement a lock-free skip list (or provide code sketch) in C++ or Java for a backend index. Focus on the core insert and delete algorithms using CAS, and discuss strategies for safe memory reclamation (hazard pointers, epoch-based reclamation) to avoid use-after-free in concurrent access.

Sample Answer

**Approach (brief)** I'll sketch a lock-free skip list in C++-style pseudocode focusing on insert/delete using CAS plus strategies for safe reclamation (hazard pointers / epochs).

**Core ideas**- Each node has key, value, array of next pointers (levels) and a marked flag for logical deletion.- Use atomic compare-and-swap (CAS) on next pointers; logical delete (mark) before physical removal.- Search returns predecessor and successor arrays for each level.

**Insert (sketch, C++-like)**

cpp

// Node { key, value, next[level], marked (atomic<bool>) }
// find(key, preds[], succs[]) fills arrays
bool insert(K key, V val) {
  while (true) {
    find(key, preds, succs);
    if (succs[0] && succs[0]->key==key) return false; // existing
    Node* newNode = new Node(key,val, level=randomLevel());
    for (int i=0;i<=newNode->topLevel;i++) newNode->next[i]=succs[i];
    if (!atomic_compare_exchange_strong(&preds[0]->next[0], &succs[0], newNode)) {
      delete newNode; continue; // retry
    }
    // link higher levels (if CAS fails, other threads will help or retry)
    for (int i=1;i<=newNode->topLevel;i++) {
      while (!atomic_compare_exchange_strong(&preds[i]->next[i], &succs[i], newNode)) {
        find(key,preds,succs); // refresh
      }
    }
    return true;
  }
}

**Delete (sketch)**

cpp

bool remove(K key) {
  Node* node;
  while (true) {
    find(key,preds,succs);
    node = succs[0];
    if (!node || node->key!=key) return false;
    // mark top-down
    for (int i=node->topLevel;i>0;i--) {
      Node* succ;
      while (true) {
        succ = node->next[i].load();
        if (node->next[i].compare_exchange_strong(succ, markPointer(succ))) break;
        if (isMarked(node->next[i].load())) break;
      }
    }
    // mark level 0 (logical deletion)
    Node* succ0 = node->next[0].load();
    if (!node->next[0].compare_exchange_strong(succ0, markPointer(succ0))) continue;
    // try physical removal by CAS on preds
    find(key,preds,succs);
    for (int i=0;i<=node->topLevel;i++)
      preds[i]->next[i].compare_exchange_strong(node, succs[i]);
    retire(node); // schedule for reclamation
    return true;
  }
}

**Memory reclamation**- Hazard pointers: each thread publishes pointers it may dereference; retired nodes are reclaimed only when no hazard pointer references them. Good for bounded pause, predictable reclamation.- Epoch-based reclamation: threads enter epochs; retired nodes are freed once all threads moved past the epoch where node was retired. Simpler and more performant under high concurrency but requires all threads to cooperate and can delay reclamation.- Choose hazard pointers for long-lived threads with pointer-heavy reads (fine-grained safety). Use epoch-based (e.g., RCU-like) in throughput-critical backends where pauses are acceptable.

**Correctness & performance notes**- Linearizability: insert linearizes at successful CAS linking level 0; remove linearizes at successful logical mark of level 0.- Must ensure find() helps remove marked nodes (helping) to avoid ABA and to maintain progress.- Complexity: expected O(log n) time per op; CAS-heavy with retries under contention.

**Practical tips**- Use well-tested libraries where possible (folly’s LockFreeSkipList, Java’s ConcurrentSkipListMap is lock-based).- Thoroughly test with stress tests and tools (ThreadSanitizer, valgrind) and verify reclamation strategy under production workload.

MediumTechnical

72 practiced

You are responsible for a trie-based autocomplete that must handle millions of stored phrases in multiple languages. Describe a testing and profiling plan to find bottlenecks and optimize memory/time. Include unit tests, integration tests, benchmarks, memory profiling, and strategies to reduce node footprint (e.g., compression, pooling).

Sample Answer

**Overview / goals**Define latency (e.g., autocomplete query p95 < 10ms) and memory targets (per-shard RAM). Iterate: reproduce, profile, optimize, verify.

**Unit tests**- Functional: insert / lookup / prefix / delete across languages (UTF-8, combined forms). Use normalization (NFC/NFD) in tests.- Edge cases: empty strings, very long phrases, diacritics, surrogate pairs.- Thread-safety: concurrent reads/writes using stress tests (race detectors).- Deterministic persistence tests: serialize/deserialize produces identical behavior.

**Integration tests**- End-to-end API tests (HTTP): hit autocomplete endpoints with realistic payloads.- Data pipeline tests: bulk-load millions of phrases, validate counts, sampling accuracy.- Multi-language correctness: verify language-specific tokenization and ranking.

**Benchmarking**- Microbenchmarks: single-node query latency, insertion throughput, bulk-load time. Tools: JMH (Java), pytest-benchmark, node-bench.- Load tests: simulate production traffic patterns with k6 or Locust; vary read/write ratios and shard counts.- Metrics: p50/p95/p99 latency, CPU, GC pause, QPS per core, memory per stored phrase.

**Memory & CPU profiling**- Heap profiles: pprof, Java Flight Recorder / VisualVM, massif/heaptrack for native. Capture before/after bulk-load.- CPU flamegraphs to find hot code paths.- Allocation tracing to identify per-node overhead (object headers, pointers).- Track fragmentation and GC behavior.

**Optimize node footprint**- Data structure choices: evaluate compressed trie variants (radix/Patricia trie), double-array trie for compactness, or finite-state transducer if static.- Node layout: - Store child map as contiguous arrays or sorted vectors + binary search for small nodes. - Use 32-bit offsets instead of pointers; pack flags into bitfields. - Store shared suffixes via deduplication (hash-consing).- Compression: - Path compression (collapse single-child chains). - Tail pooling: store long suffixes in a pooled string arena and reference by offset. - Front-coding for sorted phrase blocks on-disk.- Memory pooling / arenas: - Use object pools or arena allocators to avoid per-node allocation overhead. - Preallocate per-shard pools to reduce fragmentation and improve cache locality.- Lazy loading / sharding: - Keep hot prefixes in memory; cold partitions on SSD or memory-mapped files. - Shard by language or prefix to bound per-process memory.- Serialization: compact binary format for snapshots; mmap for fast load.

**Verification after changes**- Re-run unit/integration tests and benchmarks; compare baseline and optimized metrics.- Regression tests for correctness and concurrency.- Continuous profiling in staging (periodic heap/CPU snapshots).

**Trade-offs & monitoring**- Compression reduces memory but may increase CPU—define SLA and tune.- Expose metrics (memory per shard, hit-rate, cache miss) and alerts; roll out optimizations behind feature flags.

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.