Case study: LLD parking lot

The parking lot is one of the ten problems in Tradeoff's machine-coding practice round (lesson 105). The statement is short. Vehicles arrive, get a slot and a ticket, and pay when they leave. Then the interviewer gives one new requirement, for example monthly passes.

The interviewer does not care about parking. They look at three things. Did you choose sensible classes? Did you keep the rules that may change in a separate place? Did the new requirement fit with a small change?

A weak answer puts everything in one class, with chains of if on the vehicle type. It works for the first version. Then the new requirement needs edits in many places, and each edit can break old code. A strong answer uses a few small classes and runs the thin version early. It adds the new rule as a new small class and says why the change was small.

At SDE-1 level, you should reach working code with clear classes. At SDE-2 level, you should add the new requirement with a small change. At SDE-3 level, you should also say what the design costs, and when simpler code is better. This is our own guide, not an official rule.

Think of the person at the gate of a mall parking lot. This person has a board that shows the free slots, a book of tickets and a rate card. When a car arrives, the person looks at the board and picks a slot. When it leaves, the person reads the ticket, looks at the rate card and says the fee. If the mall changes its prices, the owner gives a new rate card. The job does not change.

Only the rule cards change. We build the same thing in code.

Low-level design (LLD) means choosing the classes and methods of a small program before you write it. This lesson takes one problem from the statement to working code. Then it adds a new requirement. The code is Python, as in lesson 106. The ideas are the same in other languages.

The statement

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

1. A mall lot has floors, numbered from 1. Every floor has the same number of bike slots, car slots and truck slots. A slot fits only one type of vehicle.
2. On a floor, slots are numbered S1, S2 and so on: bike slots first, then car slots, then truck slots. A slot id looks like "F2-S3", which means floor 2, slot 3.
3. A vehicle gets the free slot of its type with the lowest floor, and on that floor the lowest number. It also gets a ticket: "T1", "T2" and so on. If no slot is free, it gets an empty text, and no ticket number is used.
4. When the vehicle leaves, the ticket is closed, the slot is free again, and the lot returns the fee.
5. The fee: a stay of 15 minutes or less is free. Otherwise every started hour costs Rs 10 for a bike, Rs 20 for a car and Rs 50 for a truck. For every started 24 hours, the fee is never more than 8 hours' worth.
6. Bad input is an error. The bad inputs are: an unknown vehicle type, a plate that is already parked, an unknown or closed ticket, and leaving before entering. A plate is the number plate of the vehicle.
7. The lot answers four questions. How many slots of a type are free? Where is a ticket parked? Which plates are parked? How much money has the lot collected?

Time is a whole number of minutes. Everything stays in memory, and calls arrive one after another. The rates are the practice problem's values, made up for teaching.

Step 1: nouns become classes

Lesson 109 showed how to find classes. Underline the nouns in the statement. Keep a noun as a class when it has its own data or its own rules. Keep it as a plain value when it is only a number or a word. The verbs become methods. Some helpers are not nouns in the statement, but they have one clear job.

We add one helper, SlotPool. It is the board of free slots, kept in order for each type.

Step 2: rules that may change become strategies

Lesson 106 showed a Discount abstract class, and an order service that receives one Discount object. Lesson 107 named this shape a strategy: one rule in its own small class with one method. The main class holds one strategy and calls it. To change the rule, you pass in another object.

Which rules may change? Read the statement again. Two rules look like choices that the mall can change: how to choose a slot, and how to work out a fee. In the practice round, the interviewer also says that the lot may get new vehicle types and slot types. So we make two strategies:

• SlotPicker has one method, choose(pool, vehicle, time). It takes a slot from the pool, or returns None. We pass the whole vehicle and the time, not only the type, because a rule often needs more than the type.
• FeeRule has one method, fee(ticket, leave). It returns the fee in rupees.

Other parts stay plain. The ticket counter is a number that goes up by one. Nobody asked to change it, so it does not get a class.

Step 3: build the thin path first

Lesson 105 said to build the thinnest path that runs. Here that is park and leave. The order is: the three data classes, the pool, the two strategies, then ParkingLot with park and unpark. Run it. Then add the counts, the plates and the error cases.

