Low-level design · Problem P10 of 15 · Classic systems

Elevator system

Elevators look like a physics problem, but the design question is about two decisions: which car answers a hall call (the scheduler), and in what order a car serves its stops (its movement rule). Make both explicit and the rest is simple.

1. The prompt

The prompt"Design an elevator system for a building with several elevators. People press up or down on a floor (hall calls) and choose a floor inside the car (car calls)."

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

Ask	Assume (unless told otherwise)
How many cars and floors?	Configurable; the demo uses 2 cars and 10 floors.
How is a car chosen?	Nearest car that's idle or already heading that way; others pay a penalty.
How does a car order its stops?	LOOK: keep going while there are stops ahead, then turn.

Must do

Hall calls with a direction, assigned to one car
Car calls from inside
Cars move one floor per tick and open at stops

Must be

Reasonable waiting time, no starvation
Scheduling rule swappable
Simulation-friendly: time advances in ticks

Out of scope

Doors, weight limits, emergency modes (follow-ups)
Real-time hardware control

3. The classes

The class diagram: arrows show who uses or holds whom.

Class	Its one job
ElevatorSystem	Receives calls, asks the scheduler, ticks every car
Car	Its floor, direction and set of stops; one step per tick
Scheduler	Chooses the car for a hall call (strategy)
Dir	UP, DOWN or IDLE

4. How it works

Run the same algorithm as the code. Press a hall call, then Tick to advance time one floor at a time. Dashed cells are a car's pending stops.

5. Patterns and why

Pattern	Where	Why it's worth it here
Strategy	Scheduler (NearestCarScheduler)	Swap in a zone-based or energy-saving scheduler without touching cars
Simulation clock	tick() advances every car one step	Deterministic tests: script calls at given ticks and compare the log
LOOK algorithm	Car.step()	Serves stops in sweeps, so no stop waits forever

Memory hook: "Pick a car, then sweep"The scheduler picks the car; each car keeps going while it has stops ahead, then turns around.

6. The code

The demo scripts calls at given ticks and prints every assignment and door opening, so all three languages can be compared line by line.

from __future__ import annotations
from abc import ABC, abstractmethod
from enum import Enum
from typing import Optional


class Dir(Enum):
    UP = 1
    DOWN = -1
    IDLE = 0


class Car:
    """Moves one floor per tick. Keeps going in its direction while it has stops ahead, then turns (the LOOK rule)."""

    def __init__(self, name: str, floor: int) -> None:
        self.name, self.floor, self.dir = name, floor, Dir.IDLE
        self.stops: set[int] = set()

    def step(self) -> Optional[str]:
        if not self.stops:
            self.dir = Dir.IDLE
            return None
        if self.floor in self.stops:
            self.stops.discard(self.floor)
            return f"opens at {self.floor}"
        ahead = (self.dir is Dir.UP and any(s > self.floor for s in self.stops)) or \
                (self.dir is Dir.DOWN and any(s < self.floor for s in self.stops))
        if not ahead:
            self.dir = Dir.UP if any(s > self.floor for s in self.stops) else Dir.DOWN
        self.floor += self.dir.value
        if self.floor in self.stops:
            self.stops.discard(self.floor)
            return f"opens at {self.floor}"
        return None


class Scheduler(ABC):
    @abstractmethod
    def pick(self, cars: list[Car], floor: int, direction: Dir) -> Car: ...


class NearestCarScheduler(Scheduler):
    """Closest car that is idle, or already heading that way in the same direction; others pay a penalty."""

    PENALTY = 20

    def pick(self, cars: list[Car], floor: int, direction: Dir) -> Car:
        def cost(c: Car) -> int:
            d = abs(c.floor - floor)
            on_the_way = c.dir is direction and (floor - c.floor) * c.dir.value >= 0
            return d if c.dir is Dir.IDLE or on_the_way else d + self.PENALTY
        return min(cars, key=lambda c: (cost(c), c.name))


class ElevatorSystem:
    def __init__(self, cars: list[Car], scheduler: Scheduler) -> None:
        self.cars, self.scheduler = cars, scheduler
        self.by_name = {c.name: c for c in cars}

    def hall_call(self, floor: int, direction: Dir) -> str:
        car = self.scheduler.pick(self.cars, floor, direction)
        car.stops.add(floor)
        return f"hall call {floor} {direction.name} -> car {car.name}"

    def car_call(self, name: str, floor: int) -> str:
        self.by_name[name].stops.add(floor)
        return f"car {name}: button {floor}"

    def tick(self) -> list[str]:
        return [f"car {c.name} {e}" for c in self.cars if (e := c.step())]


