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

80 practiced

Implement an LRU (Least Recently Used) cache that supports get(key) and put(key, value) in O(1) time. Provide a thread-unsafe implementation first (your language of choice: Python/Java/C++), describe the data structures used, and discuss how you'd make it thread-safe for multi-threaded environments.

Sample Answer

To implement an LRU cache in O(1) for get and put, use a hashmap for key→node lookup and a doubly-linked list to maintain recency (head = most recent, tail = least recent). On get/put you move a node to head. Evict tail when capacity exceeded.

python

class Node:
    def __init__(self, k, v):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}               # key -> Node
        # dummy head/tail for simpler ops
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        p, n = node.prev, node.next
        p.next, n.prev = n, p

    def _add_to_head(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if not node:
            return -1
        self._remove(node)
        self._add_to_head(node)
        return node.v

    def put(self, key, value):
        node = self.map.get(key)
        if node:
            node.v = value
            self._remove(node)
            self._add_to_head(node)
            return
        node = Node(key, value)
        self.map[key] = node
        self._add_to_head(node)
        if len(self.map) > self.cap:
            # evict tail.prev
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]

Key points:- Hashmap provides O(1) lookup; doubly-linked list provides O(1) insertion/removal given a node.- Time: O(1) average for get/put. Space: O(capacity).

Edge cases:- capacity <= 0 (reject/raise), duplicate puts, get non-existent key.

Thread-safety:- This implementation is thread-unsafe because operations mutate shared structures. To make it thread-safe: - Coarse-grained: protect get/put with a single mutex (Lock). Simple but serializes all ops. - Fine-grained: separate locks for map and list or use ConcurrentHashMap + a concurrent linked deque + compare-and-swap strategies; more complex to avoid race conditions on node movement. - Read-heavy workloads: use Read-Write lock (Readers can access concurrently; writers acquire exclusive lock) but careful: get modifies recency so it's a writer. - Alternative: use existing thread-safe caches (e.g., Java's ConcurrentLinkedHashMap or Guava Cache) or use segmenting/sharding (multiple LRU shards) to improve concurrency.- Also consider atomicity for eviction and memory visibility (volatile or synchronized in Java).

HardTechnical

96 practiced

Design an internationalized real-time prefix search supporting multiple languages and Unicode: describe normalization (NFC/NFD), accent folding, case folding, tokenization, and the choice of data structures (per-language tries, inverted indexes). Explain how to handle multi-byte characters, variable-length grapheme clusters, and performance considerations.

Sample Answer

Requirements & constraints:- Real-time prefix search across multiple languages and scripts, low-latency (ms), supports Unicode, accents, case-insensitive matches, and correct grapheme handling.

Normalization & folding:- Normalize all input and indexed strings to a stable Unicode form — use NFC for storage/search canonicalization (combines base+combining marks). Alternatively use NFKC when you want compatibility decomposition (e.g., width/symbol compatibility) but be cautious about semantic changes.- Case folding: apply Unicode CaseFolding (full mapping) to both indexed terms and queries so "Σ" vs "σ" and language-specific cases are handled.- Accent (diacritic) folding: make it configurable per use-case. For accent-insensitive search, remove diacritics by decomposing to NFD then stripping combining marks (U+0300–U+036F), then recompose to NFC. Preserve original for display/highlight.

