Design an Elevator System
An elevator system models physical hardware — a real-world-entity problem: a car that moves one floor at a time in a single direction, requests arriving from buttons on every floor, and a scheduler that determines which stop to serve next. The rule that the car moves in one direction at a time shapes the class structure, the storage format for pending stops, and the synchronization model.
See It in Action
Requests arrive from two sources, exactly as the classes model them: a hall button on a landing calls the car with a direction (up or down), while a car button inside the elevator selects a destination floor. Press some of each, then step the car and watch it work through the pending stops and go idle when none remain.
Clarifying Requirements
"Design an elevator system for a building" leaves nearly everything open, so start with the questions that bound it. How many elevator cars? Do all cars serve all floors, or are they zoned? What generates requests — hall buttons on each floor, cabin buttons inside the car, or both? Which scheduling algorithm? What happens if a car breaks down?
For this walkthrough we commit to a single elevator car serving all floors in a building of
configurable height. Requests arrive from two sources: hall buttons on a landing (specifying
a floor and a direction of travel) and cabin buttons pressed by a passenger already inside the
car (specifying a destination floor only). The car must serve every requested stop, advance one
floor per step command, and go idle when no stops remain. How it orders those stops — the
movement policy — is the first real design decision, weighed in the design section rather than fixed
here. The demo above previews the car's behavior; the rule behind it is what the next sections
derive.
Core Entities
Scanning the requirements for the nouns that carry state or enforce rules produces a short list.
A Direction is the enum that governs which way the car moves — UP or DOWN. The absence
of a direction means the car is idle; this is represented as None rather than a third enum
value, which keeps the movement logic clean.
A Request is a value object that pairs a floor number with an optional intended direction of travel. Hall calls carry both (the passenger specifies which direction they want to go); cabin presses carry only a floor (the destination is known, direction is irrelevant).
An Elevator is the car itself. It owns its current floor, its current direction of travel,
and the set of floors it still needs to visit. It exposes two public methods: request, which
adds a floor to the target set, and step, which advances the car by one tick.
Finally, something has to decide each tick which floor the car heads to next, given its current floor, direction, and set of pending stops. What rule that decision follows, and whether it lives on the car or in a class of its own, are design decisions the next section works through — for now it is the last responsibility to place.
An ElevatorSystem is the entry point — it owns the elevator and routes incoming commands to the right method. In a single-car design this is thin; in a multi-car system it would own a list of elevators and a dispatcher strategy.
The diagram below shows how the five entities relate to each other.
Designing the Classes
Step 3 of the delivery framework asks you to derive each class's state from the requirements, then assign its behavior as method signatures, before writing a single line of implementation. The guiding principle is Tell, Don't Ask: a class makes decisions about its own state rather than exposing raw fields for callers to inspect and act on.
Direction
The requirement "the car moves in one direction at a time" demands an unambiguous label for
that direction. Two values suffice: UP and DOWN. Idle — the absence of a direction — is
represented as None in Python rather than a third enum member, because the SCAN branching
logic (if direction is UP, if direction is DOWN, else: idle) is cleanest when idle falls
into the else arm automatically.
An enum gives Direction a fixed set of values and prevents misspelled strings from reaching the
comparison logic.
Request
A hall button press carries a floor number and the direction the passenger intends to travel.
A cabin button press carries only a floor. Both sources share the same structure, so a single
value object with floor: int and direction: Optional[Direction] covers both cases.
Request is a pure data holder — it validates nothing and decides nothing. In the current
design, Elevator.request() receives the fields directly rather than a Request object, which
is fine for a single-car system. The class exists to document the contract: the outside world
thinks in terms of a (floor, direction) pair, not a raw integer.
Choosing the movement policy
The car holds a set of pending stops and, each tick, must pick the next floor to move toward. Three rules are worth weighing before settling on one. Before reading on, decide which one serves every waiting passenger within a bounded time without sending the car back and forth.
Decision checkpoint
The car picks its next stop from the pending set each tick. Serve requests in arrival order (FIFO), always head to the nearest pending floor, or sweep in one direction serving every stop before reversing (SCAN/LOOK)?
With the policy settled on SCAN/LOOK — sweep in the current direction, serve every stop along the way, reverse only when none remain ahead — one tick of the car runs the loop below: a request enters the target set, and on each tick the car either moves, opens its doors, or idles.
The next question is where that logic should live.
SchedulingStrategy
The SCAN/LOOK rule describes an algorithm, not a data store. That algorithm — deciding the next
floor to travel toward — could be a method on Elevator, or pulled into a separate class the
elevator calls each tick. Before reading on, decide where the decision logic should live, given
that the policy may well change (nearest-floor, a priority queue, or destination dispatch are all
plausible successors).
Decision checkpoint
Should the SCAN/LOOK 'which floor next' logic be a method inside Elevator, or extracted into a separate SchedulingStrategy the elevator delegates to?
The scheduling algorithm belongs in its own class. Its one method is
next_stop(current_floor, direction, targets) → Optional[int]: the caller provides everything the
algorithm needs, and the strategy returns the next floor to travel toward, or None if targets is
empty. The strategy holds no mutable state — every call is a pure function of its inputs.
Pulling the scheduling algorithm out of Elevator keeps the two concerns separate. An Elevator
that contained the SCAN logic in-line would need to be modified whenever the algorithm changed —
say, to nearest-floor or priority-queue. By delegating to a SchedulingStrategy, the elevator
calls strategy.next_stop(...) on every tick. A different scheduling policy becomes a new strategy
subclass passed to the constructor; Elevator is unchanged.
That leaves how to store the pending stops. Every step tests whether the current floor is a
target and removes it if so, and "nearest stop ahead" needs the floors in order. A sorted list
keeps order ready but pays to insert and remove; a plain set is the other candidate. Before
reading on, decide which fits the operations step performs most often.
Decision checkpoint
Pending stops need fast membership-and-removal each tick plus an ordering for SCAN. Store them in a sorted list, or in a set[int] and recompute order on demand?
Targets are stored as a set[int] rather than a sorted list. Sets give O(1) membership tests
(floor in _targets) and O(1) removal (discard), both of which happen on every step. The
SCAN order is recomputed on each tick by filtering the set into above/below lists, which is O(n)
but n is small — a building has dozens of floors, not millions. This avoids the complexity of
maintaining a sorted structure under concurrent inserts.
Pure SCAN travels to the end of the building before reversing, even if no stops remain. LOOK
reverses as soon as no stops exist in the current direction — which is what next_stop
implements. The two names are often used interchangeably in interviews; what matters is the
reversal rule.
Elevator
Three mutable fields capture the car's entire physical state: current_floor: int (the car's
position), direction: Optional[Direction] (which way it is moving, or None if idle), and
_targets: set[int] (floors the car still needs to visit). A fourth field, _doors_open: bool,
models the one-tick door-open event so that the tick after an arrival returns "idle" or "moving"
rather than "doors open" again.
Two public methods follow from the requirements. request(floor, direction) adds a floor to the
target set after validating it is within the building. step() advances the car by one tick and
returns a status string. Everything else — the strategy, the doors flag — is private. This is
Tell, Don't Ask: callers never read current_floor and decide what to do next; they call
step() and receive the result.
Class Diagram and State Machine
The SCAN algorithm maps cleanly onto three direction states. The state machine below shows the full transition table — idle transitions to Up or Down on the first request, each running state either continues, reverses, or collapses to idle when the target set empties.
Try It Yourself
Before reading the implementation, build it. Implement a function
elevator_system(num_floors, instructions) that replays a sequence of commands and returns
one result line per step command.
Each instruction is a list of strings. There are three commands:
["request", floor, direction] registers a hall button press on the given floor. The direction
is "up" or "down" and records which way the passenger intends to travel. Add the floor to
the elevator's target set.
["select", floor] registers a cabin button press — a passenger already inside the car presses
the button for their destination floor. Add the floor to the target set.
["step"] advances the elevator by one tick using SCAN/LOOK and appends one line to the output:
"Floor N moving up"or"Floor N moving down"while travelling between stops,"Floor N doors open"when the car arrives at a pending stop (remove that floor from the target set),"Floor N idle"when the target set is empty.
The elevator starts at floor 1 with direction idle. Run your solution against the test cases below, then read the reference implementation.
Code Walkthrough
The reference implementation is four small classes and a thin entry function. The walkthrough below builds each class from its design contract, then traces one complete request through the full algorithm.
The enum is two lines. Its value is the lowercase string used in output, so direction.value
produces "up" or "down" directly without a mapping table.
1from enum import Enum
2from typing import Optional
3
4
5class Direction(Enum):
6 UP = "up"
7 DOWN = "down"
Full Solution
1from enum import Enum
2
3from enum import Enum
4from typing import Optional
5
6
7class Direction(Enum):
8 UP = "up"
9 DOWN = "down"
10
11
12class Request:
13 def __init__(self, floor: int, direction: Optional[Direction] = None) -> None:
14 self.floor = floor
15 self.direction = direction
16
17
18class SchedulingStrategy:
19 """Interface for elevator scheduling. Default is SCAN/LOOK."""
20
21 def next_stop(
22 self,
23 current_floor: int,
24 direction: Optional[Direction],
25 targets: set[int],
26 ) -> Optional[int]:
27 """Return the next floor to travel toward, or None if targets is empty."""
28 if not targets:
29 return None
30 if direction is Direction.UP:
31 above = [f for f in targets if f > current_floor]
32 if above:
33 return min(above)
34 # LOOK: reverse; pick the highest floor below
35 below = [f for f in targets if f < current_floor]
36 return max(below) if below else None
37 if direction is Direction.DOWN:
38 below = [f for f in targets if f < current_floor]
39 if below:
40 return max(below)
41 above = [f for f in targets if f > current_floor]
42 return min(above) if above else None
43 # Idle: pick the nearest floor; break ties by going UP
44 return min(targets, key=lambda f: (abs(f - current_floor), -f))
45
46
47class Elevator:
48 def __init__(self, num_floors: int) -> None:
49 self.num_floors: int = num_floors
50 self.current_floor: int = 1
51 self.direction: Optional[Direction] = None # None means idle
52 self._targets: set[int] = set()
53 self._doors_open: bool = False
54 self._strategy: SchedulingStrategy = SchedulingStrategy()
55
56 # --- public mutation -------------------------------------------------
57
58 def request(self, floor: int, direction: Optional[Direction] = None) -> None:
59 """Register an external hall call or an in-car destination."""
60 if 1 <= floor <= self.num_floors:
61 self._targets.add(floor)
62
63 def step(self) -> str:
64 """Advance one tick and return a status string."""
65 # If doors were open last tick, close them and recalculate direction.
66 if self._doors_open:
67 self._doors_open = False
68
69 if not self._targets:
70 self.direction = None
71 return f"Floor {self.current_floor} idle"
72
73 next_stop = self._strategy.next_stop(
74 self.current_floor, self.direction, self._targets
75 )
76
77 if next_stop is None:
78 self.direction = None
79 return f"Floor {self.current_floor} idle"
80
81 # Decide direction of travel toward next_stop.
82 if next_stop > self.current_floor:
83 self.direction = Direction.UP
84 self.current_floor += 1
85 elif next_stop < self.current_floor:
86 self.direction = Direction.DOWN
87 self.current_floor -= 1
88 # else: we are already at next_stop (should be removed below)
89
90 if self.current_floor in self._targets:
91 self._targets.discard(self.current_floor)
92 self._doors_open = True
93 return f"Floor {self.current_floor} doors open"
94
95 # Still travelling — report direction.
96 dir_str = self.direction.value if self.direction else "idle"
97 return f"Floor {self.current_floor} moving {dir_str}"
98
99
100def elevator_system(
101 num_floors: int, instructions: list[list[str]]
102) -> list[str]:
103 elevator = Elevator(num_floors)
104 output: list[str] = []
105 for instruction in instructions:
106 command, *args = instruction
107 if command == "request":
108 floor = int(args[0])
109 direction = Direction(args[1]) if args[1] in ("up", "down") else None
110 elevator.request(floor, direction)
111 elif command == "select":
112 elevator.request(int(args[0]))
113 elif command == "step":
114 output.append(elevator.step())
115 return output
116
117if __name__ == "__main__":
118 num_floors = int(input())
119 instructions = [input().split() for _ in range(int(input()))]
120 res = elevator_system(num_floors, instructions)
121 for line in res:
122 print(line)
1231import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.Scanner;
5import java.util.TreeMap;
6
7class Solution {
8 static class Direction {
9 static final String UP = "up";
10 static final String DOWN = "down";
11 }
12
13 static class SchedulingStrategy {
14 public Integer nextStop(int currentFloor, String direction, TreeMap<Integer, Integer> targets) {
15 if (targets.isEmpty()) return null;
16 if (Direction.UP.equals(direction)) {
17 Integer above = targets.higherKey(currentFloor);
18 if (above != null) return above;
19 Integer below = targets.lowerKey(currentFloor);
20 return below;
21 }
22 if (Direction.DOWN.equals(direction)) {
23 Integer below = targets.lowerKey(currentFloor);
24 if (below != null) return below;
25 Integer above = targets.higherKey(currentFloor);
26 return above;
27 }
28 // Idle: pick nearest floor; break ties by going UP (higher floor wins)
29 Integer best = null;
30 int bestDist = Integer.MAX_VALUE;
31 for (int f : targets.keySet()) {
32 int dist = Math.abs(f - currentFloor);
33 if (dist < bestDist || (dist == bestDist && f > best)) {
34 bestDist = dist;
35 best = f;
36 }
37 }
38 return best;
39 }
40 }
41
42 static class Elevator {
43 int numFloors;
44 int currentFloor;
45 String direction;
46 TreeMap<Integer, Integer> targets;
47 boolean doorsOpen;
48 SchedulingStrategy strategy;
49
50 Elevator(int numFloors) {
51 this.numFloors = numFloors;
52 this.currentFloor = 1;
53 this.direction = null;
54 this.targets = new TreeMap<>();
55 this.doorsOpen = false;
56 this.strategy = new SchedulingStrategy();
57 }
58
59 void request(int floor) {
60 if (floor >= 1 && floor <= numFloors) {
61 targets.put(floor, 1);
62 }
63 }
64
65 String step() {
66 if (doorsOpen) {
67 doorsOpen = false;
68 }
69 if (targets.isEmpty()) {
70 direction = null;
71 return "Floor " + currentFloor + " idle";
72 }
73 Integer nextStop = strategy.nextStop(currentFloor, direction, targets);
74 if (nextStop == null) {
75 direction = null;
76 return "Floor " + currentFloor + " idle";
77 }
78 if (nextStop > currentFloor) {
79 direction = Direction.UP;
80 currentFloor++;
81 } else if (nextStop < currentFloor) {
82 direction = Direction.DOWN;
83 currentFloor--;
84 }
85 if (targets.containsKey(currentFloor)) {
86 targets.remove(currentFloor);
87 doorsOpen = true;
88 return "Floor " + currentFloor + " doors open";
89 }
90 String dirStr = direction != null ? direction : "idle";
91 return "Floor " + currentFloor + " moving " + dirStr;
92 }
93 }
94
95 public static List<String> elevatorSystem(int numFloors, List<List<String>> instructions) {
96 Elevator elevator = new Elevator(numFloors);
97 List<String> output = new ArrayList<>();
98 for (List<String> instruction : instructions) {
99 String command = instruction.get(0);
100 if (command.equals("request")) {
101 int floor = Integer.parseInt(instruction.get(1));
102 String dir = instruction.get(2);
103 elevator.request(floor);
104 } else if (command.equals("select")) {
105 elevator.request(Integer.parseInt(instruction.get(1)));
106 } else if (command.equals("step")) {
107 output.add(elevator.step());
108 }
109 }
110 return output;
111 }
112
113 public static List<String> splitWords(String s) {
114 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
115 }
116
117 public static void main(String[] args) {
118 java.util.Scanner scanner = new java.util.Scanner(System.in);
119 int numFloors = Integer.parseInt(scanner.nextLine());
120 int instructionsLength = Integer.parseInt(scanner.nextLine());
121 List<List<String>> instructions = new ArrayList<>();
122 for (int i = 0; i < instructionsLength; i++) {
123 instructions.add(splitWords(scanner.nextLine()));
124 }
125 scanner.close();
126 List<String> res = elevatorSystem(numFloors, instructions);
127 for (String line : res) {
128 System.out.println(line);
129 }
130 }
131}
1321"use strict";
2
3class Direction {
4 static UP = 'up';
5 static DOWN = 'down';
6}
7
8class SchedulingStrategy {
9 nextStop(currentFloor, direction, targets) {
10 if (targets.size === 0) return null;
11 const sorted = Array.from(targets).sort((a, b) => a - b);
12 if (direction === Direction.UP) {
13 const above = sorted.filter(f => f > currentFloor);
14 if (above.length > 0) return above[0];
15 const below = sorted.filter(f => f < currentFloor);
16 return below.length > 0 ? below[below.length - 1] : null;
17 }
18 if (direction === Direction.DOWN) {
19 const below = sorted.filter(f => f < currentFloor);
20 if (below.length > 0) return below[below.length - 1];
21 const above = sorted.filter(f => f > currentFloor);
22 return above.length > 0 ? above[0] : null;
23 }
24 // Idle: nearest floor; break ties by higher floor
25 let best = null;
26 let bestDist = Infinity;
27 for (const f of targets) {
28 const dist = Math.abs(f - currentFloor);
29 if (dist < bestDist || (dist === bestDist && f > best)) {
30 bestDist = dist;
31 best = f;
32 }
33 }
34 return best;
35 }
36}
37
38class Elevator {
39 constructor(numFloors) {
40 this.numFloors = numFloors;
41 this.currentFloor = 1;
42 this.direction = null;
43 this.targets = new Set();
44 this.doorsOpen = false;
45 this.strategy = new SchedulingStrategy();
46 }
47
48 request(floor) {
49 if (floor >= 1 && floor <= this.numFloors) {
50 this.targets.add(floor);
51 }
52 }
53
54 step() {
55 if (this.doorsOpen) this.doorsOpen = false;
56 if (this.targets.size === 0) {
57 this.direction = null;
58 return `Floor ${this.currentFloor} idle`;
59 }
60 const nextStop = this.strategy.nextStop(this.currentFloor, this.direction, this.targets);
61 if (nextStop === null) {
62 this.direction = null;
63 return `Floor ${this.currentFloor} idle`;
64 }
65 if (nextStop > this.currentFloor) {
66 this.direction = Direction.UP;
67 this.currentFloor++;
68 } else if (nextStop < this.currentFloor) {
69 this.direction = Direction.DOWN;
70 this.currentFloor--;
71 }
72 if (this.targets.has(this.currentFloor)) {
73 this.targets.delete(this.currentFloor);
74 this.doorsOpen = true;
75 return `Floor ${this.currentFloor} doors open`;
76 }
77 const dirStr = this.direction !== null ? this.direction : 'idle';
78 return `Floor ${this.currentFloor} moving ${dirStr}`;
79 }
80}
81
82function elevatorSystem(numFloors, instructions) {
83 const elevator = new Elevator(numFloors);
84 const output = [];
85 for (const instruction of instructions) {
86 const [command, ...args] = instruction;
87 if (command === 'request') {
88 elevator.request(parseInt(args[0]));
89 } else if (command === 'select') {
90 elevator.request(parseInt(args[0]));
91 } else if (command === 'step') {
92 output.push(elevator.step());
93 }
94 }
95 return output;
96}
97
98function splitWords(s) {
99 return s === "" ? [] : s.split(" ");
100}
101
102function* main() {
103 const numFloors = parseInt(yield);
104 const instructionsLength = parseInt(yield);
105 const instructions = [];
106 for (let i = 0; i < instructionsLength; i++) {
107 instructions.push(splitWords(yield));
108 }
109 const res = elevatorSystem(numFloors, instructions);
110 for (const line of res) {
111 console.log(line);
112 }
113}
114
115class EOFError extends Error {}
116{
117 const gen = main();
118 const next = (line) => gen.next(line).done && process.exit();
119 let buf = "";
120 next();
121 process.stdin.setEncoding("utf8");
122 process.stdin.on("data", (data) => {
123 const lines = (buf + data).split("\n");
124 buf = lines.pop();
125 lines.forEach(next);
126 });
127 process.stdin.on("end", () => {
128 buf && next(buf);
129 gen.throw(new EOFError());
130 });
131}
1321class Direction {
2 static UP = 'up';
3 static DOWN = 'down';
4}
5
6class SchedulingStrategy {
7 nextStop(currentFloor: number, direction: string | null, targets: Set<number>): number | null {
8 if (targets.size === 0) return null;
9 const sorted = Array.from(targets).sort((a, b) => a - b);
10 if (direction === Direction.UP) {
11 const above = sorted.filter(f => f > currentFloor);
12 if (above.length > 0) return above[0];
13 const below = sorted.filter(f => f < currentFloor);
14 return below.length > 0 ? below[below.length - 1] : null;
15 }
16 if (direction === Direction.DOWN) {
17 const below = sorted.filter(f => f < currentFloor);
18 if (below.length > 0) return below[below.length - 1];
19 const above = sorted.filter(f => f > currentFloor);
20 return above.length > 0 ? above[0] : null;
21 }
22 // Idle: nearest floor; break ties by higher floor
23 let best: number | null = null;
24 let bestDist = Infinity;
25 for (const f of targets) {
26 const dist = Math.abs(f - currentFloor);
27 if (dist < bestDist || (dist === bestDist && f > (best ?? -Infinity))) {
28 bestDist = dist;
29 best = f;
30 }
31 }
32 return best;
33 }
34}
35
36class Elevator {
37 numFloors: number;
38 currentFloor: number;
39 direction: string | null;
40 targets: Set<number>;
41 doorsOpen: boolean;
42 strategy: SchedulingStrategy;
43
44 constructor(numFloors: number) {
45 this.numFloors = numFloors;
46 this.currentFloor = 1;
47 this.direction = null;
48 this.targets = new Set();
49 this.doorsOpen = false;
50 this.strategy = new SchedulingStrategy();
51 }
52
53 request(floor: number): void {
54 if (floor >= 1 && floor <= this.numFloors) {
55 this.targets.add(floor);
56 }
57 }
58
59 step(): string {
60 if (this.doorsOpen) this.doorsOpen = false;
61 if (this.targets.size === 0) {
62 this.direction = null;
63 return `Floor ${this.currentFloor} idle`;
64 }
65 const nextStop = this.strategy.nextStop(this.currentFloor, this.direction, this.targets);
66 if (nextStop === null) {
67 this.direction = null;
68 return `Floor ${this.currentFloor} idle`;
69 }
70 if (nextStop > this.currentFloor) {
71 this.direction = Direction.UP;
72 this.currentFloor++;
73 } else if (nextStop < this.currentFloor) {
74 this.direction = Direction.DOWN;
75 this.currentFloor--;
76 }
77 if (this.targets.has(this.currentFloor)) {
78 this.targets.delete(this.currentFloor);
79 this.doorsOpen = true;
80 return `Floor ${this.currentFloor} doors open`;
81 }
82 const dirStr = this.direction !== null ? this.direction : 'idle';
83 return `Floor ${this.currentFloor} moving ${dirStr}`;
84 }
85}
86
87function elevatorSystem(numFloors: number, instructions: string[][]): string[] {
88 const elevator = new Elevator(numFloors);
89 const output: string[] = [];
90 for (const instruction of instructions) {
91 const [command, ...args] = instruction;
92 if (command === 'request') {
93 elevator.request(parseInt(args[0]));
94 } else if (command === 'select') {
95 elevator.request(parseInt(args[0]));
96 } else if (command === 'step') {
97 output.push(elevator.step());
98 }
99 }
100 return output;
101}
102
103function splitWords(s: string): string[] {
104 return s === "" ? [] : s.split(" ");
105}
106
107function* main() {
108 const numFloors = parseInt(yield);
109 const instructionsLength = parseInt(yield);
110 const instructions = [];
111 for (let i = 0; i < instructionsLength; i++) {
112 instructions.push(splitWords(yield));
113 }
114 const res = elevatorSystem(numFloors, instructions);
115 for (const line of res) {
116 console.log(line);
117 }
118}
119
120class EOFError extends Error {}
121{
122 const gen = main();
123 const next = (line?: string) => gen.next(line ?? "").done && process.exit();
124 let buf = "";
125 next();
126 process.stdin.setEncoding("utf8");
127 process.stdin.on("data", (data: string) => {
128 const lines = (buf + data).split("\n");
129 buf = lines.pop() ?? "";
130 lines.forEach(next);
131 });
132 process.stdin.on("end", () => {
133 buf && next(buf);
134 gen.throw(new EOFError());
135 });
136}
1371#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <limits>
5#include <sstream>
6#include <string>
7#include <vector>
8
9#include <string>
10#include <vector>
11#include <set>
12#include <algorithm>
13#include <climits>
14#include <optional>
15
16enum class Direction { UP, DOWN, IDLE };
17
18class SchedulingStrategy {
19public:
20 std::optional<int> nextStop(int currentFloor, Direction direction, const std::set<int>& targets) {
21 if (targets.empty()) return std::nullopt;
22 if (direction == Direction::UP) {
23 auto it = targets.upper_bound(currentFloor);
24 if (it != targets.end()) return *it;
25 if (!targets.empty()) {
26 auto it2 = targets.lower_bound(currentFloor);
27 if (it2 != targets.begin()) { --it2; return *it2; }
28 }
29 return std::nullopt;
30 }
31 if (direction == Direction::DOWN) {
32 auto it = targets.lower_bound(currentFloor);
33 if (it != targets.begin()) { --it; return *it; }
34 if (!targets.empty()) {
35 auto it2 = targets.upper_bound(currentFloor);
36 if (it2 != targets.end()) return *it2;
37 }
38 return std::nullopt;
39 }
40 // Idle: nearest floor; break ties by higher floor
41 int best = -1;
42 int bestDist = INT_MAX;
43 for (int f : targets) {
44 int dist = std::abs(f - currentFloor);
45 if (dist < bestDist || (dist == bestDist && f > best)) {
46 bestDist = dist;
47 best = f;
48 }
49 }
50 return best == -1 ? std::nullopt : std::optional<int>(best);
51 }
52};
53
54class Elevator {
55public:
56 int numFloors;
57 int currentFloor;
58 Direction direction;
59 std::set<int> targets;
60 bool doorsOpen;
61 SchedulingStrategy strategy;
62
63 Elevator(int numFloors) : numFloors(numFloors), currentFloor(1),
64 direction(Direction::IDLE), doorsOpen(false) {}
65
66 void request(int floor) {
67 if (floor >= 1 && floor <= numFloors) {
68 targets.insert(floor);
69 }
70 }
71
72 std::string step() {
73 if (doorsOpen) doorsOpen = false;
74 if (targets.empty()) {
75 direction = Direction::IDLE;
76 return "Floor " + std::to_string(currentFloor) + " idle";
77 }
78 auto nextStop = strategy.nextStop(currentFloor, direction, targets);
79 if (!nextStop) {
80 direction = Direction::IDLE;
81 return "Floor " + std::to_string(currentFloor) + " idle";
82 }
83 int ns = *nextStop;
84 if (ns > currentFloor) {
85 direction = Direction::UP;
86 currentFloor++;
87 } else if (ns < currentFloor) {
88 direction = Direction::DOWN;
89 currentFloor--;
90 }
91 if (targets.count(currentFloor)) {
92 targets.erase(currentFloor);
93 doorsOpen = true;
94 return "Floor " + std::to_string(currentFloor) + " doors open";
95 }
96 std::string dirStr = (direction == Direction::UP) ? "up" :
97 (direction == Direction::DOWN) ? "down" : "idle";
98 return "Floor " + std::to_string(currentFloor) + " moving " + dirStr;
99 }
100};
101
102std::vector<std::string> elevator_system(int num_floors, std::vector<std::vector<std::string>> instructions) {
103 Elevator elevator(num_floors);
104 std::vector<std::string> output;
105 for (const auto& instruction : instructions) {
106 const std::string& command = instruction[0];
107 if (command == "request") {
108 int floor = std::stoi(instruction[1]);
109 elevator.request(floor);
110 } else if (command == "select") {
111 elevator.request(std::stoi(instruction[1]));
112 } else if (command == "step") {
113 output.push_back(elevator.step());
114 }
115 }
116 return output;
117}
118
119void ignore_line() {
120 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
121}
122
123template<typename T>
124std::vector<T> get_words() {
125 std::string line;
126 std::getline(std::cin, line);
127 std::istringstream ss{line};
128 ss >> std::boolalpha;
129 std::vector<T> v;
130 std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
131 return v;
132}
133
134int main() {
135 int num_floors;
136 std::cin >> num_floors;
137 ignore_line();
138 int instructions_length;
139 std::cin >> instructions_length;
140 ignore_line();
141 std::vector<std::vector<std::string>> instructions;
142 for (int i = 0; i < instructions_length; i++) {
143 instructions.emplace_back(get_words<std::string>());
144 }
145 std::vector<std::string> res = elevator_system(num_floors, instructions);
146 for (const std::string& line : res) {
147 std::cout << line << '\n';
148 }
149}
1501module Direction
2 UP = 'up'
3 DOWN = 'down'
4end
5
6class SchedulingStrategy
7 def next_stop(current_floor, direction, targets)
8 return nil if targets.empty?
9 sorted = targets.to_a.sort
10 if direction == Direction::UP
11 above = sorted.select { |f| f > current_floor }
12 return above.min if !above.empty?
13 below = sorted.select { |f| f < current_floor }
14 return below.empty? ? nil : below.max
15 end
16 if direction == Direction::DOWN
17 below = sorted.select { |f| f < current_floor }
18 return below.max if !below.empty?
19 above = sorted.select { |f| f > current_floor }
20 return above.empty? ? nil : above.min
21 end
22 # Idle: nearest floor; break ties by higher floor
23 best = nil
24 best_dist = Float::INFINITY
25 targets.each do |f|
26 dist = (f - current_floor).abs
27 if dist < best_dist || (dist == best_dist && f > best)
28 best_dist = dist
29 best = f
30 end
31 end
32 best
33 end
34end
35
36class Elevator
37 def initialize(num_floors)
38 @num_floors = num_floors
39 @current_floor = 1
40 @direction = nil
41 @targets = Set.new
42 @doors_open = false
43 @strategy = SchedulingStrategy.new
44 end
45
46 def request(floor)
47 @targets.add(floor) if floor >= 1 && floor <= @num_floors
48 end
49
50 def step
51 @doors_open = false if @doors_open
52 if @targets.empty?
53 @direction = nil
54 return "Floor #{@current_floor} idle"
55 end
56 next_stop = @strategy.next_stop(@current_floor, @direction, @targets)
57 if next_stop.nil?
58 @direction = nil
59 return "Floor #{@current_floor} idle"
60 end
61 if next_stop > @current_floor
62 @direction = Direction::UP
63 @current_floor += 1
64 elsif next_stop < @current_floor
65 @direction = Direction::DOWN
66 @current_floor -= 1
67 end
68 if @targets.include?(@current_floor)
69 @targets.delete(@current_floor)
70 @doors_open = true
71 return "Floor #{@current_floor} doors open"
72 end
73 dir_str = @direction || 'idle'
74 "Floor #{@current_floor} moving #{dir_str}"
75 end
76end
77
78def elevator_system(num_floors, instructions)
79 require 'set'
80 elevator = Elevator.new(num_floors)
81 output = []
82 instructions.each do |instruction|
83 command = instruction[0]
84 args = instruction[1..]
85 if command == 'request'
86 floor = args[0].to_i
87 elevator.request(floor)
88 elsif command == 'select'
89 elevator.request(args[0].to_i)
90 elsif command == 'step'
91 output << elevator.step
92 end
93 end
94 output
95end
96
97if __FILE__ == $0
98 num_floors = Integer(gets, 10)
99 instructions = Array.new(Integer(gets, 10)) { gets.split }
100 res = elevator_system(num_floors, instructions)
101 res.each { |line| puts(line) }
102end
103Run and Test
The command stream makes the design checkable against exact expected output. The sequence diagram below traces the first three commands of test 1 through every layer of the design.
Trace test 1 step by step to see how the pieces connect.
Setup: num_floors = 5. The elevator starts at floor 1, direction idle, targets empty.
Command ["request", "3", "up"]: elevator.request(3, Direction.UP) adds 3 to the target
set. targets = {3}.
Command ["step"]: _doors_open is False, so skip the reset. targets is non-empty.
strategy.next_stop(1, None, {3}) — direction is idle, picks the nearest floor, which is 3.
next_stop = 3 > current_floor 1 → set direction UP, move to floor 2. Floor 2 is not in
targets. Return "Floor 2 moving up". ✓
Command ["step"]: next_stop(2, UP, {3}) — above floor 2: [3]. Returns 3. Move to floor 3.
Floor 3 is in targets → discard 3, set _doors_open = True. Return "Floor 3 doors open". ✓
Command ["step"]: _doors_open is True → set False. targets = {}. Return "Floor 3 idle". ✓
Test 2 covers the SCAN reversal behavior: the elevator starts idle at floor 1 with requests at floors 2 and 4. The idle strategy picks the nearest floor (floor 2, distance 1) first. After serving floor 2 the direction is UP and floor 4 is still pending, so the car continues upward to serve floor 4 before going idle. Test 5 demonstrates mid-journey enqueue: a request for floor 3 arrives while the car is already moving up toward floor 5; SCAN serves floor 3 on the way up without reversing, then continues to floor 5.
Concurrency and Thread Safety
The simulation above is single-threaded — each tick arrives in order and there are no parallel callers. In a real deployment the structure becomes a classic producer/consumer problem.
Multiple threads represent passengers pressing buttons simultaneously: Thread A is Alice on
floor 3 pressing the UP button; Thread B is Bob on floor 7 pressing the UP button; both are
producers writing to the elevator's target set. The control loop is the single
consumer: it runs elevator.step() on each clock tick, reading and modifying the same
target set. Without synchronization, producers and the consumer interleave in ways that corrupt
the shared set.
The concrete failure is a lost request. If two button-press threads both call
elevator.request() at the same moment and request is not atomic, one write can overwrite
the other's partial update. The stop set ends up with only one of the two floors, and the
passenger whose request was dropped waits indefinitely.
The fix is a single lock that guards both request (producers) and step (consumer). Because
_update_direction inside step also reads the target set, the lock must cover the entire
body of both methods — holding it for a partial read leaves a window where the set can change
between the read and the write.
import threading
class Elevator:
def __init__(self, num_floors: int) -> None:
# ... other fields ...
self._lock = threading.Lock() # one lock guards both producers and consumer
def request(self, floor: int, direction: Optional[Direction] = None) -> None:
with self._lock: # producer acquires lock before writing
if 1 <= floor <= self.num_floors:
self._targets.add(floor)
def step(self) -> str:
with self._lock: # consumer acquires the same lock before reading
# ... full step logic unchanged ...
Holding the lock for the entire step call (one floor movement per tick) is acceptable: each
tick is brief, and the lock is released before the next tick begins, so producers are never
blocked for more than one tick at a time. An alternative to a per-elevator mutex is a
thread-safe blocking queue such as Python's queue.Queue or Java's
LinkedBlockingDeque. Producers append floors to the tail without reading the current contents;
the control loop drains the queue at the head. The trade-off is that the sorted SCAN order is
harder to maintain lock-free — the simplest production approach is a threading.Lock
protecting a sorted set, which gives both thread safety and ordered access in one structure.
For a horizontally scaled deployment, the in-process set must move to a shared data store. A Redis
sorted set holds the pending stops — ZADD elevator:stops <floor> <floor> — and its
single-threaded command execution removes the lost-update race without any application-level
locking. What does not carry over is the stop selection: ZPOPMIN always pops the globally
lowest floor, ignoring the car's current floor and direction, so it would break the SCAN/LOOK
order the design depends on. The control loop must still pick the next stop with a direction-aware
query and remove exactly that floor, ideally inside one Lua script so the read-and-remove stays
atomic: travelling up, ZRANGEBYSCORE elevator:stops <floor> +inf LIMIT 0 1 takes the nearest stop
above; travelling down, ZREVRANGEBYSCORE elevator:stops <floor> -inf LIMIT 0 1 takes the nearest
below. (An ascending ZRANGEBYSCORE alone would hand back the lowest floor on the way down and
break the order.) Redis is the
shared storage here, not a replacement for the scheduling policy.
Scaling to multiple cars
The single-car design already leaves the seam for a bank of cars: ElevatorSystem owns the car and
routes every command to it. With several cars, routing stops being a pass-through and becomes the
central decision of the multi-elevator problem — when a hall call comes in, which car should
answer it? Each car still runs SCAN/LOOK on its own pending stops; this is a separate choice
layered on top of that.
A hall call carries a floor and a direction. Before reading on, decide what a dispatcher should look at to pick the car that will serve that call soonest.
Decision checkpoint
A hall call arrives at floor 7 going up, with three cars in motion. Should the dispatcher choose the car by closest current floor, by the closest car already heading the right way, or by which car's existing route will actually sweep past floor 7 going up?
Routing this way changes no existing class. ElevatorSystem holds a list of Elevator instances
and a DispatchStrategy; on a hall call it asks the strategy to score the cars and forwards the
call to the winner, which folds the floor into its own target set and schedules it with SCAN/LOOK
exactly as before. The dispatcher reads only the observable state each car already exposes
(current_floor, direction, and its pending stops) — Elevator and SchedulingStrategy are
untouched. The decision itself is the request-aware rule from the checkpoint — score each car by
how cheaply its current route can absorb the call. The DispatchStrategy interface is what lets a
team ship a simpler nearest-car stub first and grow into the request-aware scorer later without
touching ElevatorSystem: the same open/closed payoff the single-car design bought with
SchedulingStrategy.
Extensions
Weight limits add a sensor integration: the elevator publishes a load_kg reading; before
accepting a new cabin button press the system checks whether adding one more passenger would exceed
the rated capacity. This adds a field to Elevator and a guard in request, but changes no
scheduling logic.
Express zones — where certain cars skip floors 2 through 10 and serve only the lobby and floors 11
and above — are handled entirely inside SchedulingStrategy. The strategy receives a floor range at
construction time and filters the target set to only floors within the range before computing the
next stop. Callers that enqueue an out-of-range floor are silently ignored, or the dispatcher routes
the request to a different car whose zone includes that floor.
Each extension lands by adding a class or adjusting one method, never by rewriting Elevator.
That extensibility follows from splitting responsibilities correctly at the start: Elevator
owns movement and state; SchedulingStrategy owns the ordering decision; ElevatorSystem
owns routing across cars.
Quiz
Test your understanding of the key design decisions in this elevator system.
Elevator System Design Quiz
Why is scheduling logic placed in its own SchedulingStrategy class rather than directly inside Elevator?
When moving UP with targets {3, 7} at floor 5, what does SCAN/LOOK choose next, and when does it reverse?
Why is idle represented as direction = None rather than adding an IDLE value to the Direction enum?
Why are pending stops stored in a set rather than a sorted list?
What concurrency bug arises when multiple button-press threads call elevator.request() simultaneously, and how does the design fix it?