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

85 practiced

Implement a Binary Indexed Tree variant to support range_add(l, r, delta) and point_query(i) in O(log n) time. Provide code and explain how the variant differs from the standard BIT and why it allows range updates.

Sample Answer

To support range_add(l, r, delta) and point_query(i) in O(log n), use a Fenwick tree that stores differences: perform +delta at l and -delta at r+1. A point query is then the prefix sum up to i which equals accumulated deltas affecting that point.

python

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, idx, val):
        # internal point-add to BIT (1-indexed)
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx

    def _sum(self, idx):
        # prefix sum query
        s = 0
        while idx > 0:
            s += self.bit[idx]
            idx -= idx & -idx
        return s

    # Public APIs (1-indexed positions)
    def range_add(self, l, r, delta):
        if l > r: return
        self._add(l, delta)
        if r + 1 <= self.n:
            self._add(r + 1, -delta)

    def point_query(self, i):
        return self._sum(i)

Why it works:- We store difference array D where D[i] = A[i] - A[i-1]. Adding delta to [l..r] updates D[l]+=delta and D[r+1]-=delta. The original value A[i]=sum_{k<=i} D[k], so point_query is prefix sum on D.Key points:- Time: O(log n) for both operations. Space: O(n).- Edge cases: use 1-indexing or convert 0-indexed inputs; handle l>r; ensure r+1 within bounds.- Compared to standard BIT (which typically supports point_add & prefix_sum), this variant uses the BIT over the difference array to turn range updates into two point updates.

MediumTechnical

92 practiced

As an SRE optimizing a critical in-memory index, compare contiguous array-based layouts versus pointer-based (linked) structures. Discuss cache locality, memory overhead, allocation patterns, fragmentation, GC impact, and how each choice affects tail latency under high load. Provide concrete examples and metrics to measure.

Sample Answer

Short answer: contiguous array-based layouts (arrays, flat structs, packed buffers) almost always give better cache locality, lower CPU per lookup, and lower tail latency than pointer-based linked structures; linked structures can be simpler for dynamic inserts but pay heavy costs in cache misses, memory overhead, allocation churn, fragmentation and GC pressure — all of which worsen tail latency under load.

Comparison (concrete):

- Cache locality - Array: sequential memory, prefetch-friendly, high L1/L2 hit rate. Example: scanning 1M fixed-size records yields ~2–5× fewer L1 misses vs pointers. - Linked: pointers scatter nodes → many random accesses, higher cache-miss penalty (50–200ns extra per miss).

- Memory overhead & allocation patterns - Array: compact (no per-node header), low pointer overhead; one large allocation reduces allocator overhead. - Linked: per-node allocator metadata + pointer fields (8–16 bytes/node). High allocation rate if nodes created individually → allocator contention.

- Fragmentation & GC impact - Array: single slab reduces fragmentation; in GC languages, fewer objects = fewer tracing/pause costs. - Linked: many small objects increase fragmentation; in tracing GCs, more live objects → longer pauses and increased p99 latencies.

- Tail latency under high load - Array: predictable latency; p95/p99 driven mainly by CPU and cache pressure. Under load, tail less volatile. - Linked: p99 can spike due to cascading cache misses, allocator locks, and GC pauses.

Practical patterns & mitigations:- Use contiguous arrays or flatbuffers for read-heavy indexes; use segmentation (chunked arrays) for efficient incremental growth.- If pointers needed, use object pools/slab allocators or arena allocation to group nodes and improve locality.- Use cache-aware layouts: struct-of-arrays vs array-of-structs depending on access pattern.

Metrics & tools to measure:- Latency histograms (p50/p95/p99) and tail SLO breaches (Prometheus + histograms).- CPU cycles/op (perf, VTune), L1/L2 miss rates (perf stat, Intel PMU).- Allocator metrics: allocation rate, malloc contention (jemalloc stats, tcmalloc).- Memory fragmentation and RSS (smaps, jemalloc_malloc_stats).- GC metrics: pause times, heap size, GC CPU (runtime/GC traces, jvm/gc logs).- Profiling: flamegraphs, heap/alloc profiles (pprof, heaptrack).- End-to-end: run load tests (wrk, vegeta, custom harness) comparing layouts; measure p99 and allocate/GC rates.

