Design a Food Delivery System (LLD)
Food delivery looks like ride sharing with a kitchen in the middle, and that middle step changes the design. There are three parties instead of two. The restaurant has to agree to the order, and it might not answer at all. The order sits in a "being cooked" phase where a partner can be found in parallel. And three different apps (customer, restaurant, partner) all want live updates for the same order.
The DoorDash/Swiggy system design covers search, the distributed order pipeline and ETA prediction. This page stays at class level: what the objects are, which one owns each rule, and how the code stays correct when the restaurant taps "accept" in the same instant the timeout fires. If you've done the ride-sharing case study, you'll recognise the partner claim. The new parts are the cart, pricing, the timeout and Observer.
1. Requirements
Clarifying questions
| Question | Answer we assume |
|---|---|
| Can a cart hold items from two restaurants? | No. One restaurant per cart, enforced at add time |
| Do prices change after ordering? | No. The order snapshots name and price per line |
| Does the restaurant confirm each order? | Yes, accept or reject. No answer within 5 minutes means auto-reject |
| When do we look for a delivery partner? | As soon as the restaurant accepts, while the food is cooked |
| What if no partner is free? | The order waits in a queue and is retried when a partner frees up |
| Can the customer cancel? | Only before the restaurant accepts |
| Pricing? | Subtotal + delivery fee (distance-based, free above a threshold) − coupon |
| Payment, refunds, ratings, search? | Out of scope. Payment is covered in ride sharing |
Functional requirements
- Customers build a cart from one restaurant's menu and place an order, optionally with a coupon.
- The restaurant accepts or rejects. Orders not answered within 5 minutes are rejected automatically.
- On acceptance, a nearby delivery partner is assigned with a pluggable strategy (nearest, or longest-idle for fairness).
- The order moves
PLACED → ACCEPTED → READY → PICKED_UP → DELIVERED, withREJECTEDandCANCELLEDbranching fromPLACED. - Every status change and partner assignment is pushed to subscribers (customer app, restaurant tablet, partner app).
Non-functional requirements
- A partner carries at most one order (batching comes as an extension).
- A restaurant's accept and the timeout can't both win.
- Events for one order arrive in order, and a broken subscriber can't block an order.
- Money is integer cents, and the clock is injected so timeouts can be tested without sleeping.
2. Entities
| Entity | Kind | Responsibility |
|---|---|---|
Restaurant | Entity | id, location, menu of MenuItem |
MenuItem | Value object | id, name, price |
Cart | Entity, one per customer | one restaurant, item quantities. drain() turns it into order lines atomically |
OrderLine | Value object | price snapshot: item id, name, unit price, quantity |
Price | Value object | subtotal, delivery fee, discount, total |
Order | Aggregate root | lines, price, status, assigned partner, placed-at time |
Partner | Entity | location, idle-since time, atomic PartnerStatus |
AssignmentStrategy | Strategy | ranks free partners for a restaurant |
DeliveryFeePolicy / Coupon | Strategy | the two halves of pricing |
PricingEngine | Domain service | combines lines, fee and coupon into a Price |
OrderObserver | Observer interface | onStatus, onPartnerAssigned |
DeliveryService | Facade | every use case, the registries, the waiting queue |
The design hinges on one decision: OrderLine copies the price. If an order referenced MenuItem directly, a restaurant raising the burger price at 7 pm would change the total of an order placed at 6:59. Snapshots make the order immutable in everything except status and partner.
classDiagram
class DeliveryService {
+cart(customerId) Cart
+placeOrder(customerId, dropoff, coupon) Order
+accept(orderId)
+reject(orderId)
+cancel(orderId, customerId)
+expireUnaccepted() int
+markReady(orderId)
+pickUp(orderId, partnerId)
+deliver(orderId, partnerId)
+assignWaiting()
+subscribe(observer)
}
class Restaurant {
+id
+location
+menu Map
}
class MenuItem {
+id
+name
+priceCents
}
class Cart {
-restaurant
-quantities Map
+add(restaurant, itemId, qty)
+drain() OrderLines
}
class Order {
+id
+lines List~OrderLine~
+price Price
+placedAt
-status OrderStatus
-partner Partner
}
class OrderLine {
+name
+unitCents
+qty
}
class Partner {
+id
-status AtomicReference
+idleSince
+transition(from, to) boolean
}
class AssignmentStrategy {
<<interface>>
+rank(partners, restaurant) List~Partner~
}
class PricingEngine {
+price(lines, km, coupon) Price
}
class DeliveryFeePolicy {
<<interface>>
+feeCents(km, subtotal) long
}
class Coupon {
<<interface>>
+discountCents(subtotal, fee) long
}
class OrderObserver {
<<interface>>
+onStatus(order, from, to)
+onPartnerAssigned(order, partner)
}
DeliveryService --> PricingEngine
DeliveryService --> AssignmentStrategy
DeliveryService o-- "*" OrderObserver
DeliveryService o-- "*" Order
DeliveryService o-- "*" Cart
Restaurant *-- "*" MenuItem
Cart --> Restaurant
Order --> Restaurant
Order *-- "*" OrderLine
Order --> Partner
PricingEngine --> DeliveryFeePolicy
PricingEngine o-- "*" Coupon
AssignmentStrategy <|.. NearestToRestaurant
AssignmentStrategy <|.. LongestIdleFirst
DeliveryFeePolicy <|.. DistanceFee
Coupon <|.. PercentOff
Coupon <|.. FreeDelivery
OrderObserver <|.. CustomerFeed
3. Lifecycles
stateDiagram-v2
[*] --> PLACED : cart drained, price fixed
PLACED --> ACCEPTED : restaurant accepts, partner search starts
PLACED --> REJECTED : restaurant rejects
PLACED --> REJECTED : no answer in 5 minutes
PLACED --> CANCELLED : customer cancels
ACCEPTED --> READY : food packed
READY --> PICKED_UP : assigned partner collects
PICKED_UP --> DELIVERED : handed to customer
DELIVERED --> [*]
REJECTED --> [*]
CANCELLED --> [*]
Partner assignment isn't a status. It runs alongside ACCEPTED and READY, and only PICKED_UP requires it, because pickUp checks that the caller is the assigned partner. That's why a slow partner search never blocks the kitchen.
stateDiagram-v2
[*] --> AVAILABLE : partner online
AVAILABLE --> BUSY : claimed for an order, CAS
BUSY --> AVAILABLE : order delivered
AVAILABLE --> OFFLINE : logs off
OFFLINE --> AVAILABLE : logs on
4. Key flows
Place, accept, assign
sequenceDiagram
participant C as Customer
participant S as DeliveryService
participant P as PricingEngine
participant R as Restaurant tablet
participant A as AssignmentStrategy
participant O as Observers
C->>S: placeOrder alice, dropoff, SAVE20
S->>S: cart.drain gives lines with price snapshot
S->>P: price lines, 4 km, SAVE20
P-->>S: 1100 + 300 - 150
S->>O: PLACED
R->>S: accept O1
S->>S: lock O1, PLACED to ACCEPTED
S->>O: ACCEPTED
S->>A: rank free partners near R1
S->>S: partner CAS AVAILABLE to BUSY
S->>O: PARTNER near
Timeout racing accept
sequenceDiagram
participant R as Restaurant thread
participant L as Order O1 lock
participant T as Timeout sweeper
T->>L: acquire
R->>L: acquire, waits
T->>L: status PLACED and 5 min old, set REJECTED, notify
T->>L: release
L-->>R: acquired
R->>L: status is REJECTED, accept throws
Note over R,T: Reverse order: accept wins, sweeper sees ACCEPTED and skips
Partner frees up
sequenceDiagram
participant D as Partner app
participant S as DeliveryService
participant Q as Waiting queue
D->>S: deliver O1
S->>S: lock O1, DELIVERED, partner BUSY to AVAILABLE, unlock
S->>Q: poll each waiting order once
Q-->>S: O7
S->>S: lock O7, tryAssign, unlock
5. Patterns, and why
| Pattern | Where | Why | Rejected alternative |
|---|---|---|---|
| Observer | OrderObserver, CustomerFeed | Three apps (and analytics, and support tools) react to the same changes. The order shouldn't know any of them | DeliveryService calling pushService.send and smsService.send directly, which couples every new consumer to the core |
| Strategy | AssignmentStrategy | Nearest-first minimises wait. Longest-idle spreads earnings. Markets choose | A mode flag with an if |
| Strategy | DeliveryFeePolicy, Coupon | Fee rules and promotions change weekly | Hard-coded fee arithmetic in placeOrder |
| State machine (enum + guard) | move(o, from, to) | Every transition is "check one state, set another" | State classes. With no per-state behaviour, they'd be ceremony |
| Facade | DeliveryService | One place where locks and invariants live | Callers mutating Order |
| Value objects | OrderLine, Price, MenuItem | Immutability makes snapshots safe to share across threads | Mutable lines that change when the menu does |
Why is Coupon a Strategy and not a Decorator? In ride sharing, fare components wrap each other because each one transforms the previous total. Here we allow one coupon per order, and it computes a discount from the subtotal and fee. If the interviewer allows stacking ("a coupon plus a membership discount"), turn coupons into decorators over a base price, or apply a list of discounts in a defined order. Say which one, and why the order matters.
Observer delivery: synchronous, under the order lock. This gives a simple guarantee: for any one order, subscribers see events in the order they happened, because the next transition can't start until notification finishes. The cost is that a slow subscriber slows that order down. So the rule for subscribers is "enqueue and return". safely(...) catches subscriber exceptions, so a dead push service doesn't fail the restaurant's accept. In production you'd publish to a queue with a per-order sequence number. The broader channel and retry design lives in the notification service case study.
6. The code
All three are runnable and end with asserts. The Java main includes both concurrency checks. Save the Python as food_delivery.py, since the tests import it.
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.function.LongSupplier;
record Location(double x, double y) {
double distanceTo(Location o) { return Math.hypot(x - o.x, y - o.y); }
}
record MenuItem(String id, String name, long priceCents) {}
record OrderLine(String itemId, String name, long unitCents, int qty) {
long totalCents() { return unitCents * qty; }
}
record Price(long subtotal, long deliveryFee, long discount) {
long total() { return subtotal + deliveryFee - discount; }
}
enum OrderStatus { PLACED, ACCEPTED, READY, PICKED_UP, DELIVERED, REJECTED, CANCELLED }
enum PartnerStatus { OFFLINE, AVAILABLE, BUSY }
class DeliveryException extends RuntimeException {
DeliveryException(String message) { super(message); }
}
final class Restaurant {
final String id; final Location location; final Map<String, MenuItem> menu = new ConcurrentHashMap<>();
Restaurant(String id, Location location, MenuItem... items) {
this.id = id; this.location = location;
for (MenuItem i : items) menu.put(i.id(), i);
}
}
final class Cart {
private Restaurant restaurant; // guarded by this
private final Map<String, Integer> quantities = new LinkedHashMap<>();
synchronized void add(Restaurant r, String itemId, int qty) {
if (qty <= 0 || !r.menu.containsKey(itemId)) throw new DeliveryException("bad item or quantity");
if (restaurant != null && restaurant != r) throw new DeliveryException("cart holds another restaurant's items");
restaurant = r;
quantities.merge(itemId, qty, Integer::sum);
}
/** Snapshot prices into order lines and empty the cart, atomically. */
synchronized Map.Entry<Restaurant, List<OrderLine>> drain() {
if (restaurant == null) throw new DeliveryException("cart is empty");
List<OrderLine> lines = new ArrayList<>();
quantities.forEach((id, q) -> {
MenuItem m = restaurant.menu.get(id);
lines.add(new OrderLine(id, m.name(), m.priceCents(), q));
});
Map.Entry<Restaurant, List<OrderLine>> out = Map.entry(restaurant, lines);
restaurant = null; quantities.clear();
return out;
}
}
final class Partner {
final String id;
private volatile Location location;
private final AtomicReference<PartnerStatus> status = new AtomicReference<>(PartnerStatus.AVAILABLE);
volatile long idleSince;
Partner(String id, Location location, long now) { this.id = id; this.location = location; this.idleSince = now; }
Location location() { return location; }
void moveTo(Location l) { location = l; }
PartnerStatus status() { return status.get(); }
boolean transition(PartnerStatus from, PartnerStatus to) { return status.compareAndSet(from, to); }
}
final class Order {
final String id, customerId; final Restaurant restaurant; final Location dropoff;
final List<OrderLine> lines; final Price price; final long placedAt;
OrderStatus status = OrderStatus.PLACED; // guarded by this
Partner partner; // guarded by this
Order(String id, String customerId, Restaurant r, Location dropoff, List<OrderLine> lines, Price price, long placedAt) {
this.id = id; this.customerId = customerId; this.restaurant = r; this.dropoff = dropoff;
this.lines = List.copyOf(lines); this.price = price; this.placedAt = placedAt;
}
synchronized OrderStatus status() { return status; }
synchronized Partner partner() { return partner; }
}
interface OrderObserver {
void onStatus(Order o, OrderStatus from, OrderStatus to);
default void onPartnerAssigned(Order o, Partner p) {}
}
interface AssignmentStrategy { List<Partner> rank(List<Partner> candidates, Restaurant r); }
final class NearestToRestaurant implements AssignmentStrategy {
public List<Partner> rank(List<Partner> c, Restaurant r) {
Map<Partner, Double> d = new HashMap<>();
for (Partner p : c) d.put(p, p.location().distanceTo(r.location)); // snapshot
List<Partner> out = new ArrayList<>(c);
out.sort(Comparator.comparingDouble(d::get));
return out;
}
}
final class LongestIdleFirst implements AssignmentStrategy { // fairness between partners
public List<Partner> rank(List<Partner> c, Restaurant r) {
Map<Partner, Long> idle = new HashMap<>();
for (Partner p : c) idle.put(p, p.idleSince);
List<Partner> out = new ArrayList<>(c);
out.sort(Comparator.comparingLong(idle::get));
return out;
}
}
interface DeliveryFeePolicy { long feeCents(double km, long subtotalCents); }
final class DistanceFee implements DeliveryFeePolicy {
private final long baseCents, perKmCents, freeAboveCents; private final double includedKm;
DistanceFee(long base, double includedKm, long perKm, long freeAbove) {
baseCents = base; this.includedKm = includedKm; perKmCents = perKm; freeAboveCents = freeAbove;
}
public long feeCents(double km, long subtotal) {
if (subtotal >= freeAboveCents) return 0;
return baseCents + Math.round(Math.max(0, km - includedKm) * perKmCents);
}
}
interface Coupon {
String code();
long minSubtotalCents();
long discountCents(long subtotal, long fee);
}
record PercentOff(String code, int percent, long capCents, long minSubtotalCents) implements Coupon {
public long discountCents(long subtotal, long fee) { return Math.min(capCents, subtotal * percent / 100); }
}
record FreeDelivery(String code, long minSubtotalCents) implements Coupon {
public long discountCents(long subtotal, long fee) { return fee; }
}
final class PricingEngine {
private final DeliveryFeePolicy feePolicy; private final Map<String, Coupon> coupons = new ConcurrentHashMap<>();
PricingEngine(DeliveryFeePolicy feePolicy) { this.feePolicy = feePolicy; }
void addCoupon(Coupon c) { coupons.put(c.code(), c); }
Price price(List<OrderLine> lines, double km, String couponCode) {
long subtotal = lines.stream().mapToLong(OrderLine::totalCents).sum();
long fee = feePolicy.feeCents(km, subtotal);
long discount = 0;
if (couponCode != null) {
Coupon c = coupons.get(couponCode);
if (c == null) throw new DeliveryException("unknown coupon " + couponCode);
if (subtotal < c.minSubtotalCents()) throw new DeliveryException("order too small for " + couponCode);
discount = Math.min(c.discountCents(subtotal, fee), subtotal + fee); // never below zero
}
return new Price(subtotal, fee, discount);
}
}
final class DeliveryService {
static final long ACCEPT_TIMEOUT_MS = 5 * 60_000;
static final double PARTNER_RADIUS_KM = 5.0;
private final Map<String, Partner> partners = new ConcurrentHashMap<>();
private final Map<String, Cart> carts = new ConcurrentHashMap<>();
private final Map<String, Order> orders = new ConcurrentHashMap<>();
private final Queue<Order> awaitingPartner = new ConcurrentLinkedQueue<>();
private final List<OrderObserver> observers = new CopyOnWriteArrayList<>();
private final AtomicLong ids = new AtomicLong();
private final PricingEngine pricing; private final AssignmentStrategy assignment; private final LongSupplier clock;
DeliveryService(PricingEngine pricing, AssignmentStrategy assignment, LongSupplier clock) {
this.pricing = pricing; this.assignment = assignment; this.clock = clock;
}
Partner addPartner(String id, Location at) { Partner p = new Partner(id, at, clock.getAsLong()); partners.put(id, p); return p; }
void subscribe(OrderObserver o) { observers.add(o); }
Cart cart(String customerId) { return carts.computeIfAbsent(customerId, k -> new Cart()); }
Order placeOrder(String customerId, Location dropoff, String couponCode) {
Map.Entry<Restaurant, List<OrderLine>> drained = cart(customerId).drain();
Restaurant r = drained.getKey();
Price price;
try {
price = pricing.price(drained.getValue(), r.location.distanceTo(dropoff), couponCode);
} catch (DeliveryException e) { // give the items back
for (OrderLine l : drained.getValue()) cart(customerId).add(r, l.itemId(), l.qty());
throw e;
}
Order o = new Order("O" + ids.incrementAndGet(), customerId, r, dropoff, drained.getValue(), price, clock.getAsLong());
orders.put(o.id, o);
synchronized (o) { notifyStatus(o, null, OrderStatus.PLACED); }
return o;
}
void accept(String orderId) {
Order o = get(orders, orderId);
synchronized (o) {
move(o, OrderStatus.ACCEPTED, OrderStatus.PLACED);
if (!tryAssign(o)) awaitingPartner.add(o);
}
}
void reject(String orderId) { Order o = get(orders, orderId); synchronized (o) { move(o, OrderStatus.REJECTED, OrderStatus.PLACED); } }
void cancel(String orderId, String customerId) {
Order o = get(orders, orderId);
synchronized (o) {
if (!o.customerId.equals(customerId)) throw new DeliveryException("not your order");
move(o, OrderStatus.CANCELLED, OrderStatus.PLACED);
}
}
/** Rejects every order the restaurant ignored for too long. Run it from a scheduler. */
int expireUnaccepted() {
long now = clock.getAsLong(); int expired = 0;
for (Order o : orders.values()) {
synchronized (o) {
if (o.status == OrderStatus.PLACED && now - o.placedAt >= ACCEPT_TIMEOUT_MS) {
move(o, OrderStatus.REJECTED, OrderStatus.PLACED); expired++;
}
}
}
return expired;
}
void markReady(String orderId) { Order o = get(orders, orderId); synchronized (o) { move(o, OrderStatus.READY, OrderStatus.ACCEPTED); } }
void pickUp(String orderId, String partnerId) {
Order o = get(orders, orderId);
synchronized (o) {
requirePartner(o, partnerId);
move(o, OrderStatus.PICKED_UP, OrderStatus.READY);
}
}
void deliver(String orderId, String partnerId) {
Order o = get(orders, orderId);
synchronized (o) {
requirePartner(o, partnerId);
move(o, OrderStatus.DELIVERED, OrderStatus.PICKED_UP);
o.partner.idleSince = clock.getAsLong();
o.partner.transition(PartnerStatus.BUSY, PartnerStatus.AVAILABLE);
}
assignWaiting(); // outside the lock: touches other orders
}
/** Retries orders that found no partner. Each order is polled by exactly one thread. */
void assignWaiting() {
for (int n = awaitingPartner.size(); n > 0; n--) {
Order o = awaitingPartner.poll();
if (o == null) return;
synchronized (o) {
boolean stillNeeds = o.partner == null && (o.status == OrderStatus.ACCEPTED || o.status == OrderStatus.READY);
if (stillNeeds && !tryAssign(o)) awaitingPartner.add(o);
}
}
}
// caller holds o's monitor
private boolean tryAssign(Order o) {
List<Partner> free = new ArrayList<>();
for (Partner p : partners.values())
if (p.status() == PartnerStatus.AVAILABLE && p.location().distanceTo(o.restaurant.location) <= PARTNER_RADIUS_KM)
free.add(p);
for (Partner p : assignment.rank(free, o.restaurant)) {
if (p.transition(PartnerStatus.AVAILABLE, PartnerStatus.BUSY)) { // atomic claim
o.partner = p;
for (OrderObserver ob : observers) safely(() -> ob.onPartnerAssigned(o, p));
return true;
}
}
return false;
}
// caller holds o's monitor
private void move(Order o, OrderStatus to, OrderStatus requiredFrom) {
if (o.status != requiredFrom) throw new DeliveryException("order " + o.id + " is " + o.status + ", not " + requiredFrom);
o.status = to;
notifyStatus(o, requiredFrom, to);
}
// called under the order's lock, so each order's events arrive in order
private void notifyStatus(Order o, OrderStatus from, OrderStatus to) {
for (OrderObserver ob : observers) safely(() -> ob.onStatus(o, from, to));
}
private static void safely(Runnable r) {
try { r.run(); } catch (RuntimeException e) { System.err.println("observer failed: " + e); }
}
private static void requirePartner(Order o, String partnerId) {
if (o.partner == null || !o.partner.id.equals(partnerId)) throw new DeliveryException("not your delivery");
}
private static <T> T get(Map<String, T> m, String id) {
T v = m.get(id);
if (v == null) throw new DeliveryException("unknown id " + id);
return v;
}
}
/** Example observer: what the customer's app would show. */
final class CustomerFeed implements OrderObserver {
final Map<String, List<String>> events = new ConcurrentHashMap<>();
public void onStatus(Order o, OrderStatus from, OrderStatus to) {
events.computeIfAbsent(o.id, k -> new CopyOnWriteArrayList<>()).add(to.name());
}
public void onPartnerAssigned(Order o, Partner p) {
events.computeIfAbsent(o.id, k -> new CopyOnWriteArrayList<>()).add("PARTNER:" + p.id);
}
}
public class Main {
static final AtomicLong now = new AtomicLong(0);
static DeliveryService service(AssignmentStrategy s) {
PricingEngine pricing = new PricingEngine(new DistanceFee(200, 2.0, 50, 2000));
pricing.addCoupon(new PercentOff("SAVE20", 20, 150, 500));
pricing.addCoupon(new FreeDelivery("FREEDEL", 800));
DeliveryService d = new DeliveryService(pricing, s, now::get);
return d;
}
static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }
public static void main(String[] args) throws Exception {
DeliveryService d = service(new NearestToRestaurant());
CustomerFeed feed = new CustomerFeed(); d.subscribe(feed);
Restaurant r1 = new Restaurant("R1", new Location(0, 0), new MenuItem("burger", "Burger", 450), new MenuItem("fries", "Fries", 200));
d.addPartner("near", new Location(1, 0)); d.addPartner("far", new Location(4, 0));
d.cart("alice").add(r1, "burger", 2); d.cart("alice").add(r1, "fries", 1);
try { d.cart("alice").add(new Restaurant("R2", new Location(9, 9), new MenuItem("x", "X", 1)), "x", 1); check(false, "mixed cart"); }
catch (DeliveryException expected) {}
Order o = d.placeOrder("alice", new Location(4, 0), "SAVE20");
// subtotal 1100, fee 200 + 2 km * 50 = 300, 20% = 220 capped at 150
check(o.price.equals(new Price(1100, 300, 150)) && o.price.total() == 1250, "price " + o.price);
d.accept(o.id);
check(o.partner().id.equals("near"), "nearest partner assigned");
d.markReady(o.id); d.pickUp(o.id, "near"); d.deliver(o.id, "near");
check(feed.events.get(o.id).equals(List.of("PLACED", "ACCEPTED", "PARTNER:near", "READY", "PICKED_UP", "DELIVERED")),
"observer saw " + feed.events.get(o.id));
d.cart("bob").add(r1, "burger", 2);
check(d.placeOrder("bob", new Location(1, 0), "FREEDEL").price.total() == 900, "free delivery coupon");
d.cart("bob").add(r1, "fries", 1);
try { d.placeOrder("bob", new Location(1, 0), "FREEDEL"); check(false, "min subtotal"); }
catch (DeliveryException expected) {}
// timeout: the restaurant never answers
d.cart("carol").add(r1, "fries", 3);
Order slow = d.placeOrder("carol", new Location(1, 0), null);
now.addAndGet(DeliveryService.ACCEPT_TIMEOUT_MS - 1);
d.expireUnaccepted();
check(slow.status() == OrderStatus.PLACED, "not yet");
now.addAndGet(1);
d.expireUnaccepted();
check(slow.status() == OrderStatus.REJECTED, "auto-rejected at 5 minutes");
concurrentAcceptsShareNoPartner();
acceptRacingTimeout();
System.out.println("food-delivery: all checks passed");
}
static void concurrentAcceptsShareNoPartner() throws Exception {
DeliveryService d = service(new NearestToRestaurant());
Restaurant r = new Restaurant("R1", new Location(0, 0), new MenuItem("burger", "Burger", 450));
for (int i = 0; i < 5; i++) d.addPartner("p" + i, new Location(i * 0.2, 0));
List<Order> placed = new ArrayList<>();
for (int i = 0; i < 20; i++) { d.cart("c" + i).add(r, "burger", 1); placed.add(d.placeOrder("c" + i, new Location(1, 1), null)); }
ExecutorService pool = Executors.newFixedThreadPool(20);
CountDownLatch go = new CountDownLatch(1);
List<Future<?>> fs = new ArrayList<>();
for (Order o : placed) fs.add(pool.submit(() -> { go.await(); d.accept(o.id); return null; }));
go.countDown();
for (Future<?> f : fs) f.get();
pool.shutdown();
List<String> got = new ArrayList<>();
for (Order o : placed) if (o.partner() != null) got.add(o.partner().id);
check(got.size() == 5 && new HashSet<>(got).size() == 5, "5 orders, 5 distinct partners: " + got);
Order done = placed.stream().filter(o -> o.partner() != null).findFirst().orElseThrow();
String p = done.partner().id;
d.markReady(done.id); d.pickUp(done.id, p); d.deliver(done.id, p);
long assigned = placed.stream().filter(o -> o != done && o.partner() != null).count();
check(assigned == 5, "freed partner picked up a waiting order");
}
static void acceptRacingTimeout() throws Exception {
ExecutorService pool = Executors.newFixedThreadPool(2);
for (int i = 0; i < 300; i++) {
now.set(0);
DeliveryService d = service(new NearestToRestaurant());
Restaurant r = new Restaurant("R1", new Location(0, 0), new MenuItem("burger", "Burger", 450));
CustomerFeed feed = new CustomerFeed(); d.subscribe(feed);
d.cart("c").add(r, "burger", 1);
Order o = d.placeOrder("c", new Location(1, 0), null);
now.set(DeliveryService.ACCEPT_TIMEOUT_MS); // the deadline is right now
CyclicBarrier b = new CyclicBarrier(2);
Future<Boolean> accepted = pool.submit(() -> {
b.await();
try { d.accept(o.id); return true; } catch (DeliveryException e) { return false; }
});
Future<Integer> expired = pool.submit(() -> { b.await(); return d.expireUnaccepted(); });
boolean won = accepted.get(); int n = expired.get();
check(won != (n == 1), "exactly one of accept and timeout wins");
check(o.status() == (won ? OrderStatus.ACCEPTED : OrderStatus.REJECTED), "status matches the winner");
List<String> ev = feed.events.get(o.id);
check(ev.contains("ACCEPTED") != ev.contains("REJECTED"), "one terminal decision event: " + ev);
}
pool.shutdown();
}
}
from __future__ import annotations
import math
import threading
from collections import deque
from dataclasses import dataclass, field
from enum import Enum
from itertools import count
from typing import Callable, Protocol
@dataclass(frozen=True)
class Location:
x: float
y: float
def distance_to(self, o: Location) -> float:
return math.hypot(self.x - o.x, self.y - o.y)
@dataclass(frozen=True)
class MenuItem:
id: str
name: str
price_cents: int
@dataclass(frozen=True)
class OrderLine:
item_id: str
name: str
unit_cents: int
qty: int
@property
def total_cents(self) -> int:
return self.unit_cents * self.qty
@dataclass(frozen=True)
class Price:
subtotal: int
delivery_fee: int
discount: int
@property
def total(self) -> int:
return self.subtotal + self.delivery_fee - self.discount
class OrderStatus(Enum):
PLACED = 1; ACCEPTED = 2; READY = 3; PICKED_UP = 4; DELIVERED = 5; REJECTED = 6; CANCELLED = 7
class PartnerStatus(Enum):
OFFLINE = 1; AVAILABLE = 2; BUSY = 3
class DeliveryError(Exception):
pass
class Restaurant:
def __init__(self, id: str, location: Location, *items: MenuItem) -> None:
self.id, self.location = id, location
self.menu = {i.id: i for i in items}
class Cart:
def __init__(self) -> None:
self._lock = threading.Lock()
self._restaurant: Restaurant | None = None
self._quantities: dict[str, int] = {}
def add(self, r: Restaurant, item_id: str, qty: int) -> None:
if qty <= 0 or item_id not in r.menu:
raise DeliveryError("bad item or quantity")
with self._lock:
if self._restaurant is not None and self._restaurant is not r:
raise DeliveryError("cart holds another restaurant's items")
self._restaurant = r
self._quantities[item_id] = self._quantities.get(item_id, 0) + qty
def drain(self) -> tuple[Restaurant, list[OrderLine]]:
"""Snapshot prices into order lines and empty the cart, atomically."""
with self._lock:
r = self._restaurant
if r is None:
raise DeliveryError("cart is empty")
lines = [OrderLine(i, r.menu[i].name, r.menu[i].price_cents, q) for i, q in self._quantities.items()]
self._restaurant, self._quantities = None, {}
return r, lines
class Partner:
def __init__(self, id: str, location: Location, now: float) -> None:
self.id, self.location, self.idle_since = id, location, now
self._status = PartnerStatus.AVAILABLE
self._lock = threading.Lock()
@property
def status(self) -> PartnerStatus:
return self._status
def transition(self, frm: PartnerStatus, to: PartnerStatus) -> bool:
with self._lock:
if self._status is not frm:
return False
self._status = to
return True
@dataclass(eq=False)
class Order:
id: str
customer_id: str
restaurant: Restaurant
dropoff: Location
lines: tuple[OrderLine, ...]
price: Price
placed_at: float
status: OrderStatus = OrderStatus.PLACED # guarded by lock
partner: Partner | None = None # guarded by lock
lock: threading.RLock = field(default_factory=threading.RLock)
class OrderObserver:
"""Base class with no-op hooks, so observers override only what they need."""
def on_status(self, o: Order, frm: OrderStatus | None, to: OrderStatus) -> None: ...
def on_partner_assigned(self, o: Order, p: Partner) -> None: ...
class AssignmentStrategy(Protocol):
def rank(self, candidates: list[Partner], r: Restaurant) -> list[Partner]: ...
class NearestToRestaurant:
def rank(self, candidates: list[Partner], r: Restaurant) -> list[Partner]:
return sorted(candidates, key=lambda p: p.location.distance_to(r.location))
class LongestIdleFirst:
def rank(self, candidates: list[Partner], r: Restaurant) -> list[Partner]:
return sorted(candidates, key=lambda p: p.idle_since)
class DistanceFee:
def __init__(self, base: int, included_km: float, per_km: int, free_above: int) -> None:
self._base, self._included, self._per_km, self._free_above = base, included_km, per_km, free_above
def fee_cents(self, km: float, subtotal: int) -> int:
if subtotal >= self._free_above:
return 0
return self._base + round(max(0.0, km - self._included) * self._per_km)
class Coupon(Protocol):
code: str
min_subtotal_cents: int
def discount_cents(self, subtotal: int, fee: int) -> int: ...
@dataclass(frozen=True)
class PercentOff:
code: str
percent: int
cap_cents: int
min_subtotal_cents: int
def discount_cents(self, subtotal: int, fee: int) -> int:
return min(self.cap_cents, subtotal * self.percent // 100)
@dataclass(frozen=True)
class FreeDelivery:
code: str
min_subtotal_cents: int
def discount_cents(self, subtotal: int, fee: int) -> int:
return fee
class PricingEngine:
def __init__(self, fee_policy: DistanceFee) -> None:
self._fee_policy = fee_policy
self._coupons: dict[str, Coupon] = {}
def add_coupon(self, c: Coupon) -> None:
self._coupons[c.code] = c
def price(self, lines: list[OrderLine], km: float, coupon_code: str | None) -> Price:
subtotal = sum(l.total_cents for l in lines)
fee = self._fee_policy.fee_cents(km, subtotal)
discount = 0
if coupon_code is not None:
c = self._coupons.get(coupon_code)
if c is None:
raise DeliveryError(f"unknown coupon {coupon_code}")
if subtotal < c.min_subtotal_cents:
raise DeliveryError(f"order too small for {coupon_code}")
discount = min(c.discount_cents(subtotal, fee), subtotal + fee) # never below zero
return Price(subtotal, fee, discount)
class DeliveryService:
ACCEPT_TIMEOUT_S = 5 * 60
PARTNER_RADIUS_KM = 5.0
def __init__(self, pricing: PricingEngine, assignment: AssignmentStrategy,
clock: Callable[[], float]) -> None:
self._pricing, self._assignment, self._clock = pricing, assignment, clock
self._partners: dict[str, Partner] = {}
self._carts: dict[str, Cart] = {}
self._orders: dict[str, Order] = {}
self._awaiting: deque[Order] = deque() # deque append/popleft are thread-safe
self._observers: list[OrderObserver] = []
self._ids = count(1)
self._registry_lock = threading.Lock()
def add_partner(self, id: str, at: Location) -> Partner:
p = Partner(id, at, self._clock())
self._partners[id] = p
return p
def subscribe(self, o: OrderObserver) -> None:
self._observers.append(o)
def cart(self, customer_id: str) -> Cart:
with self._registry_lock:
return self._carts.setdefault(customer_id, Cart())
def place_order(self, customer_id: str, dropoff: Location, coupon: str | None = None) -> Order:
r, lines = self.cart(customer_id).drain()
try:
price = self._pricing.price(lines, r.location.distance_to(dropoff), coupon)
except DeliveryError:
for l in lines: # give the items back
self.cart(customer_id).add(r, l.item_id, l.qty)
raise
o = Order(f"O{next(self._ids)}", customer_id, r, dropoff, tuple(lines), price, self._clock())
self._orders[o.id] = o
with o.lock:
self._notify(o, None, OrderStatus.PLACED)
return o
def accept(self, order_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
self._move(o, OrderStatus.PLACED, OrderStatus.ACCEPTED)
if not self._try_assign(o):
self._awaiting.append(o)
def reject(self, order_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
self._move(o, OrderStatus.PLACED, OrderStatus.REJECTED)
def cancel(self, order_id: str, customer_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
if o.customer_id != customer_id:
raise DeliveryError("not your order")
self._move(o, OrderStatus.PLACED, OrderStatus.CANCELLED)
def expire_unaccepted(self) -> int:
"""Rejects every order the restaurant ignored for too long. Run it from a scheduler."""
now, expired = self._clock(), 0
for o in list(self._orders.values()):
with o.lock:
if o.status is OrderStatus.PLACED and now - o.placed_at >= self.ACCEPT_TIMEOUT_S:
self._move(o, OrderStatus.PLACED, OrderStatus.REJECTED)
expired += 1
return expired
def mark_ready(self, order_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
self._move(o, OrderStatus.ACCEPTED, OrderStatus.READY)
def pick_up(self, order_id: str, partner_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
self._require_partner(o, partner_id)
self._move(o, OrderStatus.READY, OrderStatus.PICKED_UP)
def deliver(self, order_id: str, partner_id: str) -> None:
o = self._get(self._orders, order_id)
with o.lock:
self._require_partner(o, partner_id)
self._move(o, OrderStatus.PICKED_UP, OrderStatus.DELIVERED)
assert o.partner is not None
o.partner.idle_since = self._clock()
o.partner.transition(PartnerStatus.BUSY, PartnerStatus.AVAILABLE)
self.assign_waiting() # outside the lock: touches other orders
def assign_waiting(self) -> None:
for _ in range(len(self._awaiting)):
try:
o = self._awaiting.popleft() # each order is taken by exactly one thread
except IndexError:
return
with o.lock:
needs = o.partner is None and o.status in (OrderStatus.ACCEPTED, OrderStatus.READY)
if needs and not self._try_assign(o):
self._awaiting.append(o)
def _try_assign(self, o: Order) -> bool:
"""Caller holds o.lock."""
free = [p for p in list(self._partners.values()) if p.status is PartnerStatus.AVAILABLE
and p.location.distance_to(o.restaurant.location) <= self.PARTNER_RADIUS_KM]
for p in self._assignment.rank(free, o.restaurant):
if p.transition(PartnerStatus.AVAILABLE, PartnerStatus.BUSY): # atomic claim
o.partner = p
for ob in self._observers:
self._safely(lambda: ob.on_partner_assigned(o, p))
return True
return False
def _move(self, o: Order, frm: OrderStatus, to: OrderStatus) -> None:
"""Caller holds o.lock."""
if o.status is not frm:
raise DeliveryError(f"order {o.id} is {o.status.name}, not {frm.name}")
o.status = to
self._notify(o, frm, to)
def _notify(self, o: Order, frm: OrderStatus | None, to: OrderStatus) -> None:
# called under the order's lock, so each order's events arrive in order
for ob in self._observers:
self._safely(lambda: ob.on_status(o, frm, to))
@staticmethod
def _safely(fn: Callable[[], None]) -> None:
try:
fn()
except Exception as e: # one broken observer must not block the order
print("observer failed:", e)
@staticmethod
def _require_partner(o: Order, partner_id: str) -> None:
if o.partner is None or o.partner.id != partner_id:
raise DeliveryError("not your delivery")
@staticmethod
def _get(m: dict, id: str):
if id not in m:
raise DeliveryError(f"unknown id {id}")
return m[id]
class CustomerFeed(OrderObserver):
"""Example observer: what the customer's app would show."""
def __init__(self) -> None:
self.events: dict[str, list[str]] = {}
def on_status(self, o: Order, frm: OrderStatus | None, to: OrderStatus) -> None:
self.events.setdefault(o.id, []).append(to.name)
def on_partner_assigned(self, o: Order, p: Partner) -> None:
self.events.setdefault(o.id, []).append(f"PARTNER:{p.id}")
class FakeClock:
def __init__(self) -> None:
self.now = 0.0
def __call__(self) -> float:
return self.now
def make_service(clock: FakeClock, assignment: AssignmentStrategy | None = None) -> DeliveryService:
pricing = PricingEngine(DistanceFee(200, 2.0, 50, 2000))
pricing.add_coupon(PercentOff("SAVE20", 20, 150, 500))
pricing.add_coupon(FreeDelivery("FREEDEL", 800))
return DeliveryService(pricing, assignment or NearestToRestaurant(), clock)
R1 = Restaurant("R1", Location(0, 0), MenuItem("burger", "Burger", 450), MenuItem("fries", "Fries", 200))
def demo() -> None:
clock = FakeClock()
d = make_service(clock)
feed = CustomerFeed()
d.subscribe(feed)
d.add_partner("near", Location(1, 0))
d.add_partner("far", Location(4, 0))
d.cart("alice").add(R1, "burger", 2)
d.cart("alice").add(R1, "fries", 1)
o = d.place_order("alice", Location(4, 0), "SAVE20")
assert o.price == Price(1100, 300, 150) and o.price.total == 1250
d.accept(o.id)
assert o.partner is not None and o.partner.id == "near"
d.mark_ready(o.id); d.pick_up(o.id, "near"); d.deliver(o.id, "near")
assert feed.events[o.id] == ["PLACED", "ACCEPTED", "PARTNER:near", "READY", "PICKED_UP", "DELIVERED"]
d.cart("carol").add(R1, "fries", 3)
slow = d.place_order("carol", Location(1, 0))
clock.now += DeliveryService.ACCEPT_TIMEOUT_S - 1
assert d.expire_unaccepted() == 0
clock.now += 1
assert d.expire_unaccepted() == 1 and slow.status is OrderStatus.REJECTED
print("food-delivery: demo checks passed")
if __name__ == "__main__":
demo()
// food-delivery.ts — run with: npx tsx food-delivery.ts
class Location {
constructor(readonly x: number, readonly y: number) {}
distanceTo(o: Location): number { return Math.hypot(this.x - o.x, this.y - o.y); }
}
interface MenuItem { readonly id: string; readonly name: string; readonly priceCents: number }
interface OrderLine { readonly itemId: string; readonly name: string; readonly unitCents: number; readonly qty: number }
class Price {
constructor(readonly subtotal: number, readonly deliveryFee: number, readonly discount: number) {}
get total(): number { return this.subtotal + this.deliveryFee - this.discount; }
}
enum OrderStatus {
PLACED = "PLACED", ACCEPTED = "ACCEPTED", READY = "READY", PICKED_UP = "PICKED_UP",
DELIVERED = "DELIVERED", REJECTED = "REJECTED", CANCELLED = "CANCELLED",
}
enum PartnerStatus { OFFLINE = "OFFLINE", AVAILABLE = "AVAILABLE", BUSY = "BUSY" }
class DeliveryError extends Error {}
class Restaurant {
readonly menu: ReadonlyMap<string, MenuItem>;
constructor(readonly id: string, readonly location: Location, ...items: MenuItem[]) {
this.menu = new Map(items.map((i) => [i.id, i]));
}
}
class Cart {
private restaurant: Restaurant | null = null;
private readonly quantities = new Map<string, number>();
add(r: Restaurant, itemId: string, qty: number): void {
if (qty <= 0 || !r.menu.has(itemId)) throw new DeliveryError("bad item or quantity");
if (this.restaurant && this.restaurant !== r) throw new DeliveryError("cart holds another restaurant's items");
this.restaurant = r;
this.quantities.set(itemId, (this.quantities.get(itemId) ?? 0) + qty);
}
/** Snapshot prices into order lines and empty the cart. */
drain(): [Restaurant, OrderLine[]] {
const r = this.restaurant;
if (!r) throw new DeliveryError("cart is empty");
const lines = [...this.quantities].map(([id, qty]) => {
const m = r.menu.get(id)!;
return { itemId: id, name: m.name, unitCents: m.priceCents, qty };
});
this.restaurant = null; this.quantities.clear();
return [r, lines];
}
}
class Partner {
private _status = PartnerStatus.AVAILABLE;
constructor(readonly id: string, public location: Location, public idleSince: number) {}
get status(): PartnerStatus { return this._status; }
transition(from: PartnerStatus, to: PartnerStatus): boolean {
if (this._status !== from) return false;
this._status = to;
return true;
}
}
class Order {
status = OrderStatus.PLACED;
partner: Partner | null = null;
constructor(readonly id: string, readonly customerId: string, readonly restaurant: Restaurant,
readonly dropoff: Location, readonly lines: readonly OrderLine[], readonly price: Price,
readonly placedAt: number) {}
}
interface OrderObserver {
onStatus(o: Order, from: OrderStatus | null, to: OrderStatus): void;
onPartnerAssigned?(o: Order, p: Partner): void;
}
interface AssignmentStrategy { rank(candidates: Partner[], r: Restaurant): Partner[] }
function rankBy(c: Partner[], score: (p: Partner) => number): Partner[] {
return c.map((p) => ({ p, s: score(p) })).sort((a, b) => a.s - b.s).map((e) => e.p);
}
class NearestToRestaurant implements AssignmentStrategy {
rank(c: Partner[], r: Restaurant): Partner[] { return rankBy(c, (p) => p.location.distanceTo(r.location)); }
}
class LongestIdleFirst implements AssignmentStrategy {
rank(c: Partner[]): Partner[] { return rankBy(c, (p) => p.idleSince); }
}
class DistanceFee {
constructor(private base: number, private includedKm: number, private perKm: number, private freeAbove: number) {}
feeCents(km: number, subtotal: number): number {
if (subtotal >= this.freeAbove) return 0;
return this.base + Math.round(Math.max(0, km - this.includedKm) * this.perKm);
}
}
interface Coupon {
readonly code: string;
readonly minSubtotalCents: number;
discountCents(subtotal: number, fee: number): number;
}
class PercentOff implements Coupon {
constructor(readonly code: string, private percent: number, private capCents: number, readonly minSubtotalCents: number) {}
discountCents(subtotal: number): number { return Math.min(this.capCents, Math.floor((subtotal * this.percent) / 100)); }
}
class FreeDelivery implements Coupon {
constructor(readonly code: string, readonly minSubtotalCents: number) {}
discountCents(_subtotal: number, fee: number): number { return fee; }
}
class PricingEngine {
private readonly coupons = new Map<string, Coupon>();
constructor(private feePolicy: DistanceFee) {}
addCoupon(c: Coupon): void { this.coupons.set(c.code, c); }
price(lines: readonly OrderLine[], km: number, couponCode?: string): Price {
const subtotal = lines.reduce((s, l) => s + l.unitCents * l.qty, 0);
const fee = this.feePolicy.feeCents(km, subtotal);
let discount = 0;
if (couponCode !== undefined) {
const c = this.coupons.get(couponCode);
if (!c) throw new DeliveryError(`unknown coupon ${couponCode}`);
if (subtotal < c.minSubtotalCents) throw new DeliveryError(`order too small for ${couponCode}`);
discount = Math.min(c.discountCents(subtotal, fee), subtotal + fee); // never below zero
}
return new Price(subtotal, fee, discount);
}
}
class DeliveryService {
static readonly ACCEPT_TIMEOUT_MS = 5 * 60_000;
static readonly PARTNER_RADIUS_KM = 5;
private readonly partners = new Map<string, Partner>();
private readonly carts = new Map<string, Cart>();
private readonly orders = new Map<string, Order>();
private awaiting: Order[] = [];
private readonly observers: OrderObserver[] = [];
private nextId = 1;
constructor(private pricing: PricingEngine, private assignment: AssignmentStrategy, private clock: () => number) {}
addPartner(id: string, at: Location): Partner {
const p = new Partner(id, at, this.clock()); this.partners.set(id, p); return p;
}
subscribe(o: OrderObserver): void { this.observers.push(o); }
cart(customerId: string): Cart {
let c = this.carts.get(customerId);
if (!c) { c = new Cart(); this.carts.set(customerId, c); }
return c;
}
placeOrder(customerId: string, dropoff: Location, coupon?: string): Order {
const [r, lines] = this.cart(customerId).drain();
let price: Price;
try {
price = this.pricing.price(lines, r.location.distanceTo(dropoff), coupon);
} catch (e) {
for (const l of lines) this.cart(customerId).add(r, l.itemId, l.qty); // give the items back
throw e;
}
const o = new Order(`O${this.nextId++}`, customerId, r, dropoff, lines, price, this.clock());
this.orders.set(o.id, o);
this.notify(o, null, OrderStatus.PLACED);
return o;
}
accept(orderId: string): void {
const o = get(this.orders, orderId);
this.move(o, OrderStatus.PLACED, OrderStatus.ACCEPTED);
if (!this.tryAssign(o)) this.awaiting.push(o);
}
reject(orderId: string): void { this.move(get(this.orders, orderId), OrderStatus.PLACED, OrderStatus.REJECTED); }
cancel(orderId: string, customerId: string): void {
const o = get(this.orders, orderId);
if (o.customerId !== customerId) throw new DeliveryError("not your order");
this.move(o, OrderStatus.PLACED, OrderStatus.CANCELLED);
}
/** Rejects every order the restaurant ignored for too long. Call it from setInterval. */
expireUnaccepted(): number {
const now = this.clock();
let expired = 0;
for (const o of this.orders.values()) {
if (o.status === OrderStatus.PLACED && now - o.placedAt >= DeliveryService.ACCEPT_TIMEOUT_MS) {
this.move(o, OrderStatus.PLACED, OrderStatus.REJECTED); expired++;
}
}
return expired;
}
markReady(orderId: string): void { this.move(get(this.orders, orderId), OrderStatus.ACCEPTED, OrderStatus.READY); }
pickUp(orderId: string, partnerId: string): void {
const o = get(this.orders, orderId);
requirePartner(o, partnerId);
this.move(o, OrderStatus.READY, OrderStatus.PICKED_UP);
}
deliver(orderId: string, partnerId: string): void {
const o = get(this.orders, orderId);
requirePartner(o, partnerId);
this.move(o, OrderStatus.PICKED_UP, OrderStatus.DELIVERED);
o.partner!.idleSince = this.clock();
o.partner!.transition(PartnerStatus.BUSY, PartnerStatus.AVAILABLE);
this.assignWaiting();
}
assignWaiting(): void {
const waiting = this.awaiting;
this.awaiting = [];
for (const o of waiting) {
const needs = o.partner === null && (o.status === OrderStatus.ACCEPTED || o.status === OrderStatus.READY);
if (needs && !this.tryAssign(o)) this.awaiting.push(o);
}
}
private tryAssign(o: Order): boolean {
const free = [...this.partners.values()].filter((p) => p.status === PartnerStatus.AVAILABLE
&& p.location.distanceTo(o.restaurant.location) <= DeliveryService.PARTNER_RADIUS_KM);
for (const p of this.assignment.rank(free, o.restaurant)) {
if (p.transition(PartnerStatus.AVAILABLE, PartnerStatus.BUSY)) {
o.partner = p;
for (const ob of this.observers) safely(() => ob.onPartnerAssigned?.(o, p));
return true;
}
}
return false;
}
private move(o: Order, from: OrderStatus, to: OrderStatus): void {
if (o.status !== from) throw new DeliveryError(`order ${o.id} is ${o.status}, not ${from}`);
o.status = to;
this.notify(o, from, to);
}
private notify(o: Order, from: OrderStatus | null, to: OrderStatus): void {
for (const ob of this.observers) safely(() => ob.onStatus(o, from, to));
}
}
function safely(fn: () => void): void {
try { fn(); } catch (e) { console.error("observer failed:", e); }
}
function requirePartner(o: Order, partnerId: string): void {
if (o.partner?.id !== partnerId) throw new DeliveryError("not your delivery");
}
function get<T>(m: Map<string, T>, id: string): T {
const v = m.get(id);
if (v === undefined) throw new DeliveryError(`unknown id ${id}`);
return v;
}
/** Example observer: what the customer's app would show. */
class CustomerFeed implements OrderObserver {
readonly events = new Map<string, string[]>();
private log(o: Order, e: string): void { this.events.set(o.id, [...(this.events.get(o.id) ?? []), e]); }
onStatus(o: Order, _from: OrderStatus | null, to: OrderStatus): void { this.log(o, to); }
onPartnerAssigned(o: Order, p: Partner): void { this.log(o, `PARTNER:${p.id}`); }
}
function assert(cond: unknown, msg: string): asserts cond { if (!cond) throw new Error("FAILED: " + msg); }
let now = 0;
function makeService(assignment: AssignmentStrategy = new NearestToRestaurant()): DeliveryService {
const pricing = new PricingEngine(new DistanceFee(200, 2, 50, 2000));
pricing.addCoupon(new PercentOff("SAVE20", 20, 150, 500));
pricing.addCoupon(new FreeDelivery("FREEDEL", 800));
return new DeliveryService(pricing, assignment, () => now);
}
const R1 = new Restaurant("R1", new Location(0, 0),
{ id: "burger", name: "Burger", priceCents: 450 }, { id: "fries", name: "Fries", priceCents: 200 });
const later = <T>(fn: () => T) => new Promise<T>((res) => setTimeout(() => res(fn()), Math.random() * 5));
async function main(): Promise<void> {
const d = makeService();
const feed = new CustomerFeed();
d.subscribe(feed);
d.addPartner("near", new Location(1, 0));
d.addPartner("far", new Location(4, 0));
d.cart("alice").add(R1, "burger", 2);
d.cart("alice").add(R1, "fries", 1);
const o = d.placeOrder("alice", new Location(4, 0), "SAVE20");
assert(o.price.subtotal === 1100 && o.price.deliveryFee === 300 && o.price.total === 1250, "price");
d.accept(o.id);
assert(o.partner?.id === "near", "nearest partner");
d.markReady(o.id); d.pickUp(o.id, "near"); d.deliver(o.id, "near");
assert(feed.events.get(o.id)!.join() === "PLACED,ACCEPTED,PARTNER:near,READY,PICKED_UP,DELIVERED", "events");
d.cart("carol").add(R1, "fries", 3);
const slow = d.placeOrder("carol", new Location(1, 0));
now += DeliveryService.ACCEPT_TIMEOUT_MS - 1;
assert(d.expireUnaccepted() === 0, "not yet");
now += 1;
assert(d.expireUnaccepted() === 1 && slow.status === OrderStatus.REJECTED, "auto-rejected");
// 20 accepts arriving as separate events in random order, 5 partners
const c = makeService();
for (let i = 0; i < 5; i++) c.addPartner(`p${i}`, new Location(i * 0.2, 0));
const orders = Array.from({ length: 20 }, (_, i) => {
c.cart(`c${i}`).add(R1, "burger", 1);
return c.placeOrder(`c${i}`, new Location(1, 1));
});
await Promise.all(orders.map((x) => later(() => c.accept(x.id))));
const ids = orders.flatMap((x) => (x.partner ? [x.partner.id] : []));
assert(ids.length === 5 && new Set(ids).size === 5, "5 distinct partners");
// accept and the timeout sweep fire as separate events: exactly one wins
for (let i = 0; i < 50; i++) {
now = 0;
const s = makeService();
s.cart("c").add(R1, "burger", 1);
const x = s.placeOrder("c", new Location(1, 0));
now = DeliveryService.ACCEPT_TIMEOUT_MS;
const [accepted, expired] = await Promise.all([
later(() => { try { s.accept(x.id); return true; } catch { return false; } }),
later(() => s.expireUnaccepted()),
]);
assert(accepted !== (expired === 1), "exactly one winner");
}
console.log("food-delivery: all checks passed");
}
main();
export {}; // makes this file a module, so names do not clash with DOM globals
Run: javac -d out Main.java && java -ea -cp out Main, python food_delivery.py, npx tsx food-delivery.ts (and tsc --strict passes).
Three details are easy to miss in review:
placeOrderreturns the items if pricing fails.drain()empties the cart before pricing, so a rejected coupon would otherwise silently delete the customer's cart.assignWaitingpolls each order exactly once per pass. It bounds the loop by the queue's size at entry, so an order that's put back can't make the loop spin forever. Becausepollis atomic, two threads running it at once never handle the same order.delivercallsassignWaitingafter releasing the order lock.assignWaitingtakes other orders' locks. Taking them while holding this one would allow a lock-ordering deadlock.
7. Concurrency
| Shared state | Contention | Mechanism |
|---|---|---|
Partner.status | Many accepted orders competing for nearby partners | CAS AVAILABLE → BUSY |
Order.status, Order.partner | Restaurant, timeout sweeper, partner app, customer | per-order lock, all transitions via move |
Cart | Two tabs of the same customer | the cart's own lock. drain is atomic |
| Waiting queue | accept and every deliver | ConcurrentLinkedQueue (a deque in Python), poll-once semantics |
| Observer list | subscribe while notifying | CopyOnWriteArrayList |
Partner assignment. Twenty restaurants accept at once and five partners are free. Every tryAssign ranks the same snapshot and tries the same nearest partner first. Exactly one CAS succeeds, and the rest fall through to the next candidate. No partner gets two orders, and nobody holds a global lock. The Java and Python tests start 20 accepts behind a latch or barrier and assert 5 assignments to 5 distinct partners and 15 waiting orders. Then they deliver one order and assert that the freed partner was handed a waiting order.
Accept versus timeout. The sweeper and the restaurant both want to move the order out of PLACED. Both go through move(o, PLACED, …) under the order's lock, and move re-checks the current status. Whoever gets the lock first wins, and the other sees a status that isn't PLACED and stops. The tests set the clock exactly at the deadline, release both threads together 300 times, and assert three things: exactly one winner, a final status that matches the winner, and exactly one of ACCEPTED/REJECTED in the event stream.
Notice what the sweeper doesn't do: it doesn't read the status outside the lock and then act. A sweeper that collects "orders older than 5 minutes" first and rejects them later reintroduces the race. The check must be repeated inside the lock.
Lock order. Order lock, then partner CAS (non-blocking). One order lock at a time, never two. That's the whole deadlock analysis.
TypeScript. Every method is synchronous, so each one is atomic on Node's event loop. The TS main still fires accepts and the sweeper as separate timer callbacks in random order to show the invariants hold. If you add an await (say, calling the restaurant's POS before accepting), re-check status === PLACED after the await, or the timeout can slip in.
See thread-safe class design for the confinement, CAS and lock-granularity trade-offs used here.
8. The interviewer adds...
"Launch coupon: first 10,000 uses only"
A usage limit is shared, contended state, so it needs the same CAS discipline as partners. A decorator adds the limit to any coupon:
/** Decorates any coupon with a global redemption limit, enforced with CAS. */
final class LimitedCoupon implements Coupon {
private final Coupon inner; private final AtomicInteger remaining;
LimitedCoupon(Coupon inner, int maxUses) { this.inner = inner; this.remaining = new AtomicInteger(maxUses); }
public String code() { return inner.code(); }
public long minSubtotalCents() { return inner.minSubtotalCents(); }
public long discountCents(long subtotal, long fee) { return inner.discountCents(subtotal, fee); }
boolean tryRedeem() {
while (true) {
int left = remaining.get();
if (left == 0) return false;
if (remaining.compareAndSet(left, left - 1)) return true;
}
}
void release() { remaining.incrementAndGet(); } // order rejected or cancelled
}
// PricingEngine.price, after the min-subtotal check:
// if (c instanceof LimitedCoupon l && !l.tryRedeem()) throw new DeliveryException("coupon used up");
Tested: 200 threads race for a 10-use coupon and exactly 10 win. A released use can be taken exactly once more. Redeem after every other validation, and release on reject or cancel. Otherwise failed orders burn the budget.
"Partners can carry two orders from nearby restaurants"
Replace the binary status with a slot counter. Because BatchingPartner keeps the status/transition contract, DeliveryService doesn't change at all, which is Liskov substitution doing real work:
class BatchingPartner(Partner):
"""Carries up to `capacity` orders. Looks AVAILABLE while it has room, so the service is unchanged."""
def __init__(self, id: str, location: Location, now: float, capacity: int) -> None:
super().__init__(id, location, now)
self._capacity, self._load = capacity, 0
@property
def status(self) -> PartnerStatus:
return PartnerStatus.AVAILABLE if self._load < self._capacity else PartnerStatus.BUSY
def transition(self, frm: PartnerStatus, to: PartnerStatus) -> bool:
with self._lock:
if frm is PartnerStatus.AVAILABLE and to is PartnerStatus.BUSY and self._load < self._capacity:
self._load += 1 # claim one slot
return True
if frm is PartnerStatus.BUSY and to is PartnerStatus.AVAILABLE and self._load > 0:
self._load -= 1 # free one slot
return True
return False
# DeliveryService.add_partner gains a capacity argument and builds a BatchingPartner when it is > 1.
Tested: with capacity 2, the first two orders get the bike and the third waits. After one delivery, the freed slot goes to the waiting order. A real batcher also checks that the second pickup is on the way, which is a new AssignmentStrategy that scores detour distance.
"The restaurant tablet shows how many orders are in the kitchen"
That's derived state, built entirely from events, so it's just another observer:
/** Restaurant tablet: live count of orders in the kitchen. Pure observer, the service is untouched. */
class KitchenDisplay implements OrderObserver {
private readonly open = new Map<string, Set<string>>(); // restaurantId -> order ids
onStatus(o: Order, _from: OrderStatus | null, to: OrderStatus): void {
const ids = this.open.get(o.restaurant.id) ?? new Set<string>();
if (to === OrderStatus.ACCEPTED) ids.add(o.id);
if (to === OrderStatus.PICKED_UP || to === OrderStatus.CANCELLED) ids.delete(o.id);
this.open.set(o.restaurant.id, ids);
}
inKitchen(restaurantId: string): number { return this.open.get(restaurantId)?.size ?? 0; }
}
Tested: three accepted orders give 3, and after one pickup the count is 2. The same shape produces an analytics counter, an SLA monitor ("accepted but not ready after 30 minutes") or a support dashboard, all without touching the core.
9. Tests
import sys
import threading
from concurrent.futures import ThreadPoolExecutor
from food_delivery import (R1, CustomerFeed, DeliveryError, DeliveryService, FakeClock, Location,
MenuItem, OrderObserver, OrderStatus, Restaurant, make_service)
sys.setswitchinterval(1e-6)
def raises(fn) -> bool:
try:
fn()
return False
except DeliveryError:
return True
def test_cart_rules_and_coupon_failure_keeps_items():
d = make_service(FakeClock())
d.cart("bob").add(R1, "burger", 1)
other = Restaurant("R2", Location(9, 9), MenuItem("x", "X", 100))
assert raises(lambda: d.cart("bob").add(other, "x", 1))
assert raises(lambda: d.place_order("bob", Location(1, 0), "FREEDEL")) # 450 < 800 minimum
d.cart("bob").add(R1, "burger", 1) # items came back: now 900
assert d.place_order("bob", Location(1, 0), "FREEDEL").price.total == 900
def test_illegal_transitions():
d = make_service(FakeClock())
d.cart("c").add(R1, "fries", 1)
o = d.place_order("c", Location(1, 0))
assert raises(lambda: d.mark_ready(o.id)) # not accepted yet
assert raises(lambda: d.cancel(o.id, "someone-else"))
d.cancel(o.id, "c")
assert raises(lambda: d.accept(o.id))
assert o.status is OrderStatus.CANCELLED
def test_broken_observer_does_not_block_orders():
class Broken(OrderObserver):
def on_status(self, o, frm, to):
raise RuntimeError("push service down")
d = make_service(FakeClock())
d.subscribe(Broken())
feed = CustomerFeed()
d.subscribe(feed)
d.cart("c").add(R1, "fries", 1)
o = d.place_order("c", Location(1, 0))
d.accept(o.id)
assert o.status is OrderStatus.ACCEPTED and feed.events[o.id][:2] == ["PLACED", "ACCEPTED"]
def test_concurrent_accepts_never_share_a_partner():
for _ in range(30):
d = make_service(FakeClock())
for i in range(5):
d.add_partner(f"p{i}", Location(i * 0.2, 0))
orders = []
for i in range(20):
d.cart(f"c{i}").add(R1, "burger", 1)
orders.append(d.place_order(f"c{i}", Location(1, 1)))
barrier = threading.Barrier(20)
def accept(o):
barrier.wait()
d.accept(o.id)
with ThreadPoolExecutor(20) as pool:
list(pool.map(accept, orders))
got = [o.partner.id for o in orders if o.partner]
assert len(got) == 5 and len(set(got)) == 5, got
done = next(o for o in orders if o.partner)
d.mark_ready(done.id); d.pick_up(done.id, done.partner.id); d.deliver(done.id, done.partner.id)
assert sum(1 for o in orders if o is not done and o.partner) == 5 # a waiting order got the partner
def test_accept_racing_timeout():
for _ in range(300):
clock = FakeClock()
d = make_service(clock)
feed = CustomerFeed()
d.subscribe(feed)
d.cart("c").add(R1, "burger", 1)
o = d.place_order("c", Location(1, 0))
clock.now = DeliveryService.ACCEPT_TIMEOUT_S # the deadline is right now
barrier = threading.Barrier(2)
result = {}
def accept():
barrier.wait()
result["accepted"] = not raises(lambda: d.accept(o.id))
def sweep():
barrier.wait()
result["expired"] = d.expire_unaccepted()
threads = [threading.Thread(target=accept), threading.Thread(target=sweep)]
for t in threads: t.start()
for t in threads: t.join()
assert result["accepted"] != (result["expired"] == 1)
assert o.status is (OrderStatus.ACCEPTED if result["accepted"] else OrderStatus.REJECTED)
assert ("ACCEPTED" in feed.events[o.id]) != ("REJECTED" in feed.events[o.id])
if __name__ == "__main__":
for name, fn in list(globals().items()):
if name.startswith("test_"):
fn()
print("ok", name)
The suite covers the rules that break in production: cart restaurant mixing, the cart surviving a failed coupon, illegal transitions, a crashing observer, and both races. The clock is a FakeClock object, so the 5-minute timeout is tested by assigning clock.now, not by sleeping. See designing for testability.
10. Common mistakes
- Order lines that reference live menu items. Prices and names change, and history must not.
- Searching for a partner only at
READY. That adds the full search time to every delivery. Search starts atACCEPTED. - Treating "no partner" as a failure. It's a normal wait state. Queue the order and retry on every partner release.
- A timeout implemented as
sleep(5 min)per order. That's a thread per order and untestable. Use one sweeper and an injected clock. - Notifying inside a loop that can throw. One bad subscriber aborts the transition halfway, after the status already changed.
- Check-then-act in the sweeper, by collecting stale orders first and rejecting them later without re-checking.
- Coupons that make totals negative. Clamp the discount to subtotal + fee.
11. Interview follow-ups
How would you make the timeout precise without scanning every order?
Keep a min-heap (or a delay queue) keyed by deadline and pop only expired entries. A sweep every few seconds over a heap costs O(expired · log n). The lock-and-recheck logic in expireUnaccepted doesn't change.
What if the restaurant accepts but the partner never arrives?
That's a second timeout on ACCEPTED/READY with an assigned partner. Release the partner (CAS BUSY → AVAILABLE), clear order.partner, and put the order back in the waiting queue, all under the order lock.
Why not assign the partner before the restaurant accepts?
A rejected order would have tied up a partner for nothing. Some platforms pre-assign for restaurants with very high acceptance rates. That's a policy you'd express as another strategy plus a flag on Restaurant.
How do you stop the same customer placing two orders from two tabs?
drain() is atomic, so only one tab gets the items and the other sees "cart is empty". For idempotency against retries, have the client send an order key and keep a map from key to order.
How would observers work across processes?
DeliveryService publishes events to a broker. Each consumer keeps its own offset. Ordering per order is kept by partitioning on order id. The in-process OrderObserver interface becomes the adapter that publishes.
How would you price surge or peak hours?
Wrap DistanceFee in a PeakHourFee decorator that reads the injected clock. Coupons still compute from the fee they're given, so FreeDelivery stays correct under surge.