Method
hashing
Articles
DS
Data structure
Hash table
Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell.
O(1) on average
2 problems
DS
Data structure
Cuckoo hashing
Two nests per key, a lookup in at most two probes; insertion evicts tenants. Works up to a load of 1/2, with buckets up to 98 %.
lookup at most d probes in the worst case; insertion O(1) on average below the threshold
1 problem
DS
Data structure
Bloom filter
Says “surely not” or “maybe yes” about set membership, at about 10 bits per item.
O(k)
2 problems
PAR
Algorithm
Closest pair of points
The two nearest of n points in n log n: a cut, a strip 2d wide and seven neighbours; with a grid, n on average.
O(n log n)
2 problems
SYS
Algorithm
Consistent hashing
Spreads keys over servers so that adding a server moves only its share.
O(log(N·v)) to find a server
1 problem
SYS
Data structure
Count-Min Sketch
Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards.
O(d) per item and per query
2 problems
SYS
Data structure
HyperLogLog
The number of distinct elements of a stream in a kilobyte of memory: long runs of zeros in hashes and an average over registers.
O(1) per element, O(m) per estimate
2 problems
ML
Algorithm
DBSCAN
Gathers dense regions of points of any shape into clusters and marks lone points as noise.
O(n·Q + Σ|N(p)|)
2 problems
Problems
Often together
interviews 5 in production 5 databases 4 classic 4 membership 3 probabilistic 3 sketch 3 analytics 3 frequencies 2 security 2 randomized 2 nearest neighbour 2