Example measurement experiment:- Implement index as flat array vs linked nodes; populate 10M entries; run 1000 concurrent read-heavy queries.- Measure: p99 latency, L1/L2 miss/sec, malloc/sec, GC pause total.- Expectation: array: ~30–60% lower p99, 3–10× fewer L1 misses, orders-of-magnitude lower malloc/sec and smaller GC pause time.

Conclusion: prefer contiguous layouts for hot in-memory indexes; if dynamic updates force pointer-based designs, mitigate with arenas/slabs and compacting strategies and measure the metrics above to ensure SLOs.

HardSystem Design

79 practiced

Design a storage format and access layer for a web-scale directed graph (billions of nodes, tens of billions of edges) optimized for adjacency queries and traversals using limited memory. Discuss representations (CSR, Elias-Fano, WebGraph compression), random vs sequential access trade-offs, partitioning, and caching strategies.

Sample Answer

Requirements & constraints:- Billions of nodes, tens of billions of directed edges; memory limited (GBs per host).- Optimize adjacency queries (out-neighbors/in-neighbors) and breadth-first/DFS-style traversals.- High availability, predictable latency, good throughput; SRE must monitor, autoscale, and bound tail latency.

High-level design:- Store compressed adjacency lists on disk across a cluster, expose an access layer that serves adjacency and traversal primitives with caching, prefetching, and streaming APIs.

Representations (pros/cons):- CSR (compact, sequential layout): store two arrays — offsets and concatenated neighbor lists. Excellent sequential scan for traversal; random single-node lookup requires one index lookup (offset) then read slice. Offsets can be 64-bit per node; large but predictable.- Elias–Fano for monotone neighbor lists: very space-efficient for sorted neighbor IDs and supports fast select/rank; good for random access to k-th neighbor and iteration; CPU cost higher.- WebGraph-style delta + variable-byte + block-wise compression: extremely good compression for web-like graphs; supports block decompression for locality; best for sequential scans, random single-neighbor reads require decompressing a block.

Random vs sequential access trade-offs:- Sequential traversals: favor CSR or block-compressed WebGraph — stream blocks, minimal CPU.- Random single-node adjacency: prefer CSR + memory-mapped offsets or Elias–Fano for smaller RAM. WebGraph needs block decompression (higher latency) but good when many adjacent accesses hit same block.

Partitioning & placement:- Range- or hash-based partition by source node (outgoing adjacency colocated). For locality-aware workloads, do METIS/LDG graph partitioning to reduce cross-shard edges.- Store each partition as CSR/blocked-compressed files. Maintain replica partitions (R = 2–3) across failure domains for HA.- Co-locate high-degree “celebrity” nodes into separate shards or store their adjacency in specialized hot-store to reduce hotspotting.

Access layer & caching:- Node offsets in-memory: keep compact offset index (e.g., 8B/node) memory-mapped across hosts; if too big, sample + second-level index or Elias–Fano for offsets.- Block cache: LRU or segmented LRU on decompressed blocks (tuned by traversal pattern). Cache hot adjacency lists in DRAM (per-node small cache for frequent queries).- Frontier streaming for traversals: keep frontier on client side and request partitions in batch to maximize sequential reads and prefetch next blocks.- Prefetch engine: detect sequential scans within a partition and issue async reads of following blocks.- Bloom filters / small learned index per partition to quickly reject non-existent nodes/edges before disk IO.

Operational & SRE considerations:- Expose metrics: cache hit/miss, IO latency, decompression CPU, per-partition QPS, contention. Set SLOs on p99 adjacency latency and traversal throughput.- Autoscaling: scale partition-serving replicas based on CPU (decompression), IO wait, and cache pressure. Use rate-limiting and backpressure for large traversals.- Backups & consistency: partitions are immutable snapshots (append-on-update) so simple snapshot/replication works; support compaction jobs to rebuild compressed layouts.- Fault tolerance: detect slow/failed replicas; redirect to replicas. Monitor hot-node skew and add read-only replicas for read-heavy celebrities.

