Design an Elevator System: Low-Level Design Interview Walkthrough

"Design an elevator" is a classic low-level design prompt, and an easy one to get lost in. There are buttons inside and outside the car, doors, weight limits, several cars, emergency modes. The interviewer is not looking for all of it. The core is one small object that decides where a single car goes next, and a candidate who gets that decision right, with a clear reason, has most of the answer. The rest is layering.

The problem it solves

A car sits in a shaft. People press buttons for floors, at any time, in any order. The controller must decide, on every tick, whether to move up, move down, stop and open the doors, or wait. A good policy serves everyone eventually, does not waste travel, and never behaves in a way that feels broken, such as reversing halfway to a floor someone is waiting at.

The naive answer is a queue: serve buttons in the order they were pressed. It sounds fair and performs terribly, because the car zigzags across the building to honour arrival order.

The intuition

Model the car as a small state machine. Its state is a current floor, a direction (idle, up or down) and a set of pending floors. Two rules do almost all the work:

• An idle car takes its direction from the first request: up if the floor is above, down if below. Idle is a real state, not a missing one.
• A moving car keeps its direction while anything is left ahead of it. The next stop is the nearest pending floor in the current direction. Only when nothing is ahead does it turn around.

Pending floors live in a set because arrival order is never consulted; only position relative to the car matters. A request behind the car is not rejected and does not flip the heading. It waits for the return sweep.

This policy has a name in disk scheduling, where a read head faces the same problem: LOOK, a variant of the elevator algorithm SCAN that turns at the last request instead of running to the end of the shaft.

The object design follows from the rules. A Car owns its floor, direction and stops. Buttons inside the car and hall buttons outside both end in a request; a hall button also carries a direction, which a fuller design uses so a car heading up does not stop for someone who wants to go down. With several cars, a Dispatcher assigns each hall call to the car with the lowest estimated cost, typically one already moving toward that floor in the right direction. If the interviewer pushes on idle, moving and doors-open behaviour, the state pattern is the natural way to split it.

Watch it run

The animation is the lesson's car. It stands at floor 6 with no heading, and idle is a real state, not a missing one. press(9): the floor joins the pending set, a set because arrival order will never be consulted. The car is idle, so the first request sets the heading: 9 is above 6, so it goes up. press(4) arrives second, and it is behind the car. The heading does not flip; a request behind the car waits for the turn, which is what stops a lift feeling broken. next_stop() filters the set to what is ahead in the current direction, and nothing else is even considered. 4 is below 6, so it is filtered out, and 9 is the next stop, not because it was pressed first. Only when nothing is left above does the car turn, and 4 is served on the way down.

The code

The car as a state machine, one floor per tick. Pressing the floor the idle car is already on just opens the doors. The lesson's scenario serves 9, then 4, and travels 8 floors:

class Car:
    """One elevator car: a direction, a set of pending floors, one floor per tick."""
    def __init__(self, floor=0):
        self.floor, self.direction, self.stops = floor, "idle", set()
        self.served, self.travelled = [], 0

    def press(self, f):
        if f == self.floor and self.direction == "idle":
            self.served.append(f)                  # already here: just open the doors
            return
        self.stops.add(f)                          # a set: arrival order is never used
        if self.direction == "idle":               # the first request sets the heading
            self.direction = "up" if f > self.floor else "down"

    def next_stop(self):
        up = self.direction == "up"
        ahead = [f for f in self.stops if (f > self.floor if up else f < self.floor)]
        return (min if up else max)(ahead) if ahead else None

    def step(self):
        if not self.stops:
            self.direction = "idle"
            return
        if self.next_stop() is None:               # nothing ahead: turn around
            self.direction = "down" if self.direction == "up" else "up"
        self.floor += 1 if self.direction == "up" else -1
        self.travelled += 1
        if self.floor in self.stops:               # doors open here
            self.stops.remove(self.floor)
            self.served.append(self.floor)
        if not self.stops:
            self.direction = "idle"

car = Car(6)
car.press(9)
car.press(4)
print(car.direction, car.next_stop())              # up 9
while car.stops:
    car.step()
print(car.served, car.travelled, car.direction)    # [9, 4] 8 idle

The first-come alternative, and a toy model of a day: 200 seeded runs of 30 random presses over 20 floors, arriving at random times. Same presses, two policies; it reports average travel per run, then the mean and worst wait in ticks:

