The Ancients
Before "algorithm" was a word engineers used
Written in 20 minutes on a napkin in a café in Amsterdam. Dijkstra needed to find the shortest route between two Dutch cities for a computer demonstration. He didn't use paper, no pencil - just pure thought. The result was an algorithm so elegant it still powers Google Maps, OSPF routing, and every GPS system 70 years later.
Key Insight: The best algorithms are discovered by asking the right question, not the complicated one. "What is the shortest path?" is the question. The answer is a priority queue and greedy expansion.
Donald Knuth began writing what would become the Bible of computer science in 1962. Volume 3, "Sorting and Searching," catalogued every known sorting algorithm with precise mathematical analysis of time and space complexity. Before Knuth, engineers guessed. After Knuth, they measured. This is the direct ancestor of Big-O notation as a disciplined practice.
Key Insight: You can't improve what you don't measure. Big-O notation gave us a language to compare algorithms objectively. Every interview question about time complexity traces back to Knuth's rigorous framework.
Stack, Queue, and HashMap are the three data structures every algorithm builds on. Level 4 (HashMap) is you implementing the hash table from scratch - the same O(1) lookup that Luhn and Morris designed.
The Cache Revolution
Every millisecond of latency saved is money earned
Maurice Wilkes noticed that CPU speed was increasing much faster than memory speed. His solution: a small, very fast memory between the CPU and main RAM. Caches work because of "locality of reference" - programs tend to access the same memory addresses repeatedly (temporal locality) and nearby addresses (spatial locality). The same principle powers every CDN today.
Key Insight: Programs have predictable memory access patterns. Exploit them. This is why Redis works: your hot data fits in 10% of your dataset. Cache the 10%, serve 90% of requests without touching the database.
With limited cache space, which item do you evict when the cache is full? IBM Research proved that Least Recently Used (LRU) eviction approximates optimal performance for most real workloads. The intuition: if you haven't used something recently, you probably won't need it soon. The famous Belady's algorithm proved optimal but is impossible to implement online (it's future-predicting).
Key Insight: LRU is the single most frequently asked "implement from scratch" question in senior engineering interviews at FAANG. Not because it's hard - but because the O(1) solution (doubly-linked list + hashmap) reveals whether you think in data structures.
Level 7 is the classic LRU Cache interview question. Level 24 is the harder LFU variant. Every time you use Redis, Memcached, or a CDN, these two algorithms are running. Now you'll build them.
The Probability Machine
When exactness is too expensive, approximate wisely
Burton Bloom asked: what if we allow a small probability of false positives in exchange for using almost no memory? A Bloom filter uses k hash functions and a bit array. When inserting, set k bits. When querying, check k bits - if ALL are set, the element is PROBABLY in the set. If ANY is not set, the element is DEFINITELY not. No false negatives, tunable false positives.
Key Insight: Bloom filters power Google BigTable, Cassandra, PostgreSQL (to avoid disk reads for non-existent rows), browsers (Safe Browsing checks), and CDNs. The question "is this URL malicious?" is answered by a Bloom filter before any network call.
Balanced BSTs (AVL, Red-Black) are fast but complex to implement correctly. William Pugh invented a probabilistic alternative: a linked list with multiple "express lane" pointers. Each node is promoted to higher lanes with probability p (usually 0.5). The result: O(log n) average search, insert, delete - but with elegant implementation. Redis's sorted sets use a Skip List.
Key Insight: Sometimes randomness beats determinism for simplicity. Redis chose Skip Lists over balanced trees because "the code is simpler and maintenance is easier." Performance was identical but correctness was much easier to prove.
Tiers 2 covers probabilistic data structures. Level 16 (Bloom Filter) is the gateway - once you understand accepting false positives for space savings, HyperLogLog and Count-Min Sketch become logical extensions of the same philosophy.
The Traffic Problem
When everyone wants to talk at once
The internet in 1986 was collapsing under congestion. Van Jacobson reduced congestion on the ARPANET by a factor of 1000 in a single day by implementing congestion control in TCP. The core insight: when packet loss occurs, slow down. This led to exponential backoff, token bucket algorithms, and modern rate limiting - all direct descendants of Jacobson's work.
Key Insight: Rate limiting isn't just about protecting your service - it's about protecting the entire network. The same algorithms that prevent internet collapse in TCP are what Stripe, Twilio, and every API gateway uses to protect their services.
The token bucket allows bursting. Tokens accumulate at a fixed rate. Each request consumes one token. If the bucket is empty, the request is rejected. Unlike the leaky bucket (strict rate), the token bucket lets bursty traffic through if capacity has been "saved up." AWS API Gateway, Stripe, GitHub, and virtually every major API uses token bucket or a variant.
Key Insight: Burst capacity is economically valuable. A user who waits 10 minutes and then makes 100 requests should be treated differently from a bot that sends 100 requests in 1 second. Token bucket captures this business logic naturally.
Tier 2 builds the traffic control algorithms every production system uses. Level 14 (Token Bucket) is the most asked "implement this" algorithm in senior backend interviews. Level 17 (Consistent Hashing) is the most asked distributed systems design question.
The Security Arms Race
The mathematics of keeping secrets
The problem seemed mathematically impossible: two parties communicating over a public channel need to agree on a shared secret without an eavesdropper learning it. Diffie and Hellman's solution used the discrete logarithm problem - computing g^x mod p is easy, but finding x given g^x mod p is computationally infeasible. Every HTTPS session you've ever initiated used a descendant of this paper.
Key Insight: The brilliance of Diffie-Hellman: both sides compute different halves of the secret, and mathematics ensures they end up with the same result. Your browser does this 50+ times per day. TLS 1.3 uses ECDHE - Elliptic Curve Diffie-Hellman Ephemeral.
Three MIT researchers invented public-key cryptography independently (Clifford Cocks at GCHQ invented it in 1973, but it was classified). RSA uses the mathematical hardness of factoring large numbers. Multiply two 1024-bit primes in milliseconds; factor the result? The universe will end first. This enabled digital signatures, secure email (PGP), and the entire public-key infrastructure (PKI) that HTTPS runs on.
Key Insight: RSA is why you can trust that github.com is really GitHub. The server's certificate contains a public key. The private key never leaves the server. If you can't factor large primes, you can't impersonate GitHub. This is the foundation of all internet trust.
Tier 3 traces the exact cryptographic evolution from simple ciphers to the protocols securing the modern internet. Each level is a building block: hashing (SHA-256) → symmetric (AES) → asymmetric (RSA) → key exchange (DH) → protocols (JWT/OAuth).
The Distributed Systems Crisis
What happens when the network lies to you
Eric Brewer observed at PODC 2000 that distributed systems cannot simultaneously guarantee Consistency, Availability, and Partition tolerance. Lynch and Gilbert formally proved it in 2002. The choice isn't theoretical: DynamoDB chose AP (available even during partitions, eventually consistent). HBase chose CP (consistent but may be unavailable during partitions). This is the foundational constraint every distributed system architect must confront.
Key Insight: Every distributed database design decision is a CAP trade-off. When you choose DynamoDB over PostgreSQL, you're choosing AP over CP. When you add cross-region replication, you're dealing with partition tolerance. This theorem is WHY distributed systems are hard.
The problem: a transaction spans multiple databases. How do you ensure either ALL commit or NONE commit? 2PC's coordinator asks each participant: "Can you commit?" (Phase 1). If all say YES, coordinator says "Commit!" (Phase 2). The blocking problem: if the coordinator crashes after Phase 1, participants are stuck waiting forever. 2PC is still used in traditional enterprise systems despite this flaw.
Key Insight: 2PC is why microservices avoid distributed transactions. The coordinator is a single point of failure, and the blocking problem under partial failure is unsolvable without Paxos-like consensus. The Saga pattern (Level 47) was invented to replace 2PC.
Tier 4 implements the distributed systems primitives that power every large-scale system. If you can build vector clocks, implement Raft leader election, and design quorum reads/writes from scratch, you can interview for any distributed systems role at any company.
The Database Inside
How databases actually work under the hood
Bayer and McCreight needed a data structure that could handle indexes too large to fit in RAM - stored on disk, where random access is catastrophically expensive. The B-Tree keeps all leaf nodes at the same depth and stores many keys per node (matching disk block size). A B-Tree with millions of records has a height of 3-4, meaning at most 3-4 disk reads to find any record.
Key Insight: Every SQL database (MySQL InnoDB, PostgreSQL, SQLite, Oracle) uses B-Trees for indexes. When you create an index on user_id, you're building a B-Tree. Understanding B-Trees explains why sequential scans sometimes beat index lookups, and why covering indexes work.
The ACID durability guarantee: committed transactions survive crashes. The mechanism: Write-Ahead Logging. BEFORE writing data to disk, write the change to a sequential log file. On crash, replay the log to recover. The WAL design has two elegant properties: (1) sequential writes are 10-100x faster than random writes on HDD (2) crash recovery is deterministic. PostgreSQL, MySQL InnoDB, SQLite - all use WAL.
Key Insight: WAL is why "fsync" matters in PostgreSQL configurations. Disabling fsync makes writes 10x faster but violates the durability guarantee - your data can silently vanish on crash. Understanding WAL is what separates engineers who configure databases from those who understand them.
Tier 5 is database internals. Levels 49-55 implement the actual data structures that power production databases. Building a B-Tree from scratch (Level 49) gives you intuitions that no documentation can provide. This is where Forge Lab graduates become database experts.
The Internet of Algorithms
The invisible algorithms running the modern web
When multiple clients retry simultaneously after a failure, they cause a "thundering herd" that amplifies the very problem they're trying to recover from. Ethernet's CSMA/CD (1980) invented exponential backoff: double the wait time after each retry, with randomized jitter. AWS SDKs, Google Cloud, Kubernetes - all implement full jitter exponential backoff by default.
Key Insight: The retry logic in your HTTP client is a life-or-death algorithm at scale. Without exponential backoff + jitter, a 10-second outage becomes a 10-minute outage because millions of clients retry simultaneously the instant the service recovers.
In 2007, Nygard documented the pattern: don't keep hammering a failing service. After N consecutive failures, "trip" the circuit breaker - fail immediately without calling the service. After a timeout, try a single "probe" request. If it succeeds, close the circuit. Netflix's Hystrix library popularized circuit breakers; Resilience4j is the modern successor.
Key Insight: Every microservices architecture needs circuit breakers. Without them, a single slow database causes cascading failures across every service that calls it. The circuit breaker is the single most important resilience pattern for microservices.
The final levels connect everything. Level 40 (Exponential Backoff) and Level 39 (Circuit Breaker) are the resilience patterns every microservice needs. Level 60 (Final Forge) synthesizes all 59 preceding levels into a complete distributed system design.
The Full Picture
How every chapter connects to what you build in Forge Lab.
You know the history. Now build the algorithms.
Every breakthrough you just read about is a level waiting for you in Forge Lab. Start coding the algorithms that run on every server, every database, and every API on the planet.
Discussion0
Join the Discussion
Sign in to leave comments, reply to others, or like insights.
No comments yet. Be the first to start the thread!
Enjoyed this content?
Your support keeps us creating free resources
We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.
One-time payment via Stripe. ScaleDojo account required.