Interview questions

Big-O counts comparisons, but the medium charges for each dependent fetch of its own transfer unit. A B+tree with a fanout of about 680 reaches any of a billion keys in about four page reads, and its top levels stay cached. A skip list pays a separate cache or disk miss for every hop between levels.

Read moreBig-O stops being the judgeB-trees

It says a structure can minimize at most two of read amplification, update (write) amplification and memory (space) amplification; the third gets worse. It is an empirical framing, not a proven theorem, so use it as a forcing question about any design: which of the three did it spend?

Read moreThree currencies

With linear probing, a lookup for a missing key costs about ½ (1 + 1 / (1 − α)²) probes, where α is the load factor: 2.5 probes at α = 0.5, but about 50 at α = 0.9. A probe sequence is a queue for a slot, so the cost follows the same 1 / (1 − ρ) curve as any queue near full utilization.

Read moreThe cost curve is a hyperbola

Both are O(1) on average, but chaining follows a pointer for each collision, a dependent cache miss of about 80 ns, while open addressing checks neighbouring slots in the same cache line, often 16 at a time with SIMD instructions. The real cost model is cache lines touched, not comparisons.

Read moreA cache argument

Not the average number of probes, but their variance. On insert, a key that is far from its home slot takes the place of one that is close to home, so no key ends up very far away and the tail of the distribution collapses. Lookups for missing keys can also stop early.

Read moreRobin Hood hashing

Every key has exactly two candidate slots, so a lookup needs at most two probes. The cost moves to inserts: placing a key may evict another to its alternative slot, and so on in a chain, which can fail and force a full rehash. With four slots per bucket, occupancy can exceed 95%.

Read moreCuckoo hashing

Limit how much of the key-to-slot mapping changes at once: rehash incrementally with two live tables, or use extendible or linear hashing, where buckets split one at a time. Consistent hashing across machines is the same problem, with the cost counted in data moved over the network.

Read moreGrowth is the problem nobody teaches

Fanout = page size ÷ (key + pointer) = 16,384 ÷ 24 ≈ 680. Depth = log₆₈₀(10⁹) ≈ 3.2, so four levels. The root and second level are always cached, so a lookup costs one or two real I/Os.

Read moreThe constraint derived

Random keys insert everywhere, splitting pages all over the tree and leaving them about 69% full, about 45% space overhead, with a random page write per insert. Time-ordered keys append at the right edge and fill pages completely, but create one hot page and one contended latch. You have converted a space cost into a contention cost.

Read moreKey order relocates cost

No; compare write amplification. A B-tree rewrites a page per row changed: 16 KB / 200 B ≈ 80. A leveled LSM rewrites each byte about T × L times, about 30 with size ratio T = 10 and L = 3 levels. But with 8 KB rows the B-tree's figure is 2, and the LSM loses by about 15×. Separating large values from keys fixes that case.

Read moreCorrect the folklore

With size ratio T and L levels: leveled compaction writes each byte about T × L times, a read touches about L sorted runs, and space overhead is about 1 + 1/T. Tiered writes about L times, reads touch up to T × L runs, and space can reach T. The size ratio T is one dial across all three costs.

Read moreThe amplification arithmetic

Range scans. Bloom filters cannot help a range predicate, so a scan must merge iterators across every sorted run: L of them with leveled compaction, up to T × L with tiered. A B+tree simply walks its linked leaf pages.

Read moreWhere the LSM genuinely loses

With a fixed memory budget, the goal is to minimize the sum of false-positive rates across levels, and the optimum gives each level a rate proportional to its number of keys. The largest level holds most keys, so making its filter tighter is the most expensive. This allocation (Monkey: about 4.8 fewer bits per key per level at T = 10) removes the factor L from the cost of a lookup.

Read moreThe filter allocation result

A trie's depth equals the key length, not something you can tune to the medium's transfer unit. Sixteen dependent steps take about 1.3 µs in memory but about 1.6 ms on disk. The adaptive radix tree (ART) makes tries practical in memory, with node sizes that adapt to their number of children and compressed paths.

