Before you start

Ride Matching is the last problem in this module — a mix of Strategy (matching algorithm) + basic state management (driver in-pool vs on-ride, ride in-progress vs completed).

The Strategy signal, again

Two matching algorithms today (Nearest, RoundRobin). More possible later: rating-weighted, least-loaded, surge-aware, territorial. Every one is a new strategy class.

Your dispatcher must NOT know which algorithm is running. It just calls strategy.match(...) and uses the return.

The state question (again)

Every driver is in one of two states:

• Available — in the pool, can be matched
• On-ride — matched, waiting for complete_ride

Every ride is in one of two states:

• In-progress — matched but not completed
• Completed — done

Do you use the State pattern for two-state entities? No — that's the third time this course has said it. State pattern for 2 states is overkill. A single field is fine.

The rules (this is where design interviews score you)

Three matter:

1. A driver is in at most one state. They're EITHER in the available pool OR on a ride. Never both, never neither (except after remove_driver, when they're neither on purpose).
2. Completed rides can't be re-completed. complete_ride checks status before running.
3. Matching removes the driver from the pool ATOMICALLY. No window where they're "matched but still available" — a bug that would double-match them.

Enforce each in ONE place. Name them.

Where this shows up

• Uber, Ola, Rapido — the whole industry
• Delivery apps (Swiggy, Zomato) — same shape, different entities
• Load balancers routing requests to backends — same Strategy shape, different tie-breaking
• Task schedulers assigning work to workers — same shape
• Any "match-me-with-a-resource" API

The follow-up questions

• "How would you scale this to millions of drivers?" — a spatial index (quadtree, geohash) to make Nearest O(log N) instead of O(N). HLD territory.
• "How would you handle drivers going offline mid-ride?" — ride cancellation path + rematch. Real feature; out of MVP.
• "How would you support pool rides (multiple riders)?" — ride can hold multiple riders + ordered stops. Big change, but doable with the current shape.

Your design.md doesn't have to answer these — but if your design SETS YOU UP to answer them cleanly, that's the extensibility signal.

Module close

25 lessons + 12 LLD problems = 37 lessons total in the LLD course. You've drilled:

• OOP basics (module 1)
• SOLID principles (module 2)
• 14 design patterns (module 3)
• 12 LLD problems, each needing a designed + justified solution (module 4)

The last module (5, the Capstone) lets you apply everything on YOUR chosen domain, not one we gave you.

Every interview problem you meet from here will be some combination of what you've already built.

A simplified ride-hailing dispatcher. Riders request rides, drivers get matched. Uses Strategy for the matching algorithm and State for the ride lifecycle. Final LLD-problem lesson — it's meant to combine everything.

The problem

A Dispatcher(matching_strategy):

Driver ops

• add_driver(driver_id, location) — register available driver. location is a (x, y) tuple (int coords).
• remove_driver(driver_id) — drop from the pool (they went home).

Ride ops

• request_ride(rider_id, pickup_location) — attempt to match. Returns a dict:
  • {"status": "matched", "ride_id": str, "driver_id": str} on success
  • {"status": "no_drivers", "ride_id": None, "driver_id": None} if pool empty

Matched drivers are REMOVED from the available pool (they're now busy on a ride).

• complete_ride(ride_id) — driver becomes available again at their pickup location. Raises ValueError if unknown ride.

Query ops

• available_drivers() — sorted list of ids.
• ride_status(ride_id) — "in_progress" | "completed".

Matching strategies

Two must exist:

1. Nearest (by Euclidean distance)

Match the driver with minimum sqrt((dx)² + (dy)²) to the pickup. On ties, pick alphabetically-first driver_id.

2. RoundRobin

Cycle through available drivers in registration order. Ignores location.

Requirement-gathering questions

1. Cancel a request? — Not for MVP.
2. Surge pricing? — Not for MVP.
3. Multiple ride types (economy, premium)? — Not for MVP.
4. Rider ratings / driver ratings? — Not for MVP.
5. Concurrent requests? — Single-threaded.

Design goals

• Add a new matching strategy (e.g., "rating-weighted", "least-loaded") without touching Dispatcher.
• Ride lifecycle: pending → in_progress → completed. But since we auto-complete-on-request-return, we skip "pending" — every ride starts in_progress on match.
• Invariants: driver is in AT MOST ONE state (available OR on-a-ride). Completed rides can't be re-completed.

Your task

Public API:

from main import Dispatcher, NearestStrategy, RoundRobinStrategy

d = Dispatcher(matching_strategy=NearestStrategy())
d.add_driver("dA", (0, 0))
d.add_driver("dB", (10, 10))
d.add_driver("dC", (5, 5))

r = d.request_ride("rider1", (1, 1))
# nearest to (1,1) is dA at (0,0)
# r == {"status": "matched", "ride_id": "...", "driver_id": "dA"}

d.available_drivers()   # ["dB", "dC"]
d.ride_status(r["ride_id"])   # "in_progress"

d.complete_ride(r["ride_id"])
d.available_drivers()   # ["dA", "dB", "dC"]
d.ride_status(r["ride_id"])   # "completed"

Click Submit to run the tests.