AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content

05 Elevator system / Lesson 1 of 1

Elevator system: one car, then a dispatcher

14 min · +10 XP · 2 exercises · 4 questions

Read the text14 min
Exercises0/2
Quiz4 q

Quick answer

How do you code an elevator system in a machine-coding round?

Give each Elevator its floor, a direction (up, down or idle) and a sorted set of stops, and let a LOOK rule move it: keep the direction while a stop lies ahead, turn when none does, go idle when none is left. A Dispatcher sends each hall call to the nearest car that is idle or already heading towards it.

An elevator is the machine-coding problem where an object model has to carry a scheduling rule. The exercises grow it the way a round does: one car first, then two cars and a dispatcher. The elevator system note has the full design; this lesson is the part you type.

The classes

  • Elevator: floor, dir and stops, a TreeSet<Integer>. Sorted, so the next stop above is stops.higher(floor) and below is stops.lower(floor); a repeated call vanishes on its own.
  • Direction: an enum UP, DOWN, IDLE. It is the car's state: it decides which stops count as ahead.
  • Dispatcher: owns the cars and answers hall calls. A car call, pressed inside, skips it and goes straight to its car.
  • Scheduler: the rule for the next stop, behind an interface so LOOK, SCAN or first come first served can be swapped (Strategy).

One tick at a time

A simulation moves time in ticks. On each STEP a car does exactly one thing:

  1. No stops: it is idle and says so.
  2. A stop at the floor it is on: the doors open, nothing moves.
  3. Otherwise it moves one floor in its direction, and stops if that floor was asked for.

Then LOOK settles the direction: keep it while a stop lies ahead, turn when none does, go idle when none is left.

LOOK, one STEP at a time: up for 4 and 5, then down for 3 and 0
6 2 · CALL 5 · CALL 0 · STEP · CALL 4 · STEP · CALL 3 · STEP …

The car is idle at floor 2. CALL 5 gives it a direction, up, at once; CALL 0 is a second stop, below it.

0:01 / 0:23Step 1 of 9
Transcript · 9 steps

The traps

  • Nearest stop first. Short to write, and it starves: a busy cluster near the car keeps winning while a far floor waits for ever. LOOK never turns while a stop lies ahead, so a call behind the car waits one sweep at most. In the figure, the call for 3 came in behind the car; it waited for the turn and was served on the way down.
  • The idle car. Give it a direction the moment it takes its first call, or the dispatcher still sees it as free and keeps piling calls on it.
  • Moving in the wrong place. The dispatcher chooses, the car moves. A dispatcher that edits floors is the mixed responsibility interviewers look for.

Dispatching

The dispatcher's rule, in order:

  1. Among cars that are idle or already heading towards the floor, take the nearest.
  2. If none is, take the nearest car anyway; it serves the call after it turns.
  3. Ties go to the lower-numbered car, so the output is deterministic.

A car call never goes through these steps: it belongs to the car it was pressed in, even when the floor is behind it.

Common questions

Why store an elevator's stops in a TreeSet?

A TreeSet keeps the stops sorted and drops duplicates, so "is there a stop above me?" is one higher(floor) call and "below me?" one lower(floor), each O(log n). A list needs a scan, and a queue serves calls in arrival order and zigzags.

When does a LOOK elevator change direction?

Only when no stop lies ahead in its current direction. A call behind the car waits until the sweep it is on ends, which stops the car zigzagging and still reaches every floor within two sweeps.

What is the difference between a hall call and a car call in code?

A hall call goes to the Dispatcher, which chooses an elevator; a car call is pressed inside one elevator and goes straight into that elevator's stops. In code that is two entry points, such as dispatcher.call(floor) and elevator.press(floor).

Why does an idle elevator need a direction as soon as it is assigned a call?

The dispatcher reads direction to decide who answers the next call. A car left idle after taking a call still looks free, so the next call may be piled onto it, or sent the wrong way, before it has even moved.

Mark as readSign in to keep your place.
AI InterviewGet started

Elevator System Design in Java: LOOK and a Dispatcher

Code an elevator system in Java for a machine-coding round: a TreeSet of stops, direction as state, LOOK scheduling and a dispatcher for two cars.

How do you code an elevator system in a machine-coding round?

Give each Elevator its floor, a direction (up, down or idle) and a sorted set of stops, and let a LOOK rule move it: keep the direction while a stop lies ahead, turn when none does, go idle when none is left. A Dispatcher sends each hall call to the nearest car that is idle or already heading towards it.

Lesson

An elevator is the machine-coding problem where an object model has to carry a scheduling rule. The exercises grow it the way a round does: one car first, then two cars and a dispatcher. The elevator system note has the full design; this lesson is the part you type.

The classes

  • Elevator: floor, dir and stops, a TreeSet<Integer>. Sorted, so the next stop above is stops.higher(floor) and below is stops.lower(floor); a repeated call vanishes on its own.
  • Direction: an enum UP, DOWN, IDLE. It is the car's state: it decides which stops count as ahead.
  • Dispatcher: owns the cars and answers hall calls. A car call, pressed inside, skips it and goes straight to its car.
  • Scheduler: the rule for the next stop, behind an interface so LOOK, SCAN or first come first served can be swapped (Strategy).

One tick at a time

A simulation moves time in ticks. On each STEP a car does exactly one thing:

  1. No stops: it is idle and says so.
  2. A stop at the floor it is on: the doors open, nothing moves.
  3. Otherwise it moves one floor in its direction, and stops if that floor was asked for.

Then LOOK settles the direction: keep it while a stop lies ahead, turn when none does, go idle when none is left.

