Practice Problems for Basic Systems Design

Hints: hashing, bloom filters, locality-sensitive hashing (including MinHash), approximate-nearest-neighbour indexes, and compression / quantization.

Putting it together

A big system can't afford to scan all N on every query, or to keep all N bytes in the memory the query runs in. The fix is always the same: turn one too-big problem into a small one. Every structure in this module's Basic and Approximation Algorithms sections does it the same handful of ways: partition it so a query touches one slice, prune the parts that are definitely unnecessary, reframe it so a coarse description still ranks right, or shrink each item by dropping redundancy or precision. Two levers, used together in real systems:

Two panels. Lever 1, don't scan all N: partition the lookup; exact = hash to one bucket (hashing), approximate = prune what is definitely absent or bucket by similarity, then check only the candidates near the query (Bloom, LSH, IVF, HNSW). Lever 2, don't store all N bytes: shrink each item; exact/lossless = drop the redundancy (RLE, dictionary, delta, bit-pack, only if the data has structure), approximate/lossy = drop precision keep order (PQ, TurboQuant, reframe via random rotation). A connector notes real systems compose both as IVF-PQ, the vector database.

Figure. Two levers for a too-big problem. Lever 1 partitions the lookup so a query examines one slice instead of all N: exactly, by hashing to a bucket; approximately, by pruning what is definitely absent (Bloom) or bucketing by similarity (LSH, IVF, HNSW) and checking only the candidates near the query. Lever 2 shrinks each item: losslessly by dropping the redundancy the data already has (only if it has structure), or lossily by dropping precision while keeping the rank order (a random rotation reframes the data so one coarse quantizer fits any of it). The exact-vs-approximate split inside each lever is the module's Basic-vs-Approximation track. Production composes both, IVF-PQ is partition plus compress, the vector database.

Each problem below is one of these four. Spot which, then name the structure.

Problem 1: Startup API Cache (1M Scale)

Problem: A music-streaming API serves 1M song-metadata requests. Each query hits several database tables, and peak-hour latency is high. What structure cuts the wait?

Show Solution

  • Concept: Hash Table

  • Design: In-memory HashMap: request_id → cached_response • Expire periodically • Evict least-recently used entries

  • Rough Performance: 100MB memory, 50K lookups/sec, 100% accuracy

  • The "Why": Database queries take 50-200ms vs 0.01ms hash lookup. Caching "popular" results avoids expensive DB connections and queries.

Problem 2: Photo Similarity Detection (1M Scale)

Problem: A photo app needs to flag near-duplicate images in a user's library to suggest a cleanup, at 1M photos. What structure finds the near-matches?

Show Solution

  • Concept: Locality-Sensitive Hashing (LSH)

  • Design: Convert images to 512-dim feature vectors • Generate similarity-preserving hash codes • Group photos in same buckets

  • Rough Performance: 200MB memory, 10K photos/sec, 95% accuracy

  • The "Why": Exact pixel comparison is $O(n^2)$ across 1M photos = 1 trillion operations. LSH allows finding near-matches in near $O(n)$ time.

Problem 3: Embedding Index Won't Fit in RAM (10M Scale)

Problem: A semantic-search service stores 10M documents as OpenAI 1,536-D float32 embeddings, about 60 GB, too big for the RAM the similarity search runs in. How do you shrink the index?

Show Solution

  • Concept: Vector Quantization (Product Quantization; TurboQuant for training-free)

  • Design: Replace each 32-bit coordinate with a few bits (4, 2, or 1-bit) so a ~6 KB vector becomes tens of bytes • Classic PQ trains a codebook on the data; TurboQuant skips the codebook with a random rotation, no training pass

  • Rough Performance: ~60 GB → ~2–8 GB (8–32× smaller), recall within a few percent of exact

  • The "Why": Search only needs rank order ("is A closer than B?"), not exact coordinates, so most of the float32 precision is wasted. Quantization keeps the order and drops the rest. (Case Study 2.4.)

Problem 4: Social Media Recommendations (100M Scale)

Problem: Instagram wants to suggest similar users to follow, based on interests, follow lists, and hashtags, at 100M users. What structure finds them?

Show Solution

  • Concept: Locality-Sensitive Hashing (LSH)

  • Design: Represent users as sparse feature vectors (likes, follows) • Hash similar users to same buckets • Pull recommendations from the same bucket

  • Rough Performance: 2GB memory, 50K users/sec, 90% relevance

  • The "Why": Computing exact similarity between 100M users requires $10^{16}$ comparisons. LSH reduces the search space to a localized bucket of likely candidates.

  • At production scale: raw LSH is the teaching version; a live recommender over 100M+ users uses a production ANN index (HNSW or IVF), the vector database from Case Study 2.3. Same idea, better recall per millisecond.