Read moreA trie is a memory structureWhat ART fixes

Not for speed but for concurrency. An insert changes only a few local pointers, each with one compare-and-swap, and never rebalances the structure, so many threads can insert without locks.

Read moreSkip list

Two lower bounds: the index must fit in memory, so granule ≥ rows × entry size ÷ memory budget; and a granule must be at least the medium's minimum efficient read. For 10¹² rows, 16-byte entries and 4 GB of memory, that is at least 4,000 rows; ClickHouse rounds to 8,192.

Read moreThe granule size is pinned by two inequalities

For a fixed set of keys, it maps each key to its own slot with one probe, in about 1.44–3 bits per key, without storing the keys. But it cannot tell you whether a key is in the set: an unknown key maps to some arbitrary slot. Add a stored fingerprint to check.

Read morePerfect hashingThe catch

Each file's [min, max] is an interval. If files are written in arrival order and the filtered column is unrelated to arrival time, every file's interval spans nearly the whole domain, so every query overlaps every file. Pruning depends on how intervals overlap, which makes clustering an indexing decision.

Read moreInterval trees

A heap that keeps only the best k items answers it exactly in O(n log k) time and O(k) memory, so it never spills to disk. The question asked for less than a full order, and the plan should use that.

Read moreTop-N

About N log k comparisons for N items from k sorted inputs. It is the core of external-sort merges, LSM compaction, merge joins and ordered reads across partitions of a topic. Compaction policy sets k for LSM reads, so it is really a read-cost decision.

Read moreThe k-way merge and its cost

Sample the keys to choose range boundaries, send each range to one worker, sort each range independently, and define the global order as the ranges concatenated. It is only as good as the sample: with skew, one range gets far more data, and the stage takes as long as its slowest task.

Read moreDistributed sort is a partitioning problem

A sum is invertible: subtract the value that leaves the window. A max is associative but not invertible, so keep a monotonic deque, or combine per-pane maxima. A median or a distinct count is holistic: it needs the whole window, or a sketch that approximates it.

Read moreMonotonic queues and deques

No false negatives: if it says "no", the key is definitely absent. It can give false positives, at a rate you choose. Used as a guard in front of a lookup, an error costs a wasted read, never a wrong answer.

Read moreBloom filter

With the optimal number of hash functions, about 1.44 · log₂(1/ε) bits per key: 9.6 bits for a 1% rate, and every extra 4.8 bits divides the rate by ten. The optimal number of hash functions is k = (m/n) · ln 2, for m bits and n keys.

Read moreThe derivation

A filter replaces a lookup in the tier it guards with a probe in memory, so its value is the latency ratio between them: about 100,000× for a spinning disk, about 1,000× for NVMe, and about 1× for a table already in memory, where it is pure overhead.

Read moreWhat a filter is actually worth

A plain filter's k probes are k random cache misses, about 500 ns for seven. A blocked filter keeps all of a key's bits in one 64-byte block, so a lookup costs one miss, at the price of 10–20% more bits for the same false-positive rate.

Read moreThe real cost in production is cache misses

• Bloom: about 44% above the information-theoretic minimum, the price of supporting inserts one at a time.
• Cuckoo: supports deletes and two-probe lookups, but an insert can fail, and it saves space only below about a 3% false-positive rate.
• XOR (and ribbon): about 1.23× the minimum, but needs the whole key set up front, which suits immutable files.

Read moreBloom is 44% above the floorCuckoo filterXOR and ribbon filters

It overestimates any item's count by at most ε · N with probability 1 − δ, where N is the total number of items in the stream. That is fine for frequent items and meaningless for rare ones: with N = 10⁹ and ε = 0.001, the error can be a million.

Read moreCount-Min Sketch

It hashes each item, splits the hashes into buckets, and keeps, per bucket, the longest run of leading zeros seen; a run of ρ zeros suggests about 2^ρ distinct items. It combines the buckets with a harmonic mean. With 16,384 six-bit registers (12 KB), the error is 1.04 / √m ≈ 0.81%.

