ByteByteGo's common interview algorithms.
Some time ago, Alex Xu posted a list of algorithms that show up in system design interviews. I’m generally interested in system design, and started following Alex after a few brief discussions with him in a private tech writing community. I also enjoyed Alex and coauthor Sahn Lam’s System Design Interview: Volume 2.
Work generally doesn’t include much direct programming for me these days, and have been looking for a well bounded project to spend some time on, so I decided to implement each of those algorithms in a GitHub repository:
repository.
Going into this exercise I had heard of all of these except count-min sketch and hierarchical timing wheels, but quite a few I had never implemented before:
- Geohash – familiar with from Alex/Sam’s book
- Quadtree – familiar with from Alex/Sam’s book
- Consistent hashing – familiar with from many places, I think originally in Cal Henderson’s Building Scalable Web Sites
- Leaky bucket – familiar with and have implemented in an interview
- Token bucket – familiar with but have not implemented
- Trie – familiar with and have implemented in an interview
- Rsync – familiar with CLI but never implemented
- Raft/Paxos – familiar with from numerous papers but haven’t implemented
- Bloomfilter – familiar with from Cassandra but never implement
- Merkle tree – familiar with from Dynamo/Cassandra but never implement
- HyperLogLog – familiar with from Redids but never implement
- Count-min sketch – unfamiliar
- Hierarchical timing wheels – unfamiliar
- Operational transformation – familiar with but haven’t imlpemented
While I’m not confident I’ll ever be in a future interview that directly requires implement any of these specific algorithms, it was still a fun bit of practice that I’d recommend to anyone who’s feeling a bit nostalgic for their programming days. (Or certainly anyone planning to do a systems design interview in the near future.)