Food delivery: orders, riders and ETA

Design a food delivery service. Customers fill a cart from one restaurant and place an order. The order moves through its states, the nearest free rider is assigned, an ETA is computed, and listeners are told of each change.

Design the core of a food delivery app. Restaurants have menus. A customer adds items to a cart and places an order. The restaurant accepts and prepares it, a rider picks it up and delivers it, and the customer can cancel early. The system picks the rider, estimates the delivery time and notifies interested parties on every change.

Questions to ask first

  • Can a cart hold items from many restaurants? Assume one restaurant per cart. Adding an item from another restaurant is refused.
  • How do we measure distance and time? Assume a grid with Manhattan distance, one step per tick, and whole ticks passed in by the caller.
  • When is a rider assigned? Assume when the restaurant accepts the order. If no rider is free, the order stays PLACED and the caller can try again.
  • Which rider is chosen? Assume the free rider nearest to the restaurant, and the lowest id when two are equally near.
  • How is the ETA computed? Assume the rider travels to the restaurant while the kitchen cooks, so the food is ready when both are done. Then add the ride to the customer.
  • Until when can a customer cancel? Assume until the food is picked up. After that the call is refused.

Requirements

  • Add restaurants with a location, a preparation time and a menu with prices. Add riders with a location.
  • Build a cart for a customer from one restaurant, adding the same item again increases its quantity.
  • Place an order from the cart at the customer's location. The cart is then empty.
  • Move an order through PLACED, ACCEPTED, PREPARING, PICKED_UP and DELIVERED, and allow CANCELLED while it has not been picked up.
  • Assign the nearest free rider when an order is accepted, and free the rider on delivery or cancel.
  • Compute an ETA tick from distance and preparation time, and notify listeners on every state change.

Out of scope

  • Real maps, payments, ratings and offers.
  • A restaurant rejecting an order, and a rider rejecting a job (see the extensions).
  • Many orders in one rider's bag.

Entities

  • Point: x, y -> distanceTo(other) is the Manhattan distance
  • Restaurant: id, location, prepTicks, menu (item to price) -> price(item), addItem()
  • Rider: id, location, available
  • Cart: one restaurant, item quantities -> add(), total(), isEmpty()
  • Order: id, customer, restaurant, destination, total, state, rider, etaTick
  • OrderState: PLACED, ACCEPTED, PREPARING, PICKED_UP, DELIVERED, CANCELLED -> next(), canCancel()
  • RiderAssignment: picks the rider -> choose(restaurantLocation, available)
  • EtaEstimator: when the food arrives -> deliveryTick(...)
  • OrderListener and OrderEvents: the Observer hook -> onChange(...), publish(order, tick)
  • FoodService: the entry point -> addToCart(), placeOrder(), advance(), cancel()

Classes in the model design

  • Point (class)
  • Restaurant (class)
  • Rider (class)
  • Cart (class)
  • Order (class)
  • OrderState (enum)
  • RiderAssignment (interface)
  • NearestRiderAssignment (class)
  • EtaEstimator (interface)
  • GridEtaEstimator (class)
  • OrderListener (interface)
  • OrderEvents (class)
  • FoodService (class)

The main use case, step by step

  1. Asha adds two burgers and fries from restaurant R1. `FoodService.addToCart` checks the restaurant, the item and the quantity, then adds to her `Cart`. An item from another restaurant would be refused.
  2. She places the order at her location. The service reads the prices into a total of 240, creates an `Order` in PLACED, clears the cart, and calls `OrderEvents.publish`. Every listener hears PLACED.
  3. The restaurant accepts. `advance` sees that the next state is ACCEPTED, so it asks `RiderAssignment` for a rider. `NearestRiderAssignment` picks the free rider closest to the restaurant, the lowest id on a tie. If none is free, the call returns NO_RIDER and the order stays PLACED.
  4. The service marks the rider busy and asks the `EtaEstimator` for the delivery tick. The food is ready after the larger of the cooking time and the rider's ride to the restaurant. Then the ride to Asha is added. The order stores the result.
  5. Each later `advance` moves the order along: PREPARING, then PICKED_UP, where the rider's location becomes the restaurant, then DELIVERED, where it becomes Asha's location and the rider is free again.
  6. After each successful move the service publishes the new state with the tick. Listeners, such as an SMS sender or a screen, are called one by one.
  7. A `cancel` while the order is PLACED, ACCEPTED or PREPARING is allowed. It frees the rider, sets CANCELLED and publishes. After PICKED_UP it returns TOO_LATE and changes nothing.