First, the data classes. @dataclass is a Python helper that writes the constructor (the method that sets up a new object) for a small data class. With frozen=True the object cannot change. With order=True two slots can be compared, first by floor and then by number. That order is exactly the rule in point 3.

from dataclasses import dataclass

VEHICLE_TYPES = ("BIKE", "CAR", "TRUCK")

@dataclass(frozen=True, order=True)
class Slot:
    floor: int
    number: int
    type: str

    @property
    def id(self):
        return f"F{self.floor}-S{self.number}"

@dataclass(frozen=True)
class Vehicle:
    plate: str
    type: str

@dataclass
class Ticket:
    id: str
    vehicle: Vehicle
    slot: Slot
    entry: int

Next, the pool. A heap keeps a list so that the smallest item always comes out first, and each push or pop is fast. Python's heapq module does this. We keep one heap of free slots for each type. The smallest slot is the one with the lowest floor and lowest number, so take always returns the right slot. The constructor below fills each heap, floor by floor.

from heapq import heappop, heappush

class SlotPool:
    def __init__(self, floors, bike_slots, car_slots, truck_slots):
        self.free = {kind: [] for kind in VEHICLE_TYPES}
        counts = (("BIKE", bike_slots), ("CAR", car_slots), ("TRUCK", truck_slots))
        for floor in range(1, floors + 1):
            number = 0
            for kind, count in counts:
                for _ in range(count):
                    number += 1
                    heappush(self.free[kind], Slot(floor, number, kind))

The rest of SlotPool has three small methods.

    def take(self, kind):
        heap = self.free[kind]
        return heappop(heap) if heap else None

    def give_back(self, slot):
        heappush(self.free[slot.type], slot)

    def count(self, kind):
        return len(self.free[kind])

Now the two strategies. Each has an abstract class (the promise) and one real class. In HourlyFee, the line (minutes + 59) // 60 rounds up to whole hours, because // divides and drops the fraction. The same trick gives the started days.

from abc import ABC, abstractmethod

class SlotPicker(ABC):
    @abstractmethod
    def choose(self, pool, vehicle, time):
        """Take a slot out of the pool, or return None."""

class OwnTypePicker(SlotPicker):
    def choose(self, pool, vehicle, time):
        return pool.take(vehicle.type)

class FeeRule(ABC):
    @abstractmethod
    def fee(self, ticket, leave):
        """Return the fee in rupees."""

class HourlyFee(FeeRule):
    RATES = {"BIKE": 10, "CAR": 20, "TRUCK": 50}

    def fee(self, ticket, leave):
        minutes = leave - ticket.entry
        if minutes <= 15:
            return 0
        hours = (minutes + 59) // 60
        days = (minutes + 1439) // 1440
        return min(hours, 8 * days) * self.RATES[ticket.vehicle.type]

Last, the main class, in four blocks. The later blocks continue the same class. It holds the pool, one picker and one fee rule. It keeps the open tickets and the plates that are parked now. park returns "" when no slot is free, and the ticket number goes up only after a slot is found.

class ParkingLot:
    def __init__(self, floors, bike_slots, car_slots, truck_slots):
        self.pool = SlotPool(floors, bike_slots, car_slots, truck_slots)
        self.picker = OwnTypePicker()
        self.fee_rule = HourlyFee()
        self.open_tickets = {}
        self.parked = set()
        self.ticket_count = 0
        self.revenue = 0

    def park(self, plate, vehicle_type, time):
        if vehicle_type not in VEHICLE_TYPES:
            raise ValueError("unknown vehicle type")
        if plate in self.parked:
            raise ValueError("this plate is already parked")
        vehicle = Vehicle(plate, vehicle_type)
        slot = self.picker.choose(self.pool, vehicle, time)
        if slot is None:
            return ""
        self.ticket_count += 1
        ticket = Ticket(f"T{self.ticket_count}", vehicle, slot, time)
        self.open_tickets[ticket.id] = ticket
        self.parked.add(plate)
        return ticket.id

    def slot_of(self, ticket_id):
        ticket = self.open_tickets.get(ticket_id)
        return ticket.slot.id if ticket else ""

    def unpark(self, ticket_id, time):
        ticket = self.open_tickets.get(ticket_id)
        if ticket is None:
            raise ValueError("unknown or closed ticket")
        if time < ticket.entry:
            raise ValueError("exit before entry")
        fee = self.fee_rule.fee(ticket, time)
        del self.open_tickets[ticket_id]
        self.parked.remove(ticket.vehicle.plate)
        self.pool.give_back(ticket.slot)
        self.revenue += fee
        return fee

    def available_slots(self, vehicle_type):
        if vehicle_type not in VEHICLE_TYPES:
            raise ValueError("unknown vehicle type")
        return self.pool.count(vehicle_type)

    def parked_plates(self):
        return sorted(self.parked)

    def total_revenue(self):
        return self.revenue

