Case study: LLD elevator and vending machine

The lift and the vending machine are two classic machine-coding problems (lesson 105). The lift is one of the ten problems in Tradeoff's practice round. In both, a thing is always in one state, and the same event does a different job in each state.

The interviewer looks at three things. Did you find the states and the legal moves before you wrote code? Is the behaviour of each state in one place? When the new requirement comes, is it an addition, or does it need edits in many methods? A new requirement can be a fire alarm for the lift, or a stopped machine for the vending machine.

A weak answer keeps several true-or-false flags and an if chain in every method. The first version works. Then the new requirement needs a new check in every method, and one forgotten check is a bug. A strong answer names the states, writes down the legal moves, and adds the new requirement as one new piece.

At SDE-1 level you should reach working code with the states named. At SDE-2 level you should add the new requirement with a small change. At SDE-3 level you should also say when a table is enough and when one class for each state is worth its cost.

Think of the operator of an old lift. He has a short rule book. Each rule starts with the state. One rule says: "If the doors are open, close them." Another says: "If the doors are closed and someone waits on this floor, open them." He does one thing at a time, and he looks only at the state and the list of waiting people. A new rule, such as "in a fire, go to the ground floor", is a new page. It is not an edit of every old page.

In lesson 66, a state machine is a list of states and the legal moves between them. Lesson 107 showed one way to write it in code: one class for each state. This lesson shows two ways, one for each problem.

1. A table of legal moves. The table lists each pair of a state and an event that is legal, and the state it leads to. Use it when the states differ only in which events are legal. The vending machine uses it.
2. One class for each mode. Use it when the same event does different work in each mode. The lift uses it. A mode is a state of the whole controller, such as normal or alarm.

Both code listings are Python, as in lesson 106. In a round, calls arrive one after another. If the interviewer asks about threads, the answer is one lock that every public method takes (lesson 110).

Problem 1: the lift

This is a shortened form of Tradeoff's practice problem. You would ask questions until you have a list like this.

1. One lift. Floors are numbered from 0 (the ground) to a top floor.
2. A person inside the lift presses a floor number. A person waiting on a floor makes a call: UP or DOWN.
3. Time moves in ticks. In one tick the lift does one thing: close the doors, open the doors, or move one floor. Moving into a floor and opening the doors are two ticks.
4. The lift has a direction: UP, DOWN or IDLE. It keeps its direction while something waits ahead. Then it turns around.
5. The doors open on a floor when there is a press for it, or a call for it in the lift's direction. They also open for any call on that floor when nothing waits ahead, or when the lift is IDLE. A press or call is served when the doors open for it.
6. When the doors close and nothing waits, the direction becomes IDLE. An idle lift goes to the nearest waiting floor, and goes up on a tie.
7. A request for the floor where the doors are open now is served at once if point 5 says so. The doors do not open again.
8. A bad floor, a direction other than UP or DOWN, UP on the top floor, or DOWN on floor 0 is an error. It changes nothing.
9. The lift answers three questions: its state as text, the floors that wait, and the floors where the doors opened.

The rule in point 4 is known as the LOOK rule: keep going while there is work ahead, then turn (see Sources).

Step 1: find the states and the moves

The car has two door states (OPEN or CLOSED) and three directions (UP, DOWN or IDLE), so 2 x 3 = 6 combinations. We do not need a rule for each one. Each tick is one move, and the move depends only on the doors and on the waiting list:

Step 2: choose the classes

Lesson 109 showed how to find classes. Keep a noun as a class when it has its own data or rules.

The main class holds one mode object and passes each call to it. This is the State pattern of lesson 107. The lift starts in NormalMode.

Step 3: the code

First the direction and the car. Dir.UP has the value 1 and Dir.DOWN has the value -1, so floor + direction.value is the next floor.

from enum import Enum

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

    def opposite(self):
        return Dir(-self.value)

class Car:
    def __init__(self, floor):
        self.floor = floor
        self.direction = Dir.IDLE
        self.doors_open = False
        self.served = []      # floors where the doors opened

    def state(self):
        doors = "OPEN" if self.doors_open else "CLOSED"
        return f"floor={self.floor} dir={self.direction.name} doors={doors}"