Patterns used

  • State machine: OrderState says what comes next (next()) and when a cancel is allowed (canCancel()). FoodService.advance performs the side effects of each move.. An order has one valid path and one early exit. With the rules in one enum, no method can move an order to a state it may not reach, and a new state, such as REJECTED, is one edit to the table.
  • Strategy: RiderAssignment (NearestRiderAssignment) and EtaEstimator (GridEtaEstimator).. How to pick a rider and how to estimate time are rules that change on their own. A new city may pick by estimated arrival time, or add a traffic factor. Each is one new class, and FoodService does not change.
  • Observer: OrderEvents holds OrderListener objects. FoodService calls publish after every successful state change.. SMS, push, an analytics counter and a restaurant screen all want to hear about changes. The order flow knows only the listener interface, so a new subscriber needs no change to the service.

Key code

Order state and the order

public enum OrderState {
    PLACED, ACCEPTED, PREPARING, PICKED_UP, DELIVERED, CANCELLED;

    /** The next state on the normal path, or null when the order is finished. */
    public OrderState next() {
        switch (this) {
            case PLACED: return ACCEPTED;
            case ACCEPTED: return PREPARING;
            case PREPARING: return PICKED_UP;
            case PICKED_UP: return DELIVERED;
            default: return null;
        }
    }

    /** A customer can cancel until the food is picked up. */
    public boolean canCancel() { return this == PLACED || this == ACCEPTED || this == PREPARING; }
}

public final class Order {
    private final String id, customer;
    private final Restaurant restaurant;
    private final Point destination;
    private final int total;                    // rupees, read from the cart when placed
    private OrderState state = OrderState.PLACED;
    private Rider rider;
    private int etaTick = -1;

    public Order(String id, String customer, Restaurant restaurant, Point destination, int total) {
        this.id = id; this.customer = customer; this.restaurant = restaurant;
        this.destination = destination; this.total = total;
    }

    public void assign(Rider rider, int etaTick) { this.rider = rider; this.etaTick = etaTick; }
    public void moveTo(OrderState next) { state = next; }
}

Strategies and the observer

public interface RiderAssignment {
    Optional<Rider> choose(Point restaurant, Collection<Rider> available);
}

public final class NearestRiderAssignment implements RiderAssignment {
    @Override public Optional<Rider> choose(Point restaurant, Collection<Rider> available) {
        return available.stream().min(Comparator
            .comparingInt((Rider r) -> r.location().distanceTo(restaurant))
            .thenComparing(Rider::id));               // equally near: the lowest id
    }
}

public interface EtaEstimator {
    int deliveryTick(int acceptTick, Rider rider, Restaurant restaurant, Point customer);
}

/** The rider rides to the restaurant while the kitchen cooks. One grid step is one tick. */
public final class GridEtaEstimator implements EtaEstimator {
    @Override public int deliveryTick(int acceptTick, Rider rider, Restaurant restaurant, Point customer) {
        int ready = Math.max(restaurant.prepTicks(), rider.location().distanceTo(restaurant.location()));
        return acceptTick + ready + restaurant.location().distanceTo(customer);
    }
}

public interface OrderListener {
    void onChange(String orderId, String customer, String state, int tick);
}

public final class OrderEvents {
    private final List<OrderListener> listeners = new ArrayList<>();

    public void subscribe(OrderListener l) { listeners.add(l); }

    public void publish(Order order, int tick) {
        for (OrderListener l : listeners) l.onChange(order.id(), order.customer(), order.state().name(), tick);
    }
}

Advance and cancel in the service

public class FoodService {
    public synchronized String advance(String orderId, int tick) {
        Order o = orders.get(orderId);
        if (o == null) return "NO_ORDER";
        OrderState next = o.state().next();
        if (next == null) return "FINISHED";                          // delivered or cancelled
        if (next == OrderState.ACCEPTED && !assignRider(o, tick)) return "NO_RIDER";   // stays PLACED
        if (next == OrderState.PICKED_UP) o.rider().moveTo(o.restaurant().location());
        if (next == OrderState.DELIVERED) {
            o.rider().moveTo(o.destination());
            o.rider().setAvailable(true);
        }
        o.moveTo(next);
        events.publish(o, tick);                                      // only after the change is complete
        return next.name();
    }

    public synchronized String cancel(String orderId, int tick) {
        Order o = orders.get(orderId);
        if (o == null) return "NO_ORDER";
        if (!o.state().canCancel()) return "TOO_LATE";
        if (o.rider() != null) o.rider().setAvailable(true);          // free the rider where they stand
        o.moveTo(OrderState.CANCELLED);
        events.publish(o, tick);
        return "OK";
    }

    private boolean assignRider(Order o, int tick) {
        List<Rider> free = riders.values().stream().filter(Rider::isAvailable).collect(Collectors.toList());
        Optional<Rider> rider = assignment.choose(o.restaurant().location(), free);
        if (rider.isEmpty()) return false;
        rider.get().setAvailable(false);
        o.assign(rider.get(), eta.deliveryTick(tick, rider.get(), o.restaurant(), o.destination()));
        return true;
    }
}

Deep dives

Modelling the order lifecycle

Weak: Keep a String status and write if (status.equals("PICKED_UP")) in many places. A typo compiles. Any code can set any status, so an order can jump from PLACED to DELIVERED without a rider.