if __name__ == "__main__":
    system = ElevatorSystem([Car("A", 0), Car("B", 9)], NearestCarScheduler())
    script = {0: [lambda: system.hall_call(3, Dir.UP), lambda: system.hall_call(8, Dir.DOWN)],
              2: [lambda: system.car_call("B", 0)],
              4: [lambda: system.car_call("A", 7)],
              5: [lambda: system.hall_call(2, Dir.UP)]}
    for t in range(14):
        for action in script.get(t, []):
            print(f"t={t} {action()}")
        for event in system.tick():
            print(f"t={t} {event}")
    print("final floors:", " ".join(f"{c.name}={c.floor}" for c in system.cars))

enum Dir { UP = 1, DOWN = -1, IDLE = 0 }

/** Moves one floor per tick. Keeps going in its direction while it has stops ahead, then turns (the LOOK rule). */
class Car {
  dir = Dir.IDLE;
  readonly stops = new Set<number>();
  constructor(readonly name: string, public floor: number) {}

  step(): string | null {
    if (this.stops.size === 0) {
      this.dir = Dir.IDLE;
      return null;
    }
    if (this.stops.has(this.floor)) {
      this.stops.delete(this.floor);
      return `opens at ${this.floor}`;
    }
    const s = [...this.stops];
    const ahead = (this.dir === Dir.UP && s.some((x) => x > this.floor)) || (this.dir === Dir.DOWN && s.some((x) => x < this.floor));
    if (!ahead) this.dir = s.some((x) => x > this.floor) ? Dir.UP : Dir.DOWN;
    this.floor += this.dir;
    if (this.stops.has(this.floor)) {
      this.stops.delete(this.floor);
      return `opens at ${this.floor}`;
    }
    return null;
  }
}

interface Scheduler { pick(cars: Car[], floor: number, direction: Dir): Car; }

/** Closest car that is idle, or already heading that way in the same direction; others pay a penalty. */
class NearestCarScheduler implements Scheduler {
  static readonly PENALTY = 20;
  pick(cars: Car[], floor: number, direction: Dir): Car {
    const cost = (c: Car) => {
      const d = Math.abs(c.floor - floor);
      const onTheWay = c.dir === direction && (floor - c.floor) * c.dir >= 0;
      return c.dir === Dir.IDLE || onTheWay ? d : d + NearestCarScheduler.PENALTY;
    };
    return [...cars].sort((a, b) => cost(a) - cost(b) || a.name.localeCompare(b.name))[0];
  }
}

class ElevatorSystem {
  private byName: Map<string, Car>;
  constructor(private cars: Car[], private scheduler: Scheduler) { this.byName = new Map(cars.map((c) => [c.name, c])); }

  hallCall(floor: number, direction: Dir): string {
    const car = this.scheduler.pick(this.cars, floor, direction);
    car.stops.add(floor);
    return `hall call ${floor} ${Dir[direction]} -> car ${car.name}`;
  }

  carCall(name: string, floor: number): string {
    this.byName.get(name)!.stops.add(floor);
    return `car ${name}: button ${floor}`;
  }

  tick(): string[] {
    const out: string[] = [];
    for (const c of this.cars) {
      const e = c.step();
      if (e) out.push(`car ${c.name} ${e}`);
    }
    return out;
  }

  floors(): string { return this.cars.map((c) => `${c.name}=${c.floor}`).join(" "); }
}

const system = new ElevatorSystem([new Car("A", 0), new Car("B", 9)], new NearestCarScheduler());
const script = new Map<number, (() => string)[]>([
  [0, [() => system.hallCall(3, Dir.UP), () => system.hallCall(8, Dir.DOWN)]],
  [2, [() => system.carCall("B", 0)]],
  [4, [() => system.carCall("A", 7)]],
  [5, [() => system.hallCall(2, Dir.UP)]],
]);
for (let t = 0; t < 14; t++) {
  for (const action of script.get(t) ?? []) console.log(`t=${t} ${action()}`);
  for (const event of system.tick()) console.log(`t=${t} ${event}`);
}
console.log("final floors:", system.floors());

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.Supplier;
import java.util.stream.Collectors;

enum Dir {
    UP(1), DOWN(-1), IDLE(0);

    final int step;

    Dir(int step) {
        this.step = step;
    }
}

/** Moves one floor per tick. Keeps going in its direction while it has stops ahead, then turns (the LOOK rule). */
class Car {
    final String name;
    int floor;
    Dir dir = Dir.IDLE;
    final Set<Integer> stops = new HashSet<>();

    Car(String name, int floor) {
        this.name = name;
        this.floor = floor;
    }