Now the board. A floor that waits is pending. ahead is true when a waiting floor lies beyond this floor in the given direction. to_serve is point 5 of the statement. It returns whether a press is served here, and the directions of the calls that are served here.

class Board:
    def __init__(self):
        self.presses = set()    # floors pressed inside the car
        self.calls = set()      # (floor, Dir) from people waiting

    def pending_floors(self):
        return sorted(self.presses | {f for f, _ in self.calls})

    def ahead(self, floor, direction):
        step = direction.value
        return any((f - floor) * step > 0 for f in self.pending_floors())

    # more methods of Board
    def to_serve(self, floor, direction):
        here = {d for f, d in self.calls if f == floor}
        if direction != Dir.IDLE and self.ahead(floor, direction):
            here &= {direction}
        return floor in self.presses, here

    def clear(self, floor, directions):
        self.presses.discard(floor)
        for d in directions:
            self.calls.discard((floor, d))

The rule for the next direction is its own function (point 4 and point 6). An idle lift picks the nearest waiting floor. The key (distance, f < floor) puts a floor above the lift first on a tie, because False sorts before True.

def choose_direction(floor, direction, board):
    if direction == Dir.IDLE:
        nearest = min(board.pending_floors(),
                      key=lambda f: (abs(f - floor), f < floor))
        return Dir.UP if nearest > floor else Dir.DOWN
    if board.ahead(floor, direction):
        return direction
    return direction.opposite()

Now the mode. step is the table of Step 1 in code.

class NormalMode:
    def step(self, lift):
        car, board = lift.car, lift.board
        if car.doors_open:
            car.doors_open = False
            if not board.pending_floors():
                car.direction = Dir.IDLE
            return
        pressed, calls = board.to_serve(car.floor, car.direction)
        if pressed or calls:
            board.clear(car.floor, calls)
            car.doors_open = True
            car.served.append(car.floor)
        elif board.pending_floors():
            car.direction = choose_direction(car.floor, car.direction, board)
            car.floor += car.direction.value

The same class goes on with press, request and serve_now. serve_now is point 7: when the doors are open on the floor of a new request, serve it at once.

    # more methods of NormalMode
    def press(self, lift, floor):
        lift.check_floor(floor)
        lift.board.presses.add(floor)
        self.serve_now(lift, floor)

    def request(self, lift, floor, direction):
        lift.check_call(floor, direction)
        lift.board.calls.add((floor, Dir[direction]))
        self.serve_now(lift, floor)

    def serve_now(self, lift, floor):
        car = lift.car
        if car.doors_open and car.floor == floor:
            _, calls = lift.board.to_serve(floor, car.direction)
            lift.board.clear(floor, calls)

Last, the main class. The checks come first, so a bad call changes nothing (point 8).

class Elevator:
    def __init__(self, top_floor, start_floor):
        self.top = top_floor
        self.car = Car(start_floor)
        self.board = Board()
        self.mode = NormalMode()

    def check_floor(self, floor):
        if not 0 <= floor <= self.top:
            raise ValueError("no such floor")

    def check_call(self, floor, direction):
        self.check_floor(floor)
        if direction not in ("UP", "DOWN"):
            raise ValueError("direction must be UP or DOWN")
        if (floor, direction) in ((self.top, "UP"), (0, "DOWN")):
            raise ValueError("the lift cannot go that way")

    # more methods of Elevator
    def press(self, floor):
        self.mode.press(self, floor)

    def request(self, floor, direction):
        self.mode.request(self, floor, direction)

    def step(self):
        self.mode.step(self)
        return self.car.state()

    def state(self):
        return self.car.state()

    def pending_stops(self):
        return self.board.pending_floors()

    def served_floors(self):
        return list(self.car.served)

Problem 2: the vending machine

This statement is made up for teaching. Assumption: change is one amount of rupees. Which coins make the change is out of scope.

1. Each slot has a code such as "A1", an item name, a price in whole rupees and a stock.
2. The machine accepts notes and coins of Rs 10, 20, 50 and 100. Any other value is an error.
3. The customer inserts money, one or more times, and then selects a slot. If the money covers the price and the slot has stock, the item drops. The change is the money minus the price.
4. Before selecting, the customer may cancel and get all the money back.
5. While the item drops, the machine accepts nothing. When the customer takes the item, the machine is ready again.
6. An action that is not allowed, or is refused, changes nothing.