Tokenization & grapheme clusters:- Tokenize on language-aware boundaries: whitespace + punctuation for Latin; for CJK use character n-grams or word-segmentation (dictionary-based or ML tokenizer). Always iterate by Unicode grapheme clusters (use Unicode Text Segmentation — UAX #29) to avoid splitting emoji, flags, or emoji+skin-tone sequences — treat clusters as atomic units for prefix matching.- For prefix search, support both token prefix (beginning of token) and character/grapheme prefix. For CJK, n-gram prefixes (2–4) improve recall.

Data structures:- Per-language inverted index + per-token prefix structure: store normalized tokens in an inverted index mapping token → doc/record IDs. For prefix matching, keep a compact radix trie (patricia trie) per language or per script over normalized grapheme cluster sequences to enumerate matching tokens quickly.- Alternative: a single multilingual FST (finite-state transducer) mapping token → posting list id, compact and supports storage/compression (like Lucene's FST).- For high write throughput, maintain in-memory tries for recent data and periodically merge to on-disk FSTs.

Multi-byte & variable-length handling:- Always treat strings as sequences of code points/grapheme clusters, not bytes or UTF-16 code units. Use libraries that expose grapheme iteration (ICU, Swift Foundation, Python’s regex/third-party). When storing trie edges, store UTF-8 byte sequences for space efficiency, but ensure split only on grapheme boundaries.

Performance considerations:- Use compressed tries/FSTs to reduce memory and improve cache locality.- Cache top-K suggestions at nodes to avoid fetching full posting lists.- Shard by language or prefix hash for scale; keep hot prefixes in-memory.- Precompute and store both folded (case+accent-insensitive) and exact-normalized tokens to support both modes without reprocessing.- Latency: optimize token lookup path; use async merges and immutable on-disk structures to serve queries while indexing.- Testing: exhaustive Unicode test suite — combining marks, ligatures, right-to-left scripts, emoji, normalization edge cases, and locale-specific case rules.

Trade-offs:- Aggressive folding increases recall but reduces precision (lose diacritic distinctions). Make folding configurable and provide redirects to exact-match when needed.- Per-language tries improve accuracy but increase operational complexity; multilingual FST is compact but needs careful normalization to avoid cross-language collisions.

This design balances correctness on Unicode semantics, per-language behavior, and production performance by combining proper normalization + grapheme-aware processing with compact prefix data structures (tries/FSTs) and caching.

HardTechnical

90 practiced

Explain rank and select operations on bitvectors and implement a simple rank1(pos) and select1(k) interface using a two-level directory (superblocks and blocks) in C++ or pseudo-code. Discuss memory overhead and how to tune for speed vs space.

Sample Answer

Rank(pos) returns number of 1-bits in bitvector[0..pos] (inclusive or exclusive depending on convention). Select(k) returns index of the k-th 1 (0-based k). A common succinct approach uses a two-level directory: superblocks every S bits store total 1s up to start; inside each superblock, smaller blocks every B bits store 1s from superblock start. The bit data is kept packed (e.g., uint64_t words). rank1(pos) = super_sum + block_sum + popcount(on remaining bits). select1(k) finds superblock via binary search on super_sums, then block via linear/binary search, then scans word(s) to locate exact bit.

Pseudo/C++-like implementation (assumes 0-based indexing, rank1 returns #ones in [0,pos]):

cpp

// Uses builtin popcountll
struct RankSelect {
  vector<uint64_t> bits;         // packed bitvector
  vector<uint32_t> super_sum;    // every S bits: total ones before superblock
  vector<uint16_t> block_sum;    // per block within superblock: ones since superblock start
  int S, B; // S = superblock size in bits, B = block size

  uint64_t popcount64(uint64_t x){ return __builtin_popcountll(x); }

  // rank1: count ones up to pos (inclusive)
  uint32_t rank1(uint64_t pos){
    if(pos >= total_bits()) pos = total_bits()-1;
    uint64_t s_idx = pos / S;
    uint64_t b_idx = pos / B;
    uint32_t res = super_sum[s_idx];
    // block index relative to superblock
    int blocks_per_super = S / B;
    uint64_t b_in_super = b_idx % blocks_per_super;
    res += block_sum[s_idx * blocks_per_super + b_in_super];
    // compute offset from block start to pos
    uint64_t block_start_bit = (uint64_t)b_idx * B;
    uint64_t word_idx = block_start_bit / 64;
    int bit_off = block_start_bit % 64;
    uint64_t upto = pos - block_start_bit + 1;
    // first partial word
    if(bit_off) {
      uint64_t w = bits[word_idx] >> bit_off;
      if(upto <= 64 - bit_off) {
        uint64_t mask = (upto==64-bit_off) ? ~0ULL : ((1ULL<<upto)-1);
        res += popcount64(w & mask);
        return res;
      } else {
        res += popcount64(w);
        upto -= (64 - bit_off);
        word_idx++;
      }
    }
    while(upto >= 64){
      res += popcount64(bits[word_idx++]);
      upto -= 64;
    }
    if(upto > 0){
      uint64_t mask = (1ULL<<upto)-1;
      res += popcount64(bits[word_idx] & mask);
    }
    return res;
  }

  // select1: find position of k-th 1 (k is 1-based here)
  uint64_t select1(uint32_t k){
    // find superblock: binary search on super_sum
    int lo=0, hi=super_sum.size()-1;
    while(lo < hi){
      int mid=(lo+hi+1)/2;
      if(super_sum[mid] < k) lo=mid; else hi=mid-1;
    }
    uint32_t base = super_sum[lo];
    int blocks_per_super = S/B;
    // scan blocks within superblock
    int bstart = lo * blocks_per_super;
    int bi = 0;
    while(bi < blocks_per_super && base + block_sum[bstart+bi] < k) bi++;
    // now k is within block bstart+bi
    uint64_t block_bit = (uint64_t)(bstart+bi) * B;
    uint32_t need = k - (base + (bi? block_sum[bstart+bi-1]:0));
    // scan words in block to find exact word containing need-th one
    uint64_t word = block_bit / 64;
    int off = block_bit % 64;
    while(true){
      uint64_t w = bits[word] >> off;
      uint32_t pc = popcount64(w);
      if(pc >= need){
        // find position of need-th one within w
        for(int i=0;i<64-off;i++){
          if((w>>i)&1){
            need--;
            if(need==0) return (word*64 + off + i);
          }
        }
      } else {
        need -= pc;
        word++;
        off=0;
      }
    }
  }
};

Key points and complexity:- rank1: O(1) time dominated by a few memory reads + popcount across at most (B/64 + 2) words; effectively constant.- select1: O(#superblocks search + blocks scan + small word scan). With binary search on super_sum it's O(log(n/S) + S/B + small). In practice super_sum binary search then linear scan over small blocks is fast.

Memory overhead:- super_sum costs ~ (n / S) * 32 bits (or 64-bit) and block_sum costs ~ (n / B) * bits_per_block_count (e.g., 16 bits if S small). Total overhead ≈ n*(1/S * 32 + 1/B * 16) bits.Tuning:- Larger S and B reduce directory memory but increase per-query scan work (slower select/rank). Typical choices: S =~ 512..4096, B =~ 16..256. Use 64-bit super counters when n large; use 16-bit block counters if S <= 65535.- For speed: decrease S and B (more directory entries) so rank becomes pure table lookup + popcount on <=64 bits. For space: increase S/B and compress directories (delta-encoding, variable-length).Edge cases:- empty vector, k out of range, non-multiple of 64 lengths.- Precompute and store both inclusive/exclusive conventions consistently.

This two-level scheme is practical, simple to implement, and lets you trade memory vs constant-time performance by tuning S and B.

HardTechnical

98 practiced

Design a segment tree variant for parallel range-sum queries and updates over millions of elements. Discuss memory layout (flat arrays, node packing), sharding ranges across threads, synchronization (locks, lock-free), and strategies to avoid contention when many threads update nearby ranges concurrently.

Sample Answer

Requirements & constraints:- Millions of elements, low-latency range-sum queries & point/range updates, high concurrency across many threads, favor throughput and avoid global bottlenecks.

High-level design:- Use a balanced segment tree stored in a flat array (heap indexing) for compactness and cache predictability. Pack nodes by level to improve spatial locality; store for each node: int64 sum, uint32 version/flags, and padding to 64B to avoid false sharing.

Sharding & work partitioning:- Shard the array into disjoint contiguous index ranges assigned to worker threads (static or load-balanced via work-stealing). Each shard owns the leaves for its range and the upward partial aggregates for internal nodes that are wholly inside the shard. Cross-shard queries/updates touch boundary nodes and require coordination.

Synchronization strategies:- Fine-grained locking: 1 mutex/lock per internal node (or per cache-line group) for correctness. Acquire locks top-down or use hand-over-hand locking for range updates to ensure order and avoid deadlock (lock ordering by index).- Lock-free/optimistic: use atomic fetch-add on node.sum for point updates (propagate up with atomic RMWs). For range updates, use lazy propagation with atomic "lazy" counters at nodes; apply CAS to install lazy deltas and use versioning for readers.- Read-heavy optimization: use versioned reads (read node.sum and version before/after; if versions unchanged it's consistent) to allow wait-free queries most of the time.

Avoiding contention:- Per-thread local buffers (delta logs): threads buffer frequent updates to nearby indices and periodically flush batched increments to the tree (reduces atomic ops and contention). Use timer or size threshold flush; flushing can be parallelized across shards.- Striping & coloring: partition leaves into stripes so concurrent updates to nearby indices map to different stripes; combine with per-stripe locks/atomics.- Flat combining: designate a combiner thread per shard that collects many updates and applies them in one pass to update shared nodes.- Hierarchical merge: maintain per-shard partial trees (local aggregates) and a global top tree over shard summaries. Queries first aggregate shard summaries then consult local trees as needed; updates modify local tree (low contention) and periodically propagate summary changes upward.- Padding & alignment: align node structs to cache-line boundaries; avoid false sharing by placing frequently-updated fields in separate cache lines.

Trade-offs:- Fine-grained locks: simpler, good for mixed workloads but higher overhead under extreme contention.- Lock-free atomics: lower latency for point ops but complex for range lazy propagation and correctness.- Local buffers & hierarchical merge: excellent throughput and low contention at cost of increased read latency/complexity and eventual consistency between shard summaries and leaves.

Metrics & tuning:- Measure flush frequency, combiner latency, and contention hotspots (perf counters). Tune shard size (trade local work vs. boundary hits), buffer sizes, and batching thresholds. Consider using AMD/TSC timestamps or hardware transactional memory (where available) for experiments.

This design balances correctness, throughput, and scalability by combining flat array layout, shard-local structures, batching/combining, and careful synchronization to minimize cross-thread contention.

HardTechnical

91 practiced

Compare the array-based binary heap layout (implicit binary heap in array) vs a pointer-based heap in terms of cache performance, branch misprediction, and practical impact on algorithms like Dijkstra on large graphs. Suggest experiments to measure performance differences and optimizations like d-ary heaps or Eytzinger layout.

Sample Answer

Brief answer: array-based implicit binary heaps (children at 2i+1/2i+2) almost always outperform pointer-based heaps on modern CPUs for large-scale graph algorithms because they have superior cache locality, fewer pointer-chasing branches, and much lower allocation overhead. Pointer-heaps suffer random heap-node addresses (poor spatial locality), extra pointer loads that cause cache-misses and unpredictable branch outcomes, and many small allocations that stress the allocator and TLB.

Key differences:- Cache performance: array layout stores keys/metadata densely, enabling sequential scans, prefetching, and fewer cache lines touched per operation. Pointer heaps scatter nodes and often touch multiple cache lines per decrease-key/pop.- Branch misprediction: implicit heaps use index arithmetic with predictable control flow (less mispredicts). Pointer-based operations branch on pointer-null checks and structure shapes (more unpredictable).- Practical impact for Dijkstra on large graphs: Dijkstra does many decrease-key and pop-min ops. Array-based (or d-ary) heaps reduce memory traffic and CPU stalls, giving large speedups; pointer heaps can be 2x-10x slower depending on graph size and memory locality.

Optimizations and alternatives:- d-ary heaps (d>2): reduce decrease-key cost by shallower tree (fewer comparisons) at the cost of larger branching factor per sift; optimal d depends on cache line size and degree distribution—common: 4-8.- Eytzinger (implicit BFS order) layout: arrange a complete binary search tree in array using implicit heap index but in-order/Eytzinger order to improve prefetchability for searches; useful for search trees more than priority queues but can improve cache behavior in some PQ implementations.- Use flat arrays of structs-of-arrays to minimize fetched bytes, align entries to cache lines, and use manual prefetching.- For Dijkstra, consider radix/bucket queues for bounded integer weights—better locality and O(1) decreases.

Suggested experiments:1) Microbenchmarks: - Implement: (a) implicit binary heap, (b) pointer-based binary heap (allocated nodes), (c) d-ary heap (d=4,8), (d) pairing/fibonacci heap if relevant. - Workloads: randomized insert/extract sequences, heavy decrease-key mix, and pure pops. Measure throughput, instruction counts, L1/L2/L3 cache-miss rates, branch-mispredictions. - Tools: perf (Linux), Intel VTune, valgrind/cachegrind. Collect cycles, cache-misses, branch-mispredicts, CPI.

2) Dijkstra on large graphs: - Graphs: sparse random graphs, road networks (low avg degree, large diameter), web graphs (skewed degree), and worst-case synthetic. - Implement same Dijkstra core but swap heap implementations. Fix memory layout for adjacency to minimize confounding effects. - Metrics: total runtime, time spent in PQ module, L3 misses, TLB misses, GC/allocator time (if managed language), memory footprint. - Scale N from fits-in-L3 to much larger than RAM (to see swapping/TLB effects).

Expected observations:- Array-based and d-ary heaps outperform pointer-based heaps; d-ary often best for Dijkstra on sparse graphs due to fewer sift-ups.- Branch mispredictions and cache-misses correlate strongly with runtime differences.- Eytzinger or cache-aware layouts yield measurable gains in microbenchmarks where traversal/prediction matters.

Practical advice:- Use array-based or d-ary heap for production Dijkstra unless algorithmic constraints require other heaps.- Profile before optimizing; tune d to match cache-line and degree distribution.- In GC languages, reduce allocations (use pools/arrays) to avoid allocator overhead.

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.