import random

class FifoCar:
    """The 'fair' alternative: serve buttons strictly in the order pressed."""
    def __init__(self, floor=0):
        self.floor, self.queue, self.served, self.travelled = floor, [], [], 0

    def press(self, f):
        if f not in self.queue:
            self.queue.append(f)

    def step(self):
        if not self.queue:
            return
        target = self.queue[0]
        if self.floor != target:
            self.floor += 1 if target > self.floor else -1
            self.travelled += 1
        if self.floor == target:
            self.served.append(self.queue.pop(0))

def run(car, arrivals, ticks):
    """arrivals: tick -> floors pressed. Returns total travel and every wait."""
    pressed_at, waits = {}, []
    for t in range(ticks):
        before = len(car.served)
        for f in arrivals.get(t, []):
            if f not in pressed_at:                # a lit button stays lit
                pressed_at[f] = t
                car.press(f)
        car.step()
        for f in car.served[before:]:
            waits.append(t - pressed_at.pop(f))
    return car.travelled, waits

random.seed(26)
travel, waits = {"look": 0, "fifo": 0}, {"look": [], "fifo": []}
for _ in range(200):
    arrivals = {}
    for _ in range(30):
        arrivals.setdefault(random.randrange(150), []).append(random.randrange(20))
    for name, make in (("look", Car), ("fifo", FifoCar)):
        t, w = run(make(0), arrivals, 2_000)
        travel[name] += t
        waits[name] += w
for name in ("look", "fifo"):
    w = waits[name]
    print(name, travel[name] // 200, round(sum(w) / len(w), 1), max(w))
# look 138 10.6 37
# fifo 175 29.4 103

Checked on 3,000 seeded batches of simultaneous presses from a random starting floor: the car must serve every floor exactly once, in the order of a brute-force sweep (everything ahead in the first direction, nearest first, then everything behind), with total travel equal to the sweep's length:

def sweep_reference(start, presses):
    """Brute force: the order and distance a directional sweep must produce."""
    above = sorted(f for f in set(presses) if f > start)
    below = sorted((f for f in set(presses) if f < start), reverse=True)
    order = above + below if presses[0] > start else below + above
    path = [start] + order
    return order, sum(abs(a - b) for a, b in zip(path, path[1:]))

ok = True
for _ in range(3_000):
    start = random.randrange(20)
    presses = [f for f in random.choices(range(20), k=random.randint(1, 8)) if f != start]
    if not presses:
        continue
    car = Car(start)
    for f in presses:
        car.press(f)
    while car.stops:
        car.step()
    order, distance = sweep_reference(start, presses)
    ok &= car.served == order and car.travelled == distance and car.direction == "idle"
print(ok)                                          # True

The complexity

• Per press: O(1), adding to a set.
• Per tick: O(k) to find the next stop among k pending floors. Two sorted structures, one per direction, make it O(log k), which only matters for very tall buildings or many cars.
• Travel: a sweep crosses each floor at most twice per round trip; first-come order can cross the building once per request.

Where it goes wrong

• A queue instead of a set. Arrival order leads to zigzagging, as the toy model shows.
• Reversing for a request behind the car. It starves floors ahead and feels broken to riders.
• No idle state. Without it, the first request cannot set a direction cleanly, and a car with nothing to do keeps a stale heading.
• Ignoring the current floor. A press for the floor the car is standing on should open the doors, not enter the pending set.
• Fairness by rule. Capping worst-case waits is a capacity problem, solved with more cars and a dispatcher, not by returning to first-come order.

When it shows up in interviews

It is a staple of object-oriented design rounds, alongside the parking lot and the vending machine. Expect follow-ups on multiple cars and dispatch cost, hall calls with a direction, doors and overload as extra states, and how you would test the controller without a building. The tick-based step above is the answer to the last one: the controller is a pure function of state and presses, so a test can replay any sequence.

How to say it in an interview

"The car is a state machine with a floor, a direction and a set of pending floors. An idle car takes its direction from the first request. While moving, the next stop is the nearest pending floor ahead; a request behind waits for the turn, and the car reverses only when nothing is left ahead. That is the LOOK sweep. I use a set because arrival order never matters. For several cars I add a dispatcher that assigns each hall call to the cheapest car, and I would test it by replaying press sequences tick by tick."