Problem 5: Web Crawler Deduplication (1B Scale)

Problem: A web crawler must avoid re-crawling URLs it has already seen, at 1B URLs. What structure tracks "seen"?

Show Solution

  • Concept: Bloom Filter

  • Design: A large Bloom filter tracks all visited URLs • Check URL before crawling • 1% false positive rate is acceptable (skips 1% of new pages)

  • Rough Performance: 1.2GB memory, 1M URLs/sec, 99% deduplication

  • The "Why": A standard Hash Table for 1B URLs would require 32GB+ RAM. A Bloom filter fits comfortably in the memory of a single machine.

Problem 6: Username Availability (10M Scale)

Problem: As a user types a desired username, the client should flag "taken" instantly without an API call per keystroke, over ~10M taken usernames. What structure makes the check local?

Show Solution

  • Concept: Bloom Filter

  • Design: Periodically download a compressed Bloom filter of taken usernames to the client/app • Perform local "taken" check

  • Rough Performance: ~12MB download, instant client-side checks

  • The "Why": Replaces a 100ms API call with a 0.01ms local check. A false positive simply tells the user a name is taken when it's available, a minor ux friction compared to lag.

Problem 7: Document Near-Duplicates (10B Scale)

Problem: A search engine must drop near-duplicate pages (same content, different ads), at 10B documents. What structure detects them?

Show Solution

  • Concept: Locality-sensitive hashing for sets (MinHash)

  • Design: Turn each doc into a set of word-shingles • Build a MinHash fingerprint: hash that set with many functions and keep the smallest value from each, giving a short integer signature whose fraction of matching slots estimates how much two docs overlap • Group docs with near-identical fingerprints

  • Rough Performance: 40GB memory, 500K docs/sec, 85% detection rate

  • The "Why": Comparing the full text of 10B documents is physically impossible. A MinHash fingerprint shrinks each doc to a few integers whose agreement approximates its similarity, so near-duplicates collide, the same locality idea as LSH, applied to sets.

Problem 8: Log Storage Compression (100M Scale)

Problem: A system writes 100M log entries a day, drawn from the same ~1,000 strings. How do you store them without the bloat?

Show Solution

  • Concept: Dictionary Encoding

  • Design: Create a mapping of 1,000 unique strings → 10-bit IDs • Store only IDs in the main log table

  • Rough Performance: 40GB raw logs → ~150MB stored (over 99% reduction)

  • The "Why": Storing the string "ConnectionTimeoutError" (22 bytes) millions of times is wasteful. Storing a 2-byte ID achieves massive space savings.

Problem 9: Time Series Analytics (1B Scale)

Problem: An IoT platform records a temperature sensor every second; timestamps are predictable, at 1B rows. How do you store them efficiently?

Show Solution

  • Concept: Delta Encoding

  • Design: Store a "Base" timestamp (e.g., midnight) • Store only the +1s or +2s difference (delta) for each subsequent row

  • Rough Performance: 8GB raw timestamps → ~1GB stored

  • The "Why": A standard 8-byte timestamp is redundant when values are predictable. Deltas can be further compressed using bit-packing for even smaller footprints.

Problem 10: E-commerce User Behavior (10M Scale)

Problem: An e-commerce site logs 10M user clicks; sessions are repetitive. How do you store them without redundancy?

Show Solution

  • Concept: Run-Length Encoding (RLE) + Dictionary Encoding

  • Design: Dictionary encode the action types • Use RLE for consecutive repeated actions (e.g., (view_item, 3))

  • Rough Performance: 10x compression ratio for session data

  • The "Why": User behavior is repetitive. RLE eliminates the redundancy of sequential identical events.

Problem 11: Rating System Storage (100M Scale)

Problem: You store 100M ratings (each 1 to 5) for a recommendation engine. How do you store them compactly?

Show Solution

  • Concept: Bit Packing

  • Design: A number from 1-5 only needs 3 bits ($2^3 = 8$) • Pack multiple 3-bit ratings into a single 32-bit or 64-bit word

  • Rough Performance: 400MB raw integers → ~40MB packed storage

  • The "Why": Using a full 32-bit integer for a value that only goes up to 5 wastes 90% of the allocated space. Bit packing maximizes density.

Key insight: Scale numbers (millions vs billions) + problem type ("lookup," "similarity," "storage") immediately point to the right data structure family. Real systems combine multiple techniques for 10-100x improvements.