System Design System Design Interview Practice Syllabus

What are the core components of a notification service supporting push, SMS, and email?

1) Notification producers/API, 2) a message queue for buffering and decoupling, 3) notification workers/dispatchers, 4) third-party channel adapters (APNs/FCM for push, SMS gateway, email/SMTP provider), plus a template service and rate limiter.

Why is a message queue essential in a notification service?

It decouples producers from senders, absorbs traffic spikes (buffering), enables retries with backoff for failed deliveries, and allows independent scaling of workers. It also supports at-least-once delivery with idempotency keys to avoid duplicates.

How do you prevent sending duplicate notifications when using at-least-once delivery?

Attach a unique idempotency/dedup key to each notification and store recently sent keys (e.g. in a cache/DB). Before sending, check whether the key was already processed; skip if so.

What real-time transport protocol underlies most video conferencing systems, and why not TCP?

WebRTC using RTP/UDP. UDP is preferred over TCP because low latency matters more than perfect reliability — retransmitting late audio/video is worse than dropping it. WebRTC adds NAT traversal (STUN/TURN) and congestion control.

Compare SFU and MCU architectures for multi-party video conferencing.

SFU (Selective Forwarding Unit): each client sends one stream; the server forwards streams to others without decoding — low server CPU, higher client bandwidth. MCU (Multipoint Control Unit): server mixes all streams into one composite — high server CPU, low client bandwidth. SFU scales better for large calls.

What are STUN and TURN servers used for in WebRTC?

STUN helps a client discover its public IP/port for NAT traversal to establish a direct peer connection. TURN relays media through a server when a direct peer-to-peer connection fails (symmetric NAT/firewall), at the cost of extra latency and bandwidth.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

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).