Read moreHyperLogLog

Merging is an element-wise max of registers, which gives exactly the sketch of the union. An intersection has to be computed by inclusion–exclusion (|A| + |B| − |A ∪ B|), where the errors of large numbers add up and can exceed a small answer. Use Theta sketches when intersections matter.

Read moreHyperLogLogTheta sketch and KMV

A Theta sketch keeps the k smallest hash values it has seen, which are coordinated samples across sketches. That makes union, intersection and difference all possible, with unbiased estimates. It buys a full set algebra with extra space.

Read moreTheta sketch and KMV

Inserting the same item twice leaves the sketch unchanged, as with HyperLogLog, Bloom filters, Theta and MinHash. So duplicate deliveries from an at-least-once pipeline do no harm. Counting sketches (Count-Min, t-digest, reservoir samples) are not idempotent and need deduplication or exactly-once delivery.

Read moreTwo classifications

Two p99 values do not contain the information needed to compute the p99 of the combined data. Percentiles do not compose. Store a mergeable digest per shard (t-digest or KLL), merge the digests, then read the quantile.

Read moreQuantile sketches

KLL has a proven, uniform bound on rank error and merges fully. t-digest is much more accurate in relative terms at the extremes, p99 and p99.9, but its accuracy is only shown empirically, with no bound.

Read moreQuantile sketches

Without assumptions about the distribution, it provably needs a sample almost as large as the data: a sample cannot tell whether unseen items are repeats or new. That is why HyperLogLog and KMV were invented.

Read moreReservoir sampling

A pair with Jaccard similarity J becomes a candidate with probability 1 − (1 − J^r)^b, an S-curve whose threshold sits near (1/b)^(1/r). With b = 16 and r = 8 it is about 0.71; raise r to move the threshold up. Below it, true duplicates are missed, so recall is a design choice.

Read moreSimHash and LSH

Misra-Gries or Space-Saving: smaller, deterministic, with error at most N/k for k counters. Use Count-Min only if you also need counts for arbitrary items. Neither guarantees the order of items within the top K.

Read moreTop-K and heavy hitters

Encodings (dictionary, run-length, bit-packing, delta) understand the data's structure and can often be queried without decoding. Codecs (LZ4, Zstd) compress opaque bytes and must be decompressed before anything can be read. Columnar formats apply encodings first, then a codec.

Read moreEncoding versus compression

For each chunk of 65,536 rows, an array of positions costs 16 bits per set row, and a bitmap costs 65,536 bits whatever it holds. They break even at 4,096 set rows, so Roaring picks whichever is smaller per chunk. That removes the old rule that bitmap indexes suit only low-cardinality columns.

Read moreBitmap indexes and Roaring

rank(i) counts the 1s before position i; select(k) finds the position of the k-th 1. Both can run in constant time with 3–25% extra bits, and they give addressing inside compact layouts: skipping nulls, locating variable-length strings, navigating succinct trees.

Read moreBit vectors and rank/select

It packs the low bits of each number (log₂(u/n) bits each, for n numbers drawn from a universe of u) and stores the high bits in unary in a bit vector of about 2n bits: n (2 + ⌈log₂(u/n)⌉) bits in total, with random access through select. A million IDs out of a billion take about 12 bits each, 1.5 MB.

Read moreSuccinct data structures

Coordination costs grow faster than linearly. In the Universal Scalability Law, the coherency cost β grows with N², so throughput peaks at N* = √((1 − α) / β) threads and then falls, where α is the share of contention.

Read moreThe currency is coordination

Two cores write different variables that happen to share one 64-byte cache line, so the line bounces between their caches at 40–100 ns per transfer, against about 1 ns for an uncontended increment. Pad the variables onto separate lines, or count locally and write once.

Read moreThe contention is physical

Do not share (partition so each piece of data has a single writer), do not mutate (publish immutable versions), and gamble and retry (optimistic concurrency). Prefer them in that order, all ahead of locking: the first two remove contention, while optimism and locks only put a price on it.

