Design 21: Randomness in Computing

Theme

A lot of the code I write is deterministic. Most of the time, I don’t encounter randomness unless I’m using a random number generator or sampling from a list. This made me curious about data structures and algorithms that use randomness as part of their design.

Load balancing systems may use randomization to spread traffic between nodes. Automatic API retries usually include jitter to prevent clients from retrying all at the same time. Logging systems often randomly sample requests instead of recording every request to reduce storage. Python’s dictionaries and sets use randomized hash seeds to make adversarial hash collisions much harder.

Grid

HyperLogLog, Quicksort, Quickselect, and Monte Carlo largely determined the grid’s structure. Remaining answers, such as Reservoir, Count-Min, and Las Vegas, occupied a lot of space and were difficult to find good intersections.

Overall, I wasn’t able to make the grid as pretty as I wanted. Many of the answers ended up stacked against one another, which I’m not happy about. I also truncated Bloom Filter to Bloom and removed Rabin–Karp. However, this allowed me to include the answers I wanted.

Thankfully, I was able to keep the grid balanced, with 7 across and 8 down answers.

Clues

I particularly enjoyed writing clues for Bloom, Skip List, HyperLogLog, Count-Min, MinHash, t-Digest, and Reservoir because these are data structures and algorithms I don’t typically encounter.

I like how randomness is fundamental to making them efficient, and how they rely on ideas such as hashing and sampling. Popular tools like Redis, Elasticsearch, and Apache Spark rely on many of the same techniques.

Furthermore, reading more about t-Digest made me think specifically about percentile dashboards in Grafana and Datadog. I hadn’t realized those types of metrics rely on algorithms like this behind the scenes.

Tradeoffs

This is a bit of a specialized puzzle since many of the data structures and algorithms aren’t as broadly discussed compared to more traditional data structures like stacks, lists, and queues.

However, I thought the topic was interesting because it feels like a departure from how I typically think about programming. I usually think about programs deterministically and rarely need to introduce randomness to solve the kinds of problems I encounter.

Notes

I enjoyed working on this puzzle because it made me think more about how algorithms work when perfect accuracy isn’t necessary and approximate results are acceptable in exchange for better performance or lower memory usage.