Example traversal pattern:- BFS layered traversal: client collects current frontier, groups by partition, issues batched adjacency requests; server streams compressed blocks; client applies dedupe/filter (use bloom filters to reduce repeats). This keeps memory low (store frontier + small visited bitset partitioned on disk or external store).

Trade-offs:- Max compression (WebGraph) saves storage and IO but raises CPU and random-read latency.- Elias–Fano balances random access and space but is more complex to implement.- CSR is simplest and fastest for sequential scans but larger index RAM.

Summary:- Use partitioned block-compressed storage (WebGraph-like) for disk efficiency, keep a compact in-memory index (offsets via memory-map or Elias–Fano), implement block cache + prefetch, special-case high-degree nodes, and equip SRE tooling (metrics, autoscale, backpressure, compaction) to meet reliability and latency SLOs.

MediumSystem Design

91 practiced

Design a concurrent hash map for high-throughput SRE use. Requirements: support 10k+ ops/sec, per-key concurrency, low contention, consistent reads. Discuss locking strategies (per-bucket locks, striping), lock-free options, memory reclamation (hazard pointers, epoch), and how you'd benchmark under contention.

Sample Answer

Requirements clarification:- 10k+ ops/sec sustained, per-key concurrency (parallel ops on different keys), low contention, consistent reads (linearizable or at least read-after-write for a key), production-safe memory reclamation, observability for benchmarking.

High-level design:- Use a sharded hash map: an array of buckets each holding a small lock-protected chain/tree. Map-level hash → shard index → bucket. Shards reduce global contention; per-bucket (or per-key) locking gives fine-grained concurrency.

Locking strategies:- Per-bucket locks: simplest, use a mutex per bucket. Good when keys are well-distributed. Keep bucket critical sections minimal (only mutate pointers/values).- Lock striping: map many buckets to fewer locks (e.g., 64–256 stripes) to reduce memory overhead while lowering contention vs. single global lock.- Per-key locks: use a secondary concurrent lock map (e.g., lock per key via hashed lock table) or embed a small spinlock in bucket nodes for ultra-fine-grained control—best for hot-spot mitigation.

Optimistic/Read strategies for consistent reads:- Read-copy-update (RCU) / versioned pointers: reads proceed without locks by reading an atomic pointer plus a version number; writers replace nodes with CAS and update version. Ensures wait-free reads and low latency.- Or use a reader-writer lock per bucket with writer preference tuned to writes frequency.- For linearizable reads, perform an atomic load of the value pointer; for read-after-write guarantee, ensure writer publishes with a memory barrier.

Lock-free options:- Lock-free hash tables using CAS on bucket heads and lock-free linked lists (Michael-Scott lists) or hopscotch hashing. These give high concurrency but are significantly more complex and error-prone and require careful memory reclamation.

Memory reclamation:- Hazard pointers: each reader publishes pointers it may access; reclamation defers freeing until no hazard pointer references the node. Good for predictable latency but has per-thread state overhead.- Epoch-based reclamation (EBR): threads enter/exit epochs; nodes removed in epoch N are freed once all threads have advanced past N. Lower overhead than hazard pointers, simple and fast for SRE contexts, but sensitive to stalled threads.- For lock-free designs prefer hazard pointers or EBR; for locked designs, standard refcounting or GC-like schemes may be adequate.

Practical recommendation for SRE:- Implement sharded hash map (e.g., 256 shards) with per-bucket mutexes + optimistic atomic reads (atomic pointer to value). Use epoch-based reclamation to reclaim removed nodes safely. For very hot keys add per-key spinlocks or an adaptive backoff to reduce contention.

Benchmarking under contention:- Use YCSB-style synthetic workloads covering: - High read-heavy (95/5), balanced (50/50), and write-heavy. - Key distributions: uniform, Zipfian (to create hot keys), small/large keyspace to vary contention. - Thread scaling: 1..N threads where N equals core count.- Metrics: throughput (ops/sec), latencies (p50/p95/p99), CPU utilization, kernel context switches, lock contention stats, cache-misses.- Tools: custom C++/Go microbench with timers + perf/ebpf for lock contention/counts; jemalloc or heap profiler for memory churn.- Experiments: compare striping levels, shard counts, and lock-free variant; measure effect of epoch reclamation frequency and stalled-thread sensitivity.- Failure/testing: inject thread pauses to validate EBR behaves; test long-running GC/reclamation effects.

