LLDadvancedPremium

Cab Ride Allocator: a Concurrency Barrier Problem (the Uber ride question)

The Uber ride concurrency interview question: seat ride-request threads into cabs of four — 4+0, 0+4, or 2+2 only — with a mutex, two semaphores, and a barrier. Deadlock-free, stress-tested.

By fiveyearsdevJune 15, 202612 min read

The conference just let out. A few hundred people spill onto the curb, phones up, all tapping the same ride app at once. Each person belongs to one of two political parties, and the cabs seat four. To keep the peace, a cab may leave with four of one party, or two-and-two — never anything else. Get it wrong and the ride turns into a brawl. That is the whole problem, and it is a deceptively deep one — it was the opening question for a Principal Engineer round at Arcesium. It is not really about cabs. It is the barrier problem in disguise: a thread must block until enough compatible threads have …

What’s inside

Let's start at a restaurant door, not a computer

Where this shows up in real systems

Step 1 — Functional requirements (sentences first)

Step 2 — Non-functional requirements

Step 3 — Why the obvious solution starts a fight

Step 4 — The legal groups, and the plan

Step 5 — The cast: a mutex, two seat-semaphores, two counts, a barrier

Step 6 — Forming the cab: the arriving rider decides

Step 7 — Boarding, the barrier, and the one lock that can't be dropped early

The complete implementation

How we know it works

The interview corner

Where to go from here

Read this one free

Sign in and your first premium article is on us — read Cab Ride Allocator: a Concurrency Barrier Problem (the Uber ride question) free.

LLD