Core Data Structures

Choose a lookup structure

You need to find records by key: a static structure, a hash table, a skip list, a B-tree or an LSM-tree? Four questions, each removing more of the design space, then a check of the failure mode.

Choose an ordering structure

A query needs data in order: a heap, an existing order, an in-memory sort, an external sort or a distributed sort? Four questions, starting with how much order you really need.

Choose a sketch

An exact answer is too big to keep: which sketch answers your question (membership, distinct count, frequency, quantile, similarity or a sample), and will it survive merging, duplicates and the questions asked later?

Choose a bit-level structure

A structure is read-mostly and could be packed far smaller: is the saving worth it, and should it be a bitmap, an Elias-Fano list or a packed array with rank/select? Plus when min/max statistics can prune at all.

Hash table load factor: measure the hyperbola

Fill a linear-probing table to α = 0.5 … 0.95, count probes against the formulas, then time it against chaining.

B-tree key order: UUIDv4 versus UUIDv7

Insert 5 million rows under a random UUID key and under a time-ordered key into PostgreSQL; compare index size, page fill, insert time and WAL.

LSM versus B-tree write amplification, derived and measured

Write small rows and 8 KB rows into RocksDB and LMDB, measure device bytes per user byte, then turn on RocksDB blob files.

Monkey-style filter allocation

Split one Bloom-filter memory budget across LSM levels equally or Monkey-style, count wasted I/Os per million missing-key lookups.

Sparse index granule size

Index a sorted file of 100 million records every G records and time point lookups for G from 64 to 65,536.

Sliding maximum: naive, deque and panes

Compute a sliding maximum over a 10,000-value window naively, with a monotonic deque, and with panes; then feed the deque its best and worst shapes.

Top-k with a bounded heap versus a full sort

Find the top 10 of 20 million numbers with sort | head and with a bounded heap; compare time and peak memory, then read DuckDB's plan.

Bloom filter: measure the false-positive curve and the cache cost

Measure a Bloom filter's false-positive rate at 5 to 20 bits per key against the formula, then time lookups in a 10 MB, a 1 GB and a blocked 1 GB filter.

Count-Min Sketch: head versus tail

Count a Zipf stream of 10 million events with a Count-Min sketch, compare head and tail errors, then find heavy hitters with Misra-Gries and Space-Saving.

HyperLogLog: error, merge and the intersection trap

Check HyperLogLog's error over 20 runs, merge two sketches, then estimate a 1% intersection with HLL and with a Theta sketch.

Do not average percentiles

Compute the p99 of 100 shards by averaging shard p99s and by merging KLL, t-digest and REQ sketches, against the exact pooled p99.

Roaring versus plain bitmap versus sorted array

Size sets of row IDs at five densities as a plain bitmap, a sorted array and a Roaring bitmap, then time a 1% intersection in each.

Elias-Fano and the posting-list size

Store a million sorted doc IDs as int32, delta + varint and Elias-Fano; compare size and random-access time.

False sharing: measure the 64-byte penalty

Eight threads increment their own counters: packed in one line, padded to 64 and 128 bytes, and counted locally.

SPSC ring buffer: head and tail on one line, then on two

Move 100 million items through a single-producer single-consumer ring with head and tail on one line, on separate lines, and with batched publishing.

Persistent tree: measure the cost of path copying

Insert a million keys into a mutable and a persistent binary tree; compare time and memory, hold a snapshot, count shared nodes.

Reader-writer lock against plain mutex on a read-heavy workload

99% reads and 1% writes from 1 to 16 threads under a mutex, a reader-writer lock and an atomic snapshot pointer.

Build a pruning cascade and count rows touched

Prune 1,000 point-in-range queries over 10 million rows through a zone map, a Bloom filter and a sparse index; then shuffle the rows.

Interview questions

Short questions on data structures as engines use them, such as hash tables, B-trees, LSM-trees, sorting, sketches, bitmaps and concurrent structures, each with an answer you could give aloud and a link to the full explanation.

Scenarios

Longer problems on choosing and combining data structures, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.