0123456doorsstateat 0 IDLE · stops noneprintedUP to 3UP to 4: stopUP to 5: stopDOWN to 4DOWN to 3: stopDOWN to 2DOWN to 1DOWN to 0: stop
LOOK, one STEP at a time: up for 4 and 5, then down for 3 and 0. Example: 6 2 · CALL 5 · CALL 0 · STEP · CALL 4 · STEP · CALL 3 · STEP …
  1. The car is idle at floor 2. CALL 5 gives it a direction, up, at once; CALL 0 is a second stop, below it.
  2. STEP: a stop lies ahead at 5, so the car moves up one floor. Meanwhile CALL 4 comes in, ahead of the car, and joins this sweep.
  3. STEP: the car moves to 4, which is a stop, so it is served in the same tick. CALL 3 arrives now, behind the car: it must wait.
  4. STEP: up to 5, the last stop above. Nothing lies ahead any more, so LOOK turns the car down as it stops, instead of riding on to the top.
  5. STEP: down to 4. It was served on the way up, so the car passes it; the stops ahead are 3 and 0.
  6. STEP: down to 3, the call that came in behind the car. It waited exactly one sweep.
  7. STEP: down to 2, no one asked for it, so the car keeps moving.
  8. STEP: down to 1, the last floor before the remaining stop.
  9. STEP: down to 0, the last stop. With no stops left the car goes idle; every call was served within two sweeps.

The traps

  • Nearest stop first. Short to write, and it starves: a busy cluster near the car keeps winning while a far floor waits for ever. LOOK never turns while a stop lies ahead, so a call behind the car waits one sweep at most. In the figure, the call for 3 came in behind the car; it waited for the turn and was served on the way down.
  • The idle car. Give it a direction the moment it takes its first call, or the dispatcher still sees it as free and keeps piling calls on it.
  • Moving in the wrong place. The dispatcher chooses, the car moves. A dispatcher that edits floors is the mixed responsibility interviewers look for.

Dispatching

The dispatcher's rule, in order:

  1. Among cars that are idle or already heading towards the floor, take the nearest.
  2. If none is, take the nearest car anyway; it serves the call after it turns.
  3. Ties go to the lower-numbered car, so the output is deterministic.

A car call never goes through these steps: it belongs to the car it was pressed in, even when the floor is behind it.

Common questions

Why store an elevator's stops in a TreeSet?

A TreeSet keeps the stops sorted and drops duplicates, so "is there a stop above me?" is one higher(floor) call and "below me?" one lower(floor), each O(log n). A list needs a scan, and a queue serves calls in arrival order and zigzags.

When does a LOOK elevator change direction?

Only when no stop lies ahead in its current direction. A call behind the car waits until the sweep it is on ends, which stops the car zigzagging and still reaches every floor within two sweeps.

What is the difference between a hall call and a car call in code?

A hall call goes to the Dispatcher, which chooses an elevator; a car call is pressed inside one elevator and goes straight into that elevator's stops. In code that is two entry points, such as dispatcher.call(floor) and elevator.press(floor).

Why does an idle elevator need a direction as soon as it is assigned a call?

The dispatcher reads direction to decide who answers the next call. A car left idle after taking a call still looks free, so the next call may be piled onto it, or sent the wrong way, before it has even moved.

Exercises

One car under LOOK

Simulate one elevator, one floor per tick, under LOOK.

Input. The first line is top start: the floors are 0 to top and the car starts idle at start. Then one command per line:

  • CALL f: add a stop at floor f. Outside 0..top print invalid floor f. A stop that is already there changes nothing. An idle car takes the direction of its first call at once (up if f is above it, down if below). Prints nothing otherwise.
  • STEP: one tick. With no stops print idle at F. If the floor the car is on is a stop, serve it without moving: stop at F. Otherwise move one floor in the car's direction and print UP to F or DOWN to F, adding : stop when that floor is a stop (it is served and removed). After the tick, LOOK settles the direction: no stops left means IDLE; no stop ahead in the current direction means the car turns.
  • STATUS: at F DIR stops a b c with the stops in ascending order, or stops none.

Example

6 2
CALL 5
CALL 0
STEP
STEP
STATUS

prints

UP to 3
UP to 4
at 4 UP stops 0 5

Two cars and a dispatcher

Two elevators, E1 and E2, each moving exactly as in the first exercise, and a dispatcher that answers hall calls.

Input. The first line is top a b: floors 0 to top, E1 idle at a, E2 idle at b. Then one command per line:

  • CALL f: a hall call. A car heads towards f when it is idle, going UP with f at or above its floor, or going DOWN with f at or below it. Choose the nearest car that heads towards f; if none does, the nearest car. A tie goes to E1. Add the stop to that car (an idle car takes the call's direction, as before) and print call f -> E1. A floor outside 0..top prints invalid floor f.
  • PRESS E f: a car call, added straight to that car's stops. Prints nothing, or unknown elevator E, or invalid floor f (the car is checked first).
  • STEP: one tick for E1, then E2; each prints its line from the first exercise prefixed with its id, such as E1 UP to 3 or E2 idle at 9.
  • STATUS: both cars' status lines, prefixed the same way: E1 at 3 UP stops 6.

Example

10 0 8
CALL 3
CALL 9
STEP

prints

call 3 -> E1
call 9 -> E2
E1 UP to 1
E2 UP to 9: stop

E1 got 3 (both idle, E1 nearer). For 9, E1 heads towards it but E2 is idle and nearer.

In this module: Elevator system

← Checkpoint — Vending machine · Checkpoint: Elevator system →