Trade-offs:- Stripes/shards reduce contention at modest memory cost; lock-free offers best concurrency but hard to get right and harder to maintain/debug.- EBR is easier and performant; hazard pointers safer for per-node safety under arbitrary thread suspension.- For SRE, favor maintainability: sharded map + atomic publishes + EBR provides high throughput with predictable behavior; reserve lock-free only when benchmarks prove necessity.

MediumTechnical

71 practiced

Implement a min-priority queue in Java that supports decreaseKey(node, newKey) in O(log n) time, plus extractMin and insert. Explain how you map nodes to positions (index map) and how you handle duplicate keys or node identity efficiently.

Sample Answer

Approach: implement a binary min-heap backed by an ArrayList of Node entries and maintain an indexMap (HashMap<NodeId, index>) mapping each node’s unique identity to its position in the array so decreaseKey can locate the element in O(1), then bubble-up in O(log n). Use a Node class that contains id and key; treat id as the node identity (not key) so duplicate keys are allowed. For tie-breaking we don't need extra rules since heap order uses key only.

java

import java.util.*;

public class MinPriorityQueue {
    static class Node {
        final String id; // unique identity (e.g., vertex name)
        long key;
        Node(String id, long key) { this.id = id; this.key = key; }
    }

    private final List<Node> heap = new ArrayList<>();
    private final Map<String, Integer> indexMap = new HashMap<>(); // id -> index

    public boolean isEmpty() { return heap.isEmpty(); }

    public void insert(String id, long key) {
        if (indexMap.containsKey(id)) throw new IllegalArgumentException("Duplicate id");
        Node n = new Node(id, key);
        heap.add(n);
        int i = heap.size() - 1;
        indexMap.put(id, i);
        siftUp(i);
    }

    public Node extractMin() {
        if (heap.isEmpty()) return null;
        Node min = heap.get(0);
        Node last = heap.remove(heap.size() - 1);
        indexMap.remove(min.id);
        if (!heap.isEmpty()) {
            heap.set(0, last);
            indexMap.put(last.id, 0);
            siftDown(0);
        }
        return min;
    }

    public void decreaseKey(String id, long newKey) {
        Integer idx = indexMap.get(id);
        if (idx == null) throw new NoSuchElementException("Node not found");
        Node n = heap.get(idx);
        if (newKey >= n.key) throw new IllegalArgumentException("newKey not smaller");
        n.key = newKey;
        siftUp(idx);
    }

    private void siftUp(int i) {
        while (i > 0) {
            int p = (i - 1) >>> 1;
            if (heap.get(p).key <= heap.get(i).key) break;
            swap(i, p);
            i = p;
        }
    }

    private void siftDown(int i) {
        int n = heap.size();
        while (true) {
            int l = (i << 1) + 1, r = l + 1, smallest = i;
            if (l < n && heap.get(l).key < heap.get(smallest).key) smallest = l;
            if (r < n && heap.get(r).key < heap.get(smallest).key) smallest = r;
            if (smallest == i) break;
            swap(i, smallest);
            i = smallest;
        }
    }

    private void swap(int i, int j) {
        Node a = heap.get(i), b = heap.get(j);
        heap.set(i, b); heap.set(j, a);
        indexMap.put(a.id, j);
        indexMap.put(b.id, i);
    }
}

Key points:- Index map maps immutable node id to current index; constant-time lookup for decreaseKey.- Node identity is the id field, so duplicate keys are allowed; indexMap prevents duplicate ids.- decreaseKey updates the stored key and performs siftUp to restore heap property.Complexity: insert O(log n), extractMin O(log n), decreaseKey O(log n), with O(n) space.Edge cases: inserting existing id (reject), decreaseKey with larger newKey (reject), extractMin on empty returns null. This structure is well-suited for Dijkstra-like SRE tasks (service graphs, resource priorities) where nodes represent unique resources.

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.