The states are IDLE (no money), HAS_MONEY and DISPENSING. The events are insert, select, cancel and collect. Here the states differ only in which events are legal. For example, insert does the same work in IDLE and in HAS_MONEY. So a table is enough.

LEGAL = {
    ("IDLE", "insert"): "HAS_MONEY",
    ("HAS_MONEY", "insert"): "HAS_MONEY",
    ("HAS_MONEY", "select"): "DISPENSING",
    ("HAS_MONEY", "cancel"): "IDLE",
    ("DISPENSING", "collect"): "IDLE",
}
NOTES = (10, 20, 50, 100)

class Slot:
    def __init__(self, name, price, stock):
        self.name, self.price, self.stock = name, price, stock

The table says that an event is allowed in a state. The method still checks the rules of the problem, such as price and stock. The state changes last, so a refused call changes nothing.

class VendingMachine:
    def __init__(self, slots):
        self.slots = slots        # code -> Slot
        self.state = "IDLE"
        self.credit = 0           # money inserted, not yet used
        self.ready = None         # (name, change) while DISPENSING

    def next_state(self, event):
        nxt = LEGAL.get((self.state, event))
        if nxt is None:
            raise ValueError(f"cannot {event} when {self.state}")
        return nxt

    def insert(self, amount):
        nxt = self.next_state("insert")
        if amount not in NOTES:
            raise ValueError("this note or coin is not accepted")
        self.credit += amount
        self.state = nxt

    # more methods of VendingMachine
    def select(self, code):
        nxt = self.next_state("select")
        slot = self.slots.get(code)
        if slot is None:
            raise ValueError("no such slot")
        if slot.stock == 0:
            raise ValueError("sold out")
        if self.credit < slot.price:
            raise ValueError(f"insert Rs {slot.price - self.credit} more")
        slot.stock -= 1
        self.ready = (slot.name, self.credit - slot.price)
        self.credit = 0
        self.state = nxt

cancel and collect follow the same shape.

    # more methods of VendingMachine
    def cancel(self):
        nxt = self.next_state("cancel")
        refund, self.credit = self.credit, 0
        self.state = nxt
        return refund

    def collect(self):
        nxt = self.next_state("collect")
        item, self.ready = self.ready, None
        self.state = nxt
        return item

Two facts always hold. Money waits in credit only in HAS_MONEY, and ready is set only in DISPENSING. A test can check both after every call.

Assumption: the top floor is 8. All numbers are made up to teach with.

1. The lift (the predict box). The lift is idle at floor 3. We call press(7) and request(5, "DOWN").

The answer to the predict box: no, the lift does not stop at floor 5 on the way up. It serves the call on the way down. Both stops need 4 moves + 1 open + 1 close + 2 moves + 1 open = 9 ticks. The doors open at floors 7 and 5, so served_floors() returns [7, 5].

2. The new requirement: a fire alarm. The interviewer says: "When the alarm goes on, the lift forgets every request. It closes its doors, goes straight down to floor 0 without stopping, and opens the doors there. It refuses new requests until an engineer clears the alarm. Then the lift is normal again." The tick rules for the alarm differ from the normal rules, so we make a new mode.

class AlarmMode:
    def step(self, lift):
        car = lift.car
        if car.doors_open:
            if car.floor > 0:
                car.doors_open = False
        elif car.floor > 0:
            car.floor -= 1
            if car.floor == 0:
                car.direction = Dir.IDLE
        else:
            car.doors_open = True
            car.served.append(0)

    def press(self, lift, floor):
        raise ValueError("the alarm is on")

    def request(self, lift, floor, direction):
        raise ValueError("the alarm is on")

Then Elevator gets three new methods. Switching the mode is one line.

    # three new methods of Elevator
    def trigger_alarm(self):
        if self.alarm_active():
            return
        self.board = Board()
        self.car.direction = Dir.DOWN if self.car.floor > 0 else Dir.IDLE
        self.mode = AlarmMode()

    def clear_alarm(self):
        if self.alarm_active():
            self.mode = NormalMode()
            self.car.direction = Dir.IDLE

    def alarm_active(self):
        return isinstance(self.mode, AlarmMode)

