# Algorithms

Algorithm explanations and walkthroughs.

- [Binary Search](https://scaleengineer.com/algorithms/binary-search)
  - Binary Search is a searching algorithm that finds a target in a sorted, randomly-accessible sequence by repeatedly halving the candidate range.
- [Bloom Filter](https://scaleengineer.com/algorithms/bloom-filter)
  - Three hashes set three bits per word. A 0 bit is a definite no, a full row of 1s only a maybe.
- [Consistent Hashing](https://scaleengineer.com/algorithms/consistent-hashing)
  - Nodes and keys share one hash ring, and a key walks clockwise to the first node. A node leaving moves only its own arc.
- [LRU Cache](https://scaleengineer.com/algorithms/lru-cache)
  - Every use moves its key to the front of a recency list, and eviction takes the tail. A hash map plus a doubly-linked list keeps both steps O(1).
- [Merge Sort](https://scaleengineer.com/algorithms/merge-sort)
  - Efficient, general-purpose, comparison-based, canonical divide-and-conquer  sorting algorithm: split the array in half, recursively sort each half, then merge the two sorted halves into one.
- [Merkle Tree](https://scaleengineer.com/algorithms/merkle-tree)
  - Hash each block, then hash the pairs upward until one root remains. The root commits to every byte, and log n sibling hashes prove any block.
- [Skip List](https://scaleengineer.com/algorithms/skip-list)
  - A sorted linked list plus express lanes. Searches ride the fast lanes down, and coin flips on insert keep the lanes balanced.
- [Token Bucket](https://scaleengineer.com/algorithms/token-bucket)
  - Requests spend tokens, time refills them, and an empty bucket says no. A rate limiter in two rules.