Design an Elevator (FCFS)

Medium·Tagsllddesignelevatorstate-machinefcfs

Problem Statement

Design a single-elevator system that serves a building with floors `0..totalFloors-1`. The elevator processes requests in FIFO (first-come-first-served) order — each request is honoured in the order it was submitted, one stop at a time. (Real elevators use SCAN/LOOK; FCFS is the simplest correct schedule and the natural baseline for an interview discussion about better strategies.) API contract ```java enum Direction { UP, DOWN, IDLE } class Elevator { public Elevator(int totalFloors); // floors 0..totalFloors-1, starts at 0, IDLE /** Queue a stop at `floor`. Floors are 0-indexed. * - Out-of-range floors throw IllegalArgumentException. * - A request for a floor already in the queue is ignored (no duplicates). * - A request for the elevator's current floor when the queue is empty is also ignored (the elevator is already there). / public void requestStop(int floor); /** Advance the elevator by one floor toward the head of the queue. * - If the queue is empty, do nothing (Direction stays IDLE). * - Otherwise: move one floor toward queue.peek() (UP if target > current, DOWN if <). * - If the move arrives at the target, remove it from the queue. If the queue is then empty, set Direction to IDLE; otherwise the next step picks the new head. / public void step(); public int getCurrentFloor(); public Direction getDirection(); public boolean hasPendingStops(); } ``` The validator runs three checks: 1. single_request_moves_to_floor — fresh elevator at floor 0, `requestStop(3)`, then 3 calls to `step()`. After the loop: `currentFloor == 3`, `direction == IDLE`, `hasPendingStops() == false`. Direction is `UP` during the climb. 2. fcfs_processes_in_order — fresh elevator at floor 0, `requestStop(3)` then `requestStop(1)`. The elevator reaches floor 3 first (3 steps, direction UP), then turns around and reaches floor 1 (2 more steps, direction DOWN). After 5 total steps: floor 1, IDLE. 3. edge_cases — out-of-range floor throws `IllegalArgumentException`; duplicate request is ignored (`hasPendingStops` stays false after a no-op duplicate); request for the current floor when queue is empty is ignored (no movement on next step). The stub `Elevator` throws `UnsupportedOperationException` from every method, so it fails every check until you implement it. Starter code and validators are available in Java, Python, and C++.

Examples

Example 1

Input

var e = new Elevator(10); e.requestStop(3); e.step(); e.step(); e.step(); e.getCurrentFloor()

Output

"3"

Why

Elevator starts at floor 0. Three steps toward floor 3: 0→1→2→3. After arrival, IDLE.

Example 2

Input

e.requestStop(3); e.requestStop(1); for(int i=0;i<5;i++) e.step(); e.getCurrentFloor()

Output

"1"

Why

FCFS: serves floor 3 first (3 steps), then floor 1 (2 more steps). 5 total steps land at floor 1.

Example 3

Input

e.requestStop(99) (where totalFloors=10)

Output

"throws IllegalArgumentException"

Why

Floor 99 is out of range. Request is rejected up front.

Constraints

•Elevator constructor takes a single int (totalFloors). Floors are 0..totalFloors-1.
•requestStop throws IllegalArgumentException for floors outside [0, totalFloors-1].
•requestStop deduplicates: a floor already in the queue is ignored.
•requestStop for the current floor when the queue is empty is also ignored (already there).
•step never moves more than one floor.
•step on an empty queue is a no-op; Direction stays IDLE.
•Direction is UP when moving toward a higher floor, DOWN when moving toward a lower floor, IDLE when no pending stops.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

Use a `Deque<Integer>` (or LinkedList) for FIFO order: addLast on requestStop, peekFirst/pollFirst inside step.

Hint 2

step(): if queue is empty, set direction = IDLE and return. Otherwise compare queue.peek() to currentFloor: > → UP and currentFloor++; < → DOWN and currentFloor--. After moving, if currentFloor == queue.peek() → poll it. If queue is now empty → direction = IDLE.

Hint 3

requestStop validation: check 0 <= floor < totalFloors first, then check the dedup (queue.contains(floor)), then check the current-floor-on-idle case. Order matters — the throw must come before the no-ops.

Hint 4

Direction is a derived state. You can store it as a field (set in step()) or compute it inside getDirection() from the queue head; either is fine. Storing makes the contract more obvious.