Good: Use an OrderState enum and one advance method. The enum removes typos, and next() gives one valid path. Cancel is a separate method with its own check.

Great: Let the enum own both questions: what comes next and whether a cancel is allowed. Keep the side effects of each move in one place, advance and cancel: assign the rider on ACCEPTED, move the rider on PICKED_UP, free the rider on DELIVERED or CANCELLED. Publish the event last, only when the change is complete, so a listener never sees a half-changed order.

Trade-off: An enum with next() suits a straight path with one exit. If states branch, for example a restaurant that can reject, or each state has different behaviour, a transition table or the State pattern is clearer. Choose the smaller design, and say what would make you change.

Choosing and releasing a rider

Weak: Take the first rider in the list who is free. It works with two riders and gives far riders the nearby jobs. Order of the list decides, and a replay can give a different answer.

Good: Put the choice behind a RiderAssignment strategy. NearestRiderAssignment takes the smallest distance to the restaurant and breaks ties by rider id, so a test always gets the same rider. The service filters for free riders first and passes only those.

Great: Make choosing and marking busy one atomic step, with one lock on the service or an atomic flag on the rider, so two orders cannot get the same rider. When no rider is free, do not change the order: return NO_RIDER and leave it PLACED, so the caller can retry. Update the rider's location at pickup and at delivery, so the next order sees where the rider really is. Free the rider on cancel as well.

Trade-off: Assigning at acceptance wastes no waiting time for the customer, but a rider may wait at the restaurant for a slow kitchen. Assigning when the food is nearly ready cuts waiting but risks having no free rider at that moment. Real services tune this with the prediction of cooking time.

ETA and notification hooks

Weak: Add the three times together: ride to the restaurant, cooking, ride to the customer. It over-estimates, because the rider travels while the food cooks. In the same method, call the SMS service directly after each change. Now the order flow depends on SMS, and a slow or failing SMS call stops an order.

Good: Move the estimate into an EtaEstimator. The food is ready when both the cooking and the ride to the restaurant are done, so take the larger of the two, then add the ride to the customer. Move the messages out of the order flow with the Observer pattern: the service publishes, and listeners decide what to do.

Great: Publish only after the state change is complete, in the order the changes happened, with the tick of that call. Make the publisher catch an exception from one listener and carry on with the others, so one broken subscriber cannot block the order or the rest. Store the ETA on the order when the rider is assigned, and recompute it only on a clear event, such as a new rider.

Trade-off: A synchronous observer is simple and keeps the order of events, but a slow listener delays the caller. An event queue with workers makes the order flow independent of listener speed, and costs ordering guarantees and more moving parts. Start synchronous, and name the queue as the next step.

Now add one more feature

  • Now let a restaurant reject an order. What changes? Add REJECTED to `OrderState`, with moves from PLACED. `advance` stays the same for the normal path, and a new `reject` method frees the rider if one is assigned and publishes. Listeners need no change.
  • Now let a rider carry two orders at once. What changes? A rider has a list of current orders and a capacity. The assignment strategy checks capacity and may prefer a rider already going the same way. The ETA estimator adds the extra stop.
  • Now add a delivery fee that depends on distance and demand. What changes? Add a `FeePolicy` strategy, like the fare in a ride app. The order stores the fee at placement. The cart and the state machine do not change.
  • Now stop orders for items that are sold out. What changes? `Restaurant` tracks availability per item. `addToCart` and `placeOrder` check it and return a new code. Reduce stock inside the same lock as placement so two customers cannot take the last item.
  • Now send an SMS and a push for ACCEPTED and DELIVERED only. What changes? Write two listeners that filter on the state name, and subscribe them. No class in the order flow changes, which shows the observer working.

What each level is expected to show

SDE-1: Restaurants with menus, a single-restaurant cart, an order with named states, assignment of the nearest free rider, and clear codes for bad calls. A `main` that places one order and walks it to DELIVERED is enough.

SDE-2: Everything at SDE-1, plus Strategy for rider assignment and ETA, an Observer for notifications that is published only after a change completes, atomic assign and busy, rider locations kept up to date, and a stated rule for cancel. Discuss rejection, batching and a queue for events as extensions.

Common mistakes

  • Keeping the order status as a free string, so a typo or a jump from PLACED to DELIVERED is possible.
  • Assigning the first free rider in the list and not the nearest, or with no tie rule, so results change between runs.
  • Leaving the rider busy after a cancel, or free while still carrying food, because the flag is changed in several places.
  • Calling the SMS or push service directly inside the order code, so a slow provider blocks the order.
  • Adding cooking time and the rider's ride together for the ETA, when the two overlap.
  • Reading menu prices when the item is added to the cart and never again, or from the live menu when the order is shown, so the total changes later.
  • Letting a cart mix items from two restaurants, which then needs two riders and two states.

Lessons behind this answer