    String step() {
        if (stops.isEmpty()) {
            dir = Dir.IDLE;
            return null;
        }
        if (stops.remove(floor)) return "opens at " + floor;
        boolean above = stops.stream().anyMatch(s -> s > floor), below = stops.stream().anyMatch(s -> s < floor);
        boolean ahead = (dir == Dir.UP && above) || (dir == Dir.DOWN && below);
        if (!ahead) dir = above ? Dir.UP : Dir.DOWN;
        floor += dir.step;
        if (stops.remove(floor)) return "opens at " + floor;
        return null;
    }
}

interface Scheduler {
    Car pick(List<Car> cars, int floor, Dir direction);
}

/** Closest car that is idle, or already heading that way in the same direction; others pay a penalty. */
class NearestCarScheduler implements Scheduler {
    static final int PENALTY = 20;

    public Car pick(List<Car> cars, int floor, Dir direction) {
        return cars.stream().min(Comparator.comparingInt((Car c) -> {
            int d = Math.abs(c.floor - floor);
            boolean onTheWay = c.dir == direction && (floor - c.floor) * c.dir.step >= 0;
            return c.dir == Dir.IDLE || onTheWay ? d : d + PENALTY;
        }).thenComparing(c -> c.name)).orElseThrow();
    }
}

class ElevatorSystem {
    private final List<Car> cars;
    private final Scheduler scheduler;
    private final Map<String, Car> byName = new LinkedHashMap<>();

    ElevatorSystem(List<Car> cars, Scheduler scheduler) {
        this.cars = cars;
        this.scheduler = scheduler;
        cars.forEach(c -> byName.put(c.name, c));
    }

    synchronized String hallCall(int floor, Dir direction) {
        Car car = scheduler.pick(cars, floor, direction);
        car.stops.add(floor);
        return "hall call " + floor + " " + direction + " -> car " + car.name;
    }

    synchronized String carCall(String name, int floor) {
        byName.get(name).stops.add(floor);
        return "car " + name + ": button " + floor;
    }

    synchronized List<String> tick() {
        List<String> out = new ArrayList<>();
        for (Car c : cars) {
            String e = c.step();
            if (e != null) out.add("car " + c.name + " " + e);
        }
        return out;
    }

    String floors() {
        return cars.stream().map(c -> c.name + "=" + c.floor).collect(Collectors.joining(" "));
    }
}

public class Main {
    public static void main(String[] args) {
        ElevatorSystem system = new ElevatorSystem(List.of(new Car("A", 0), new Car("B", 9)), new NearestCarScheduler());
        Map<Integer, List<Supplier<String>>> script = Map.of(
                0, List.of(() -> system.hallCall(3, Dir.UP), () -> system.hallCall(8, Dir.DOWN)),
                2, List.of(() -> system.carCall("B", 0)),
                4, List.of(() -> system.carCall("A", 7)),
                5, List.of(() -> system.hallCall(2, Dir.UP)));
        for (int t = 0; t < 14; t++) {
            for (Supplier<String> action : script.getOrDefault(t, List.of())) System.out.println("t=" + t + " " + action.get());
            for (String event : system.tick()) System.out.println("t=" + t + " " + event);
        }
        System.out.println("final floors: " + system.floors());
    }
}

Output (the same in all three languages)

t=0 hall call 3 UP -> car A
t=0 hall call 8 DOWN -> car B
t=0 car B opens at 8
t=2 car B: button 0
t=2 car A opens at 3
t=4 car A: button 7
t=5 hall call 2 UP -> car A
t=7 car A opens at 7
t=9 car B opens at 0
t=12 car A opens at 2
final floors: A=2 B=0

7. Concurrency and edge cases

Calls arrive from many floors at once while the system ticks: the call methods and tick must not interleave (the Java version synchronizes them; a real controller often runs one event loop).
Starvation: pure nearest-first can leave a far call waiting; LOOK sweeps guarantee every stop is reached within two sweeps.
Reassignment: a car can fail or fill up; the system should be able to move its hall calls to another car.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

How would you minimise average wait instead?: A scheduler that simulates each car's route with the new stop and picks the smallest added time; same interface.
Express elevators or zones?: Each car has an allowed floor range; the scheduler filters by it.
Weight limit?: The car reports when full; the scheduler skips full cars for hall calls.
How do you test it?: Exactly like the demo: script calls at ticks and assert on the event log.

9. Common mistakes

One giant if-statement for schedulingHard to test and to change. Put it behind an interface.

Serving stops in call order (FIFO)The car zigzags; LOOK sweeps are far more efficient.

Real time and threads per carA tick-based simulation is easier to reason about and test.

10. Check yourself

What is the LOOK rule?

Sweeps, like a disk head.

Why is the scheduler an interface?

Strategy pattern.

Why advance time in ticks?

Same calls, same ticks, same log.

Your turn

Add a third car (5 min). No code changes beyond construction.
Write a smarter scheduler (20 min). Pick the car with the smallest added travel time.