Look at park and unpark. They never say "bike", "car" or "truck" except in the check for a bad type. They ask the picker for a slot and the fee rule for a fee. That is the point of the strategies.

We use a small lot: 2 floors, and every floor has 1 bike slot, 2 car slots and 1 truck slot. Assumption: these sizes are made up to teach with. Each floor has 1 + 2 + 1 = 4 slots. The ids on a floor are S1 for the bike, S2 and S3 for cars, and S4 for the truck.

Cars arrive.

1. KA01 (car) arrives at minute 0. The lowest free car slot is F1-S2. The ticket is T1.
2. KA02 (car) arrives at minute 5. F1-S2 is taken, so it gets F1-S3 and ticket T2.
3. KA03 (car) arrives at minute 6. Both car slots on floor 1 are taken. Floor 2 comes next, so it gets F2-S2 and T3. The lowest number on floor 2 for a car is S2, because S1 is the bike slot.

Cars leave.

• T1 leaves at minute 115. The stay is 115 - 0 = 115 minutes. That is more than 15. Started hours: (115 + 59) // 60 = 174 // 60 = 2. Started days: (115 + 1439) // 1440 = 1, so the cap is 8 x 1 = 8 hours. min(2, 8) = 2 hours. The fee is 2 x Rs 20 = Rs 40.
• T2 leaves at minute 20. The stay is 20 - 5 = 15 minutes. That is not more than 15, so the fee is Rs 0.
• A truck stays 181 minutes. Started hours: (181 + 59) // 60 = 240 // 60 = 4. The fee is 4 x Rs 50 = Rs 200.

Total collected so far: 40 + 0 + 200 = Rs 240.

The edges of the fee rule. Most mistakes happen at the limits of the rule, such as 15, 60 and 61 minutes. These are the fees for a car (Rs 20 per hour), worked out by the code above:

The predict box. The free time is the number 15 inside HourlyFee. To change it, we change 15 to 30 in that one class. One class changes, and park and unpark do not change. A 25-minute car stay now costs Rs 0. Before, it cost (25 + 59) // 60 = 1 hour x Rs 20 = Rs 20.

The new requirement: monthly passes. The interviewer says: "A pass is registered for a plate with a last valid time. A vehicle that parks at or before that time stays free for the whole visit. A pass holder whose own slot type is full may use a free slot of the next bigger type. A bike can use a car slot, and a car can use a truck slot. Everyone else still gets only their own type." We add three small classes. A registry is a small class that remembers one kind of fact. Here it remembers the passes. The old classes stay as they are.

class PassRegistry:
    def __init__(self):
        self.valid_until = {}

    def register(self, plate, valid_until):
        self.valid_until[plate] = valid_until

    def is_active(self, plate, time):
        return plate in self.valid_until and self.valid_until[plate] >= time

NEXT_BIGGER = {"BIKE": "CAR", "CAR": "TRUCK"}

class PassOverflowPicker(SlotPicker):
    def __init__(self, passes):
        self.passes = passes
        self.normal = OwnTypePicker()

    def choose(self, pool, vehicle, time):
        slot = self.normal.choose(pool, vehicle, time)
        if slot is None and self.passes.is_active(vehicle.plate, time):
            bigger = NEXT_BIGGER.get(vehicle.type)
            if bigger:
                slot = pool.take(bigger)
        return slot

