During a system design interview, you are asked two related but separate design questions. Treat each as an independent end-to-end design; you will be evaluated on architecture, data modeling, and how you reason about scale, consistency, and failure. ### Constraints & Assumptions These apply to both parts unless a part states otherwise: - **Scale**: Millions of monthly active users; design for horizontal growth, not a fixed peak. - **Multi-region**: Users and data span multiple geographic regions. - **Mobile-first clients**: HTTPS for request/response; long-lived connections (WebSocket / gRPC stream / MQTT) available when the app is foregrounded. - **Latency targets**: Part 1 driver-matching results $p95 < 200\text{–}300\,\text{ms}$ after a ride request; Part 2 alerts delivered within a few minutes of a qualifying price change. - **Availability**: Target high availability (assume $\geq 99.9\%$) with graceful degradation rather than hard outages. - **Money is special**: Financial state (fares, charges) requires strong consistency; locations, ETAs, and price freshness can tolerate eventual consistency. ### Clarifying Questions to Ask Scope the whole problem before designing either part: - Is this a single global deployment, or independent per-region stacks with a thin global layer (auth, payments)? - What are the read/write ratios and absolute throughput targets (e.g., location updates/sec in Part 1, price refreshes/sec in Part 2)? - For Part 1, can drivers serve multiple regions, and do we control the routing/ETA/map provider or integrate a third party? - For Part 2, do we crawl sites ourselves, use partner APIs/feeds, or both — and what are the politeness/rate constraints? - What notification channels are in scope (push, email, SMS, in-app)? - What are the data-retention and analytics requirements (how long to keep trips / price history)? ### Part 1: Design a ride-hailing service (similar to Uber) Design the backend for a global, mobile-first ride-hailing platform that connects riders and drivers. The system must support: - Real-time location updates from drivers (and riders) on the order of every few seconds. - Matching a rider to nearby eligible drivers with low latency (the $p95 < 200\text{–}300\,\text{ms}$ target above). - Trip lifecycle management: request, accept, start, end, cancel. - Basic surge pricing driven by local supply and demand. - Durable persistence of trip and user data for billing and analytics. - High availability and fault tolerance across regions. Outline the high-level architecture, the key services and their data models, and how you would handle scalability, consistency, and fault tolerance. In particular, address: (a) how you store and index geo-locations for efficient nearby-driver queries, (b) how you keep driver locations fresh, and (c) how riders receive timely updates (driver ETA, trip status). ```hint Where to start Decompose by responsibility before drawing boxes: identity/profiles, a high-write **location** plane, a **matching/dispatch** path, the transactional **trip lifecycle**, **pricing/surge**, and a real-time **fan-out** plane to clients. These have very different consistency and throughput needs — don't put them in one service or one database. ``` ```hint Geo-indexing The core query is "give me the K nearest *available* drivers to this point, fast." Map the globe to a discrete grid — **geohash** prefixes or **S2 cell IDs** at a resolution of a few hundred meters — so a lookup becomes "this cell plus its neighbors, expanding the ring until K candidates are found" instead of a full scan or a distance computation over every driver. ``` ```hint Freshness & fan-out Treat the latest driver position as hot, ephemeral state (in-memory / Redis GEO), not a durable write per ping; expire stale entries with a TTL so matching never returns drivers who went offline. For live updates to clients, don't poll core services — publish trip/position events to a pub/sub bus and let a separate real-time gateway hold the WebSockets and fan out per-trip. ``` #### What This Part Should Cover - **Service decomposition with the right datastore per concern**: transactional store (e.g., an RDBMS) for trips/users/payments; in-memory/geo-indexed store for live locations; an event bus connecting them. - **Geo-indexing & nearest-driver search**: a concrete spatial scheme (geohash or S2), cell-based candidate gathering with ring expansion, and post-filtering by availability/car-type/rating before ranking by ETA/distance. - **Dispatch correctness**: avoiding double-assignment (reservation/locking), accept timeouts with retry/widen-radius, and idempotent trip creation under mobile retries. - **Scale & fault tolerance**: geographic partitioning, sharding the location and trip planes, multi-AZ deployment, and explicit CAP trade-offs (strong consistency for money, availability for locations/ETAs/surge). ### Part 2: Design a price tracking and alerting system Design a backend that lets users watch product prices and receive alerts when conditions are met. It must support: - Users registering products to watch (by URL or product ID). - Users defining alert rules — e.g., "notify me when price drops below $X" or "notify me when the discount is at least $Y\%$." - Periodic or near-real-time ingestion of current prices from external sources. - Storing per-product price history. - Sending notifications (email/push/SMS) when alert conditions are satisfied. - Operating at scale for millions of tracked products and many more alert rules. Describe the overall architecture, major components, data storage choices, and how you would handle: (a) efficiently crawling/ingesting prices without overloading external sites, (b) evaluating alert rules at scale with reasonable latency and cost, and (c) delivering reliable, de-duplicated notifications. ```hint Where to start Separate the pipeline into stages connected by a queue: **ingestion** (get the new price) → **normalization + history write** → **rule evaluation** (which watchers care?) → **notification**. Each stage scales independently on its own queue depth, and a queue between ingestion and evaluation gives you backpressure when a price refresh storm hits. ``` ```hint Evaluation fan-out The expensive question is "for this new price, which of millions of rules fired?" Key rules by `product_id` so a `PriceUpdated` event only loads that product's rule set — turning a global scan into a per-product lookup. Percentage-drop rules need a *baseline* (first-seen / N-day reference), so think about where that baseline lives. ``` ```hint Reliable, de-duped delivery A naive design re-alerts on every tick while the price sits below the threshold. Make delivery idempotent: record the last triggered state per rule (last price / event ID) and suppress repeats, and de-dup at the notification layer keyed by `(rule_id, trigger)` so a re-delivered queue message can't double-send. ``` #### What This Part Should Cover - **Staged, queue-decoupled pipeline**: ingestion → normalization/history → rule evaluation → notification, each independently scalable with backpressure. - **Polite, prioritized ingestion**: per-product refresh frequency (popular = more often), partner APIs/feeds where available, robots.txt/rate-limit respect. - **Storage choices that fit access patterns**: relational/KV for products and rules; a time-series/wide-column store for append-heavy price history; rules indexed by `product_id`. - **Rule evaluation at scale**: sharding rules by product, in-memory/cached rule sets, correct handling of absolute-threshold vs percent-drop (baseline) rules. - **Idempotent, de-duplicated, rate-limited notifications** with retry/dead-letter handling. ### What a Strong Answer Covers These dimensions span both parts: - **Queue/event-driven decoupling** so high-volume producers (location pings, price refreshes) don't block transactional or fan-out paths. - **Explicit consistency reasoning**: which state is strongly consistent (money/trips) vs eventually consistent (locations, ETAs, price freshness), and why. - **Idempotency under retries** at every consumer (duplicate trip requests, re-delivered events, repeated alerts). - **Horizontal scaling via partitioning** (by region/geohash in Part 1, by `product_id` in Part 2) and graceful degradation under failure. ### Follow-up Questions - **Part 1**: How would you prevent two riders from being matched to the same driver simultaneously, and how do you recover a trip if the dispatch service crashes mid-assignment? - **Part 1**: A whole region's location shard goes down. What does matching do in the meantime, and how do you rebuild hot state on recovery? - **Part 2**: A flash sale changes prices on 100k watched products at once. How does your pipeline avoid a notification storm and stay within per-user rate limits? - **Part 2**: How would you support richer rules (e.g., "lowest price in 90 days" or "price drop AND back in stock") without re-architecting evaluation? - **Both**: How do you measure that you're meeting the latency SLOs (match $p95$, alert delivery), and what do you alert on when you're not?