Method
randomized
Articles
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
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
GEO
Algorithm
Delaunay triangulation and Voronoi diagram
Zones of the nearest point and triangles with empty circles: two sides of one structure.
O(n log n) on average
2 problems
SYS
Technique
Retry with jitter
The pause before a retry doubles and is chosen at random: clients spread out in time and do not hit the server in waves.
O(1) per pause decision
2 problems
ML
Algorithm
k-means
Splits points into k groups so that points sit close to the centre of their group.
O(n · k · d) per step
2 problems
Problems
Often together
classic 4 points 3 interviews 3 hashing 2 nearest neighbour 2 geodata 2 membership 1 graph 1 divide and conquer 1 deduplication 1 polygon 1 maps and navigation 1