class PassFee(FeeRule):
    def __init__(self):
        self.normal = HourlyFee()

    def fee(self, ticket, leave):
        return 0 if ticket.free_stay else self.normal.fee(ticket, leave)

PassOverflowPicker first asks the old picker. Only when that finds nothing, and the plate has an active pass, does it try the next bigger type. PassFee returns 0 for a free stay and otherwise asks the old fee rule. Now the few changes to old code:

1. Ticket gets one new line: free_stay: bool = False. The rule says that the pass at the park time decides, so we save that answer on the ticket. Without it, a pass changed during the visit could change the fee.
2. In the constructor, the two strategy lines become three: self.passes = PassRegistry(), self.picker = PassOverflowPicker(self.passes) and self.fee_rule = PassFee().
3. In park, the line that builds the ticket becomes two: free = self.passes.is_active(plate, time) and ticket = Ticket(f"T{self.ticket_count}", vehicle, slot, time, free).
4. Two new methods on ParkingLot (the requirement asks for them): register_pass and has_active_pass. Each is one line that calls the registry.

unpark, SlotPool, OwnTypePicker and HourlyFee have 0 changed lines.

Now the numbers. Pass holder KA01 has a pass valid until minute 1,000. It parks a car at minute 10, and the pass is active (1,000 is at least 10). It leaves at minute 500. The fee is Rs 0. Without a pass, the stay is 500 - 10 = 490 minutes. Started hours: (490 + 59) // 60 = 9, capped at 8, so 8 x Rs 20 = Rs 160. The pass saves Rs 160, and the total collected does not grow.

Overflow: a lot of 1 floor with 1 bike slot, 1 car slot and 1 truck slot. B1 (no pass) parks a bike in F1-S1. P1 has a pass and parks a bike. The bike slot is full, so P1 gets the car slot F1-S2, and available_slots("CAR") becomes 0. P2 also has a pass and parks a bike. The bike slot and the car slot are both taken. The picker goes one step up only, so P2 gets "" and no ticket.

• Strategies solve the cost of change. The pass rule was 3 new classes and a few changed lines, and the old fee and slot code stayed safe. They cost more classes, and one more jump when you read the code. I would not add a strategy for a rule that nobody asked to change, such as the ticket counter. I would add one when two real versions of the rule exist, or the interviewer says one is coming.
• A heap for each type solves slow slot search. It costs the extra SlotPool class. Assumption: a lot has 10,000 slots. A scan over all slots may check up to 10,000 slots for each car. A heap needs about 14 steps, because halving 10,000 again and again reaches 1 after about 14 steps. For a lot of a few dozen slots, I would use a simple scan. It is shorter to write in a timed round.
• Saving the pass answer on the ticket solves a pass that changes during a visit. It costs one field and one line in park. I would remove it if the rule said that the pass at leaving time decides.
• Keeping ParkingLot as the only class the tests call solves a stable public API. It costs a few extra methods on that class when the requirement grows. I would split the class only when it becomes too big to read.

"Every noun in the statement needs its own class." Floor, fee and time did not get classes. A noun becomes a class when it has its own data or rules. A floor has only a number, and Slot already keeps it.

"A strategy class for every rule makes the design flexible." Extra classes cost time in a timed round. They also make the code harder to read. Only the slot choice and the fee were likely to change. The ticket counter stayed a number.

"A new requirement means rewriting the code that works." The pass requirement needed three new classes. In old code, one line was added to Ticket, two lines became three in the constructor, and one line became two in park. The old rules still work, because the strategies keep them apart.

1. Name the data classes and the main classes of the design, and the two strategies. What does each strategy receive and return?
2. Use the fee rule of this lesson. (a) A truck stays 1,500 minutes. What is the fee? (b) A bike stays 100 minutes. What is the fee?
3. The interviewer says: "Bikes may use a free car slot when all bike slots are full. This is for everyone, not only pass holders." Where do you change the code, and do park and unpark change?