No old line changes in Dir, Car, Board, choose_direction or NormalMode. Take the lift of part 1 after tick 3, at floor 6 going UP, and switch the alarm on. The waiting list is empty, and the direction is DOWN. The lift needs 6 ticks to move from floor 6 to floor 0, and the direction becomes IDLE on arrival. The next tick opens the doors, and served_floors() ends with 0. So the alarm needs 6 + 1 = 7 ticks. A call to press(2) now raises an error.

3. The vending machine. Assumption: A1 is Chips at Rs 20 with a stock of 5. A2 is Cola at Rs 40 with a stock of 2.

1. IDLE. insert(50): the state is HAS_MONEY and the credit is 50.
2. select("A2"): the money covers the price. The stock of Cola becomes 1. The change is 50 - 40 = Rs 10. The state is DISPENSING and the credit is 0.
3. insert(10) now raises cannot insert when DISPENSING. collect() returns ("Cola", 10) and the state is IDLE.
4. insert(10), then select("A2"): the error is insert Rs 30 more, because 40 - 10 = 30. The state is still HAS_MONEY and the credit is still 10.
5. insert(20), then select("A2"): the credit is 30, so the error is insert Rs 10 more. Then cancel() returns Rs 30 and the state is IDLE.

The table has 3 states and 4 events, so 3 x 4 = 12 pairs. Five are legal and 12 - 5 = 7 are illegal. Every illegal pair raises the same error without code of its own.

4. The new requirement: a stopped machine. The interviewer says: "An engineer can stop the machine. Any money inside goes back to the customer. A stopped machine accepts nothing. The engineer can start it again. While an item is dropping, stopping is not allowed." Add three rows to the table, and two methods:

LEGAL[("IDLE", "stop")] = "STOPPED"
LEGAL[("HAS_MONEY", "stop")] = "STOPPED"
LEGAL[("STOPPED", "start")] = "IDLE"

    # two new methods of VendingMachine
    def stop(self):
        nxt = self.next_state("stop")
        refund, self.credit = self.credit, 0
        self.state = nxt
        return refund

    def start(self):
        self.state = self.next_state("start")

With Rs 30 inserted, stop() returns Rs 30. Then insert(10) raises cannot insert when STOPPED, with no new code, because the pair is not in the table. stop() while DISPENSING raises cannot stop when DISPENSING. The table now has 4 states and 6 events, so 4 x 6 = 24 pairs. Eight are legal, and 24 - 8 = 16 are illegal. No old method changed.

• A mode class solves adding the alarm without editing the normal rules. It costs one class and one more jump when you read. I made the mode object before the alarm was asked, which cost one line and one class. I would use a plain step method if no new mode was expected.
• A table of legal moves solves the vending machine with little code. It costs a method that must still check the rules the table cannot hold, such as price. I would change to one class for each state when the same event needs different work in each state, as in the lift.
• A tick simulation solves testing, because the same requests always give the same movement and no clock is needed. It costs realism, because a real lift runs in time. A real system would call step from a timer.
• Keeping Board and Car apart solves a mode that swaps its rules and keeps the same car. It costs two more classes. I would merge them if the lift never gets a second mode.

"A state machine needs one class for each state." For the vending machine, a table of five rows does the job. One class for each state is worth its cost when the same event does different work in each mode. The step method does this in the alarm mode and in the normal mode.

"The lift serves requests in the order they come." Take a lift at floor 0 with presses for 8, then 2, then 5. In that order it moves 8 + 6 + 3 = 17 floors. With the direction rule it stops at 2, 5 and 8 on one trip and moves 8 floors.

"A new mode is one more flag, if alarm: in each method." It works once. Then step, press, request and the queries all need the flag. Every new mode adds another flag to each method. A mode class keeps the alarm rules in one place.

1. In the lift, what does one tick do when the doors are open? What does it do when the doors are closed, nothing is served here, and something waits? What does it do when the doors are closed and nothing waits?
2. The top floor is 9. The lift is idle at floor 4. We call press(8) and request(3, "UP"). After how many ticks do the doors open at floor 8, and what does served_floors() return then?
3. A teammate writes select so that it sets self.state = "DISPENSING" first and then checks the price. A customer inserts Rs 10 and selects a Rs 40 cola. What happens, and what is the fix?