Read moreThree ways not to coordinate

Each memory location has one writer, so nothing needs arbitration, only ordering. The producer owns the tail index and the consumer owns the head; plain loads and stores with release/acquire ordering are enough.

Read moreSPSC: the purest case

Mostly from layout. Putting the head and tail indices on separate cache lines gives about 10× more throughput, and publishing several items at once spreads one cache-line transfer over all of them.

Read moreFalse sharing and paddingBatch the publication

Fetch-and-add. A compare-and-swap loop fails and retries under contention, at a rate that grows like 1 / (1 − ρ). Fetch-and-add never fails, because the hardware serializes the callers, which also makes claiming a slot wait-free.

Read moreMPSC: the choice of primitive

Not in general. An uncontended lock costs about 20 ns, and under heavy contention failed lock-free retries burn CPU, so p99.9 can be worse than with a good mutex. What lock-free buys is immunity to one descheduled thread holding a lock and stalling everyone. Choose it for predictability, not speed.

Read moreProgress guarantees

Blocking guarantees nothing if the lock holder is preempted. Lock-free guarantees that some thread always makes progress. Wait-free guarantees that every thread finishes in a bounded number of steps, and it is the only one of the three that bounds tail latency.

Read moreProgress guarantees

With Little's Law: depth = arrival rate × the backlog time you are willing to accept. For 2 million items per second and 5 ms, that is 10,000 slots. When the queue is full, that is backpressure working, not a failure.

Read moreWhere this lives in data engineering

Lookups only read and inserts need one compare-and-swap, but a resize changes the key-to-bucket mapping of the whole table while other operations continue. Java 8's map migrates bins one by one, leaving forwarding nodes behind; split-ordered lists arrange keys so that doubling the table moves no data at all.

Read moreResize is where the complexity goes

Taking the read lock writes to a shared counter, so every reader invalidates every other reader's copy of that cache line. A reader that writes does not scale. Use per-core counters, sequence locks, RCU or immutable snapshots instead.

Read moreA reader that writes does not scale

Each update copies the path from the changed node to the root, and on one thread such structures are roughly 2–10× slower and larger than mutable ones. In exchange, readers need no synchronization at all, and a writer publishes with a single compare-and-swap on the root.

Read moreImmutable and persistent structuresWhy they win

They are all persistent structures: new versions share their unchanged parts with old ones, a root pointer is swapped atomically, old roots give consistent snapshots, and a collector removes versions nothing can reach any more.

Read moreThe same idea at every scale

Another thread may hold a pointer to it that it read a moment ago. Removal is easy; reclaiming the memory safely needs a protocol (hazard pointers, epochs, RCU) or a garbage collector.

Read moreThe problem stated precisely

Hazard pointers bound memory but make readers expensive. Epoch-based reclamation makes readers cheap, but memory grows without bound if one thread stalls. RCU makes readers nearly free but needs grace periods and a definition of when a thread is quiescent. You can pick two of cheap readers, bounded memory and simplicity.

Read moreThree protocols and the trade-off they form

Both are a slow reader blocking a collector. Memory reclamation, or vacuum, cannot get past the oldest participant, so space grows without bound for as long as it is stuck.

Read moreThe same question at every scale

The pruning cascade (cheap filters in front of expensive reads), the buffer–runs–merge write path (as in an LSM-tree), the columnar stack (encodings, then codecs, then statistics), and partition–localize–merge (as in distributed aggregation).

Read moreThe compositions matter more than the pieces

Each stage may only have false positives, since a false negative would drop real results; and each must be cheaper than the stage it guards, otherwise you would just run the guarded stage. Those two constraints fix the order.

Read moreThe pruning cascade

Encodings keep the data queryable without decompressing it; byte-level codecs do not. Encoding first also hands the codec more regular input.

Read moreThe columnar stack

A wrong bet about how the data will be accessed gives a cliff, not a slope: a spill to disk, a full scan, a retry storm, or one skewed task in a partitioned job.

Read moreThis mechanism in one frame