System Design System Design Interview Practice Flashcards

24 sample cards from the System Design Interview Practice deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. In a URL shortener, how many characters are needed with a base-62 encoding to represent a given number of URLs?

   With base-62 (a-z, A-Z, 0-9), $n$ characters encode $62^{n}$ URLs. For example $62^{7} \approx 3.5 \times 10^{12}$ and $62^{6} \approx 5.7 \times 10^{10}$, so 7 characters comfortably cover trillions of URLs.

2. Describe two approaches to generate short codes for a URL shortener and a trade-off of each.

   1) Hash the long URL (e.g. MD5/SHA) and take the first few base-62 chars — risk of collisions requiring checks. 2) Use an auto-increment/distributed counter and base-62 encode it — no collisions and short, but IDs are predictable/enumerable. A key-generation service can pre-generate unique keys.

3. Why is a URL shortener a read-heavy system, and how does that shape its design?

   Redirects (reads) vastly outnumber creations (writes), often $100{:}1$ or more. Design emphasizes caching hot short codes (e.g. Redis), CDNs, and read replicas; the redirect path returns an HTTP 301/302 to the long URL.

4. What is the difference between HTTP 301 and 302 redirects for a URL shortener?

   301 (permanent): browsers/caches remember it, so future requests skip the service — reduces load but loses per-click analytics. 302 (temporary): every click hits the service, enabling click tracking/analytics at the cost of higher load.

5. How does a Pastebin design differ from a URL shortener in storage terms?

   Pastebin must store the actual paste content (potentially large text blobs) plus a unique key, whereas a URL shortener stores only a short mapping to an existing URL. Pastebin often puts large content in object storage/blob store and metadata in a DB, and supports expiration/TTL.

6. How is expiration (TTL) typically implemented for pastes or short links?

   Store an expiry timestamp with each record. Lazily delete on access (return 404 if expired) and/or run a background cleanup job / use the store's native TTL (e.g. Redis EXPIRE, DynamoDB TTL) to reclaim space.

7. In a file storage service like Dropbox, what is chunking and why is it used?

   Files are split into fixed-size blocks/chunks (e.g. 4 MB). Benefits: only changed chunks are re-uploaded/downloaded (delta sync), enables deduplication of identical chunks, parallel transfers, and resumable uploads.

8. How does deduplication work in a cloud file storage system?

   Each chunk is hashed (e.g. SHA-256). Before storing, the system checks whether a chunk with that hash already exists; if so it stores only a reference, avoiding duplicate storage. This is content-addressed storage.

9. What is the metadata service responsible for in a Dropbox-style design?

   It tracks file/folder structure, versions, chunk lists and their order, sharing permissions, and per-device sync state. It coordinates conflict resolution and drives clients' sync operations, while actual chunks live in block/object storage.

10. How do clients stay in sync in a file storage service without constant polling?

    A notification/long-poll or WebSocket service tells clients when changes occur; the client then queries the metadata service for the diff and downloads only changed chunks. This is a push-notify + pull-metadata pattern.

11. What is adaptive bitrate streaming (ABR) in a video streaming platform?

    The video is pre-encoded (transcoded) into multiple resolutions/bitrates and segmented (e.g. via HLS/DASH). The player dynamically switches segments based on measured bandwidth/buffer, maximizing quality while avoiding rebuffering.

12. Describe the transcoding pipeline for an uploaded video (YouTube/Netflix).

    Upload → store raw file → a processing pipeline (often DAG of tasks / message queue) splits the video, transcodes into multiple codecs/resolutions/bitrates, generates thumbnails and segments (HLS/DASH manifests), then distributes to CDN edge caches for delivery.

13. Why is a CDN critical for a video streaming platform, and what content does it serve?

    Video segments are large and latency-sensitive at massive scale; CDNs cache segments at edge locations near viewers, cutting latency, reducing origin bandwidth, and improving cache-hit rates. Popular content is pushed to many edges; the long tail is fetched on demand.

14. What are the main components of a web crawler?

    URL frontier (queue of URLs to fetch), fetcher/downloader, DNS resolver, HTML parser/extractor, content deduplicator, URL filter, and storage. A seen-URL set prevents re-crawling, and a scheduler enforces politeness and priorities.

15. How does a web crawler enforce politeness and avoid overloading a single host?

    It respects robots.txt and rate-limits requests per host/domain (crawl delay), typically by partitioning the URL frontier by hostname so each host is fetched by one worker with a controlled interval between requests.

16. How does a crawler detect and avoid crawling duplicate or already-seen URLs/content?

    Maintain a 'seen URLs' set (often a Bloom filter for space efficiency) to skip re-crawling. For content dedup, hash page content (or use SimHash/MinHash for near-duplicate detection) and compare against stored fingerprints.

17. What is a Bloom filter and why is it useful in a crawler or cache system?

    A Bloom filter is a probabilistic set that tests membership using $k$ hash functions over an $m$-bit array. It has no false negatives but a tunable false-positive rate $$p \approx \left(1 - e^{-kn/m}\right)^{k}$$ It uses far less memory than storing all elements — ideal for 'have I seen this URL?' checks.

18. What data structure powers an efficient search-autocomplete/typeahead system?

    A trie (prefix tree). Each node represents a prefix; terminal/aggregated nodes store the top-$k$ most frequent completions for that prefix, so a lookup walks the prefix path and returns precomputed suggestions in near $O(\text{prefix length})$ time.

19. How are the top-k suggestions kept fast in an autocomplete system despite constant query updates?

    Precompute and cache the top-$k$ completions at each trie node (or store prefix→suggestions in a cache). Frequency counts are updated asynchronously/offline from query logs and periodically rebuilt, so serving reads stay $O(1)$/fast and don't block on writes.

20. In a ride-sharing service (Uber), how are drivers and riders matched geospatially at scale?

    Locations are indexed with a geospatial scheme — geohash or a hierarchical grid like Uber's H3 (hexagonal cells) or a quadtree. A rider query finds nearby driver cells, then ranks candidates by ETA/distance. Driver locations update frequently in an in-memory geo index.

21. What is a quadtree and how is it used in location-based services?

    A quadtree recursively subdivides 2D space into four quadrants until each leaf holds at most a threshold number of points. It enables efficient range and nearest-neighbor queries by pruning quadrants, adapting resolution to point density (dense areas subdivide more).

22. Explain geohash and why it enables efficient proximity search.

    Geohash encodes a lat/long into a short string by interleaving bits of latitude and longitude; shared prefixes correspond to nearby locations. Proximity search reduces to prefix matching, and neighboring cells are checked to handle boundary cases. Longer geohash = smaller, more precise cell.

23. In a proximity service like Yelp, how do you find all businesses within a radius of a user?

    Index businesses by geohash/quadtree/H3 cell. Compute the user's cell plus adjacent cells covering the search radius, fetch candidate businesses in those cells, then filter by exact Haversine distance and rank by distance/rating.

24. State the Haversine formula used to compute great-circle distance between two lat/long points.

    $$a = \sin^{2}\!\left(\frac{\Delta\varphi}{2}\right) + \cos\varphi_{1}\cos\varphi_{2}\sin^{2}\!\left(\frac{\Delta\lambda}{2}\right)$$ $$d = 2R\,\arcsin\!\left(\sqrt{a}\right)$$ where $\varphi$ is latitude, $\lambda$ is longitude, and $R$ is Earth's radius ($\approx 6371$ km).

What this deck covers

System Design Interview Practice flashcards FAQ