Frontend Prep

Appearance

40 — LLD: Parking Lot with Billing ​

Google context: This exact problem surfaced in L4 loops throughout 2025. Google rarely runs a dedicated LLD round — instead, the interviewer will code with you, then pivot halfway through to "now let us make this clean." The signal is whether you can evolve a working prototype into a maintainable design without rewriting the world. Treat every snippet below as a refactoring step, not a final answer.

Understanding the Problem ​

A parking lot issues tickets when vehicles enter, tracks how long each vehicle stays, and charges a bill at exit. The lot has a fixed inventory of spots per vehicle type (cars, bikes, trucks) and a billing rate per minute per vehicle type. You are given two arrays at construction — one describing the spot inventory, one describing the rates.

What is a Parking Lot with Billing?

Think of a mall garage. You pull in, a machine prints a ticket, you park in a spot sized for your vehicle, and when you leave the machine reads your ticket, computes duration * rate_for_vehicle_type, and charges you. The design question is how to keep spot allocation, billing, and vehicle classification as three independent concerns you can evolve separately.

Requirements ​

Clarifying Questions ​

You: The inputs are [(vehicleType, slots)] and [(vehicleType, costPerMin)]. So the lot is configured at startup and then we run entry and exit operations against it. Correct?

Interviewer: Yes. The configuration is static for the lifetime of the system.

So inventory is immutable after construction. That simplifies concurrency — the only mutable state is occupancy, not the topology.

You: What vehicle types should I support out of the gate?

Interviewer: Car, bike, truck. But assume a fourth type could be added later — say, a van.

That is a direct open/closed hint. I should avoid switch statements on vehicle type.

You: On entry, do we just grab any available spot of the right type, or is there a preference — closest to entrance, lowest ID?

Interviewer: Let us pick the lowest-numbered available spot for now. But imagine we later want to prefer handicapped-accessible spots for handicapped drivers.

That is the allocation strategy hint — I want a pluggable strategy, not a hardcoded loop.

You: What about the billing model — is it always minutes * rate, or do we want tiered pricing?

Interviewer: Start with flat per-minute. But I might ask you to switch to "first 30 minutes free, then per-minute" later.

Strategy pattern for billing too. The bill calculation has to be swappable without touching entry/exit code.

You: What happens if the lot is full for a given vehicle type?

Interviewer: Reject the entry with a clear error. Do not overflow into a different vehicle type's spots.

Simplifying assumption: strict type matching. No truck parking in two car spots.

You: What about a lost ticket? Do we need to handle that?

Interviewer: Out of scope for now. Assume the ticket is always presented at exit.

You: Multi-floor, multi-entrance?

Interviewer: Single lot, single level for now. Design so it can extend.

Final Requirements ​

  1. Construct the lot from [(vehicleType, slotCount)] and [(vehicleType, costPerMinute)].
  2. enter(vehicle) -> Ticket — allocate a spot of the matching type, record entry time, return a ticket.
  3. exit(ticket) -> Bill — compute duration, look up the rate, return a bill, free the spot.
  4. Reject entry when no matching spot is available.
  5. The billing strategy must be swappable per vehicle type (flat, tiered, hourly minimum).
  6. The allocation strategy must be swappable (first-fit today, best-fit or preference-aware tomorrow).

Out of scope: Lost tickets, payment processing, reservations, dynamic pricing based on occupancy, persistence across restarts.

Deferred tradeoffs: We keep allocation in-memory — no database. We assume a single JVM/process — distributed allocation is a separate conversation.

Core Entities and Relationships ​

Walking through the nouns from the requirements:

  • Vehicle — has a type and an identifier (license plate). Deserves a class because it is the thing we key billing on.
  • VehicleType — is this an enum or a class? Enum is tempting, but if we want extensibility (vans, motorcycles, EVs) without recompiling every switch, a lightweight class or at minimum a string key feels safer. We will start with an enum and refactor if needed.
  • Spot — a single parking space. Knows its ID and the type it accepts. A field? No — it has behavior (occupy, release) and a lifecycle distinct from the lot.
  • Ticket — a receipt of entry. Needs a unique ID, vehicle reference, spot reference, entry timestamp.
  • Bill — computed at exit. Could be a return value rather than a persisted entity, but wrapping it in a class lets us return structured data (base fare, duration, breakdown).
  • ParkingLot — orchestrates entry and exit.
  • AllocationStrategy — how we pick among available spots.
  • BillingStrategy — how we compute the bill for a given duration and vehicle type.
EntityResponsibility
VehicleTypeEnum of supported vehicle classes
VehicleHolds license plate and type
SpotA single parking space, tracks occupancy
TicketEntry receipt — links vehicle to spot with a timestamp
BillExit computation — duration, rate, total
AllocationStrategyPicks which available spot to assign
BillingStrategyComputes the bill from duration and rate
ParkingLotTop-level service — coordinates entry, exit, and strategies

Design is iterative. We will start with FirstFitAllocation and FlatRateBilling, and the extensibility section will show how clean swaps look.

Class Design ​

VehicleType (Enum) ​

CAR, BIKE, TRUCK

Starting with an enum keeps things readable. If we need per-type behavior later (e.g., EV needs a charging port), we promote to a class hierarchy.

Vehicle ​

State:

  • licensePlate: string
  • type: VehicleType

Methods: None beyond getters. Vehicles are value objects.

Spot ​

State:

  • spotId: string
  • type: VehicleType
  • occupied: boolean

Methods:

  • occupy() — marks as taken
  • release() — marks as free

A spot does not know about the lot or the ticket. That is deliberate — a spot is a physical location, not a manager.

Ticket ​

State:

  • ticketId: string
  • vehicle: Vehicle
  • spot: Spot
  • entryTime: Instant

Bill ​

State:

  • ticket: Ticket
  • exitTime: Instant
  • durationMinutes: long
  • amount: BigDecimal

AllocationStrategy (Interface) ​

Methods:

  • pick(available: List<Spot>) -> Spot — given the list of free spots for a type, pick one.

BillingStrategy (Interface) ​

Methods:

  • compute(durationMinutes: long, costPerMin: BigDecimal) -> BigDecimal

ParkingLot ​

State:

  • spotsByType: Map<VehicleType, List<Spot>> — all spots grouped by type
  • availableByType: Map<VehicleType, Deque<Spot>> — free spots for O(1) allocation
  • rates: Map<VehicleType, BigDecimal>
  • allocation: AllocationStrategy
  • billing: BillingStrategy
  • activeTickets: Map<String, Ticket>

Methods:

  • enter(vehicle) -> Ticket
  • exit(ticketId) -> Bill

Design decisions worth surfacing:

  • Why does ParkingLot hold both spotsByType and availableByType? The first is the source of truth (useful for reporting). The second is an index for fast allocation. Keeping both costs one list per type and is worth it.
  • Why is the billing strategy a single object and not per-vehicle-type? Because the policy is typically lot-wide ("we do flat rate here, tiered rate there"). The per-type difference is captured in the rate, not the algorithm. If you need per-type algorithms, you extend to Map<VehicleType, BillingStrategy>.

Design principles:

  • Strategy Pattern for allocation and billing — the two axes of change we expect.
  • Information Expert — Spot owns its occupancy. ParkingLot owns cross-spot decisions.
  • Open/Closed — adding a new vehicle type means adding an enum value and a rate; no existing code changes.

Implementation ​

Core Method: enter(vehicle) ​

Steps:

  1. Find the bucket of free spots matching vehicle.type.
  2. If empty, throw "lot full for this type".
  3. Ask allocation.pick(...) to choose a spot.
  4. Mark the spot occupied, create a ticket with the current time, store it.
  5. Return the ticket.

Edge cases:

  • Unknown vehicle type (not configured) — reject with "unsupported type".
  • Full bucket — reject.

Core Method: exit(ticketId) ​

Steps:

  1. Look up the ticket. If missing, throw "invalid ticket".
  2. Compute durationMinutes from now - entryTime.
  3. Look up the rate for the vehicle type.
  4. Call billing.compute(durationMinutes, rate).
  5. Release the spot, return it to the available bucket, remove the ticket.
  6. Return a Bill.

Edge cases:

  • Duration rounding — do we round up to the next minute, or use fractional minutes? I charge for any started minute (common in real lots). A billing strategy can override if needed.
  • Re-entry with the same ticket — after exit we remove from activeTickets, so a second exit throws "invalid ticket".

Algorithmic decision: how to find the next free spot ​

Bad: Scan spotsByType[type] linearly every entry, checking occupied. O(n) per entry. Fine for 100 spots, painful for 10,000.

Good: Maintain a List<Spot> of free spots and iterate. Still O(n) for best-fit, but allocation strategy can do O(1) for first-fit by popping the head.

Great: Deque<Spot> of free spots per type. FirstFitAllocation pops from the head in O(1). On release, push back. If allocation strategy changes to best-fit based on size subclasses, we swap to a TreeMap or priority queue behind the AllocationStrategy interface without touching the rest.

I ship the Deque version because it handles today's requirement in O(1) and the strategy interface lets me upgrade later.

Verification ​

Setup: lot built with [("car", 2), ("bike", 1)] and rates [("car", 0.10), ("bike", 0.05)]. Flat billing, first-fit allocation.

State: availableByType = {CAR: [C1, C2], BIKE: [B1]}, activeTickets = {}.

Step 1 — Car "KA-01" enters at t=0.

  • Pull CAR bucket: [C1, C2]. pick returns C1. Pop.
  • C1.occupy(). Ticket T1 created: vehicle=KA-01, spot=C1, entryTime=t0.
  • State: availableByType = {CAR: [C2], BIKE: [B1]}, activeTickets = {T1}.

Step 2 — Bike "KA-02" enters at t=5.

  • Pull BIKE bucket: [B1]. Pop. B1.occupy().
  • Ticket T2 created.
  • State: availableByType = {CAR: [C2], BIKE: []}, activeTickets = {T1, T2}.

Step 3 — Bike "KA-03" tries to enter at t=10.

  • BIKE bucket empty. Throw LotFullException("BIKE").

Step 4 — Car "KA-01" exits at t=35.

  • Look up T1. Duration = 35 min. Rate = 0.10/min.
  • billing.compute(35, 0.10) = 3.50.
  • C1.release(). Push C1 back to CAR bucket. Remove T1.
  • Return Bill(T1, 35 min, $3.50).
  • State: availableByType = {CAR: [C2, C1], BIKE: []}, activeTickets = {T2}.

State is consistent at every step. No orphan tickets, no double-released spots.

Complete Code Implementation ​

java
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.time.Duration;
import java.time.Instant;
import java.util.*;

enum VehicleType { CAR, BIKE, TRUCK }

final class Vehicle {
    final String licensePlate;
    final VehicleType type;
    Vehicle(String p, VehicleType t) { licensePlate = p; type = t; }
}

final class Spot {
    final String spotId;
    final VehicleType type;
    boolean occupied = false;
    Spot(String id, VehicleType t) { spotId = id; type = t; }
    void occupy() { occupied = true; }
    void release() { occupied = false; }
}

final class Ticket {
    final String ticketId;
    final Vehicle vehicle;
    final Spot spot;
    final Instant entryTime;
    Ticket(String id, Vehicle v, Spot s, Instant t) {
        ticketId = id; vehicle = v; spot = s; entryTime = t;
    }
}

final class Bill {
    final Ticket ticket;
    final Instant exitTime;
    final long durationMinutes;
    final BigDecimal amount;
    Bill(Ticket t, Instant e, long d, BigDecimal a) {
        ticket = t; exitTime = e; durationMinutes = d; amount = a;
    }
}

interface AllocationStrategy {
    Spot pick(Deque<Spot> available);
}

final class FirstFitAllocation implements AllocationStrategy {
    public Spot pick(Deque<Spot> available) { return available.pollFirst(); }
}

interface BillingStrategy {
    BigDecimal compute(long durationMinutes, BigDecimal costPerMin);
}

final class FlatRateBilling implements BillingStrategy {
    public BigDecimal compute(long minutes, BigDecimal rate) {
        return rate.multiply(BigDecimal.valueOf(minutes))
                   .setScale(2, RoundingMode.HALF_UP);
    }
}

final class ParkingLot {
    private final Map<VehicleType, Deque<Spot>> available = new EnumMap<>(VehicleType.class);
    private final Map<VehicleType, BigDecimal> rates;
    private final Map<String, Ticket> active = new HashMap<>();
    private final AllocationStrategy allocation;
    private final BillingStrategy billing;

    ParkingLot(List<Map.Entry<VehicleType, Integer>> inventory,
               Map<VehicleType, BigDecimal> rates,
               AllocationStrategy allocation,
               BillingStrategy billing) {
        this.rates = Map.copyOf(rates);
        this.allocation = allocation;
        this.billing = billing;
        for (var entry : inventory) {
            Deque<Spot> bucket = new ArrayDeque<>();
            for (int i = 0; i < entry.getValue(); i++) {
                bucket.offer(new Spot(entry.getKey() + "-" + i, entry.getKey()));
            }
            available.put(entry.getKey(), bucket);
        }
    }

    synchronized Ticket enter(Vehicle v) {
        Deque<Spot> bucket = available.get(v.type);
        if (bucket == null) throw new IllegalArgumentException("Unsupported type: " + v.type);
        if (bucket.isEmpty()) throw new IllegalStateException("Lot full for " + v.type);
        Spot s = allocation.pick(bucket);
        s.occupy();
        Ticket t = new Ticket(UUID.randomUUID().toString(), v, s, Instant.now());
        active.put(t.ticketId, t);
        return t;
    }

    synchronized Bill exit(String ticketId) {
        Ticket t = active.remove(ticketId);
        if (t == null) throw new IllegalArgumentException("Invalid ticket");
        Instant now = Instant.now();
        long minutes = Math.max(1, Duration.between(t.entryTime, now).toMinutes());
        BigDecimal amount = billing.compute(minutes, rates.get(t.vehicle.type));
        t.spot.release();
        available.get(t.spot.type).offer(t.spot);
        return new Bill(t, now, minutes, amount);
    }
}
cpp
#include <chrono>
#include <deque>
#include <memory>
#include <stdexcept>
#include <string>
#include <unordered_map>

enum class VehicleType { CAR, BIKE, TRUCK };

struct Vehicle { std::string plate; VehicleType type; };

struct Spot {
    std::string id;
    VehicleType type;
    bool occupied = false;
    void occupy() { occupied = true; }
    void release() { occupied = false; }
};

struct Ticket {
    std::string id;
    Vehicle vehicle;
    Spot* spot;
    std::chrono::system_clock::time_point entry;
};

struct Bill {
    std::string ticketId;
    long minutes;
    double amount;
};

struct AllocationStrategy {
    virtual Spot* pick(std::deque<Spot*>& available) = 0;
    virtual ~AllocationStrategy() = default;
};

struct FirstFit : AllocationStrategy {
    Spot* pick(std::deque<Spot*>& available) override {
        if (available.empty()) return nullptr;
        Spot* s = available.front(); available.pop_front(); return s;
    }
};

struct BillingStrategy {
    virtual double compute(long minutes, double ratePerMin) = 0;
    virtual ~BillingStrategy() = default;
};

struct FlatRate : BillingStrategy {
    double compute(long minutes, double rate) override { return minutes * rate; }
};

class ParkingLot {
    std::unordered_map<VehicleType, std::deque<Spot*>> available_;
    std::unordered_map<VehicleType, double> rates_;
    std::unordered_map<std::string, Ticket> active_;
    std::vector<std::unique_ptr<Spot>> spots_;
    AllocationStrategy* allocation_;
    BillingStrategy* billing_;
public:
    ParkingLot(const std::vector<std::pair<VehicleType,int>>& inv,
               std::unordered_map<VehicleType,double> rates,
               AllocationStrategy* a, BillingStrategy* b)
        : rates_(std::move(rates)), allocation_(a), billing_(b) {
        for (auto& [t, n] : inv) {
            auto& bucket = available_[t];
            for (int i = 0; i < n; ++i) {
                auto s = std::make_unique<Spot>();
                s->id = std::to_string((int)t) + "-" + std::to_string(i);
                s->type = t;
                bucket.push_back(s.get());
                spots_.push_back(std::move(s));
            }
        }
    }

    Ticket enter(const Vehicle& v) {
        auto it = available_.find(v.type);
        if (it == available_.end() || it->second.empty())
            throw std::runtime_error("Lot full or type unknown");
        Spot* s = allocation_->pick(it->second);
        s->occupy();
        Ticket t{ std::to_string(rand()), v, s, std::chrono::system_clock::now() };
        active_[t.id] = t;
        return t;
    }

    Bill exit(const std::string& id) {
        auto it = active_.find(id);
        if (it == active_.end()) throw std::runtime_error("Invalid ticket");
        Ticket t = it->second; active_.erase(it);
        auto now = std::chrono::system_clock::now();
        long mins = std::max<long>(1,
            std::chrono::duration_cast<std::chrono::minutes>(now - t.entry).count());
        double amt = billing_->compute(mins, rates_[t.vehicle.type]);
        t.spot->release();
        available_[t.spot->type].push_back(t.spot);
        return { id, mins, amt };
    }
};
typescript
enum VehicleType { CAR = "CAR", BIKE = "BIKE", TRUCK = "TRUCK" }

interface Vehicle { plate: string; type: VehicleType; }

class Spot {
  occupied = false;
  constructor(public readonly id: string, public readonly type: VehicleType) {}
  occupy() { this.occupied = true; }
  release() { this.occupied = false; }
}

class Ticket {
  constructor(
    public readonly id: string,
    public readonly vehicle: Vehicle,
    public readonly spot: Spot,
    public readonly entryTime: Date,
  ) {}
}

class Bill {
  constructor(
    public readonly ticket: Ticket,
    public readonly exitTime: Date,
    public readonly minutes: number,
    public readonly amount: number,
  ) {}
}

interface AllocationStrategy {
  pick(available: Spot[]): Spot | undefined;
}

class FirstFitAllocation implements AllocationStrategy {
  pick(available: Spot[]) { return available.shift(); }
}

interface BillingStrategy {
  compute(minutes: number, costPerMin: number): number;
}

class FlatRateBilling implements BillingStrategy {
  compute(minutes: number, rate: number) { return +(minutes * rate).toFixed(2); }
}

class ParkingLot {
  private available = new Map<VehicleType, Spot[]>();
  private active = new Map<string, Ticket>();

  constructor(
    inventory: Array<[VehicleType, number]>,
    private rates: Map<VehicleType, number>,
    private allocation: AllocationStrategy,
    private billing: BillingStrategy,
  ) {
    for (const [t, n] of inventory) {
      const bucket: Spot[] = [];
      for (let i = 0; i < n; i++) bucket.push(new Spot(`${t}-${i}`, t));
      this.available.set(t, bucket);
    }
  }

  enter(v: Vehicle): Ticket {
    const bucket = this.available.get(v.type);
    if (!bucket) throw new Error(`Unsupported type: ${v.type}`);
    if (bucket.length === 0) throw new Error(`Lot full for ${v.type}`);
    const s = this.allocation.pick(bucket)!;
    s.occupy();
    const t = new Ticket(crypto.randomUUID(), v, s, new Date());
    this.active.set(t.id, t);
    return t;
  }

  exit(ticketId: string): Bill {
    const t = this.active.get(ticketId);
    if (!t) throw new Error("Invalid ticket");
    this.active.delete(ticketId);
    const now = new Date();
    const minutes = Math.max(1, Math.floor((now.getTime() - t.entryTime.getTime()) / 60000));
    const amount = this.billing.compute(minutes, this.rates.get(t.vehicle.type)!);
    t.spot.release();
    this.available.get(t.spot.type)!.push(t.spot);
    return new Bill(t, now, minutes, amount);
  }
}

Extensibility ​

1. "Can you add tiered billing — first 30 minutes free, then per minute?" ​

You answer: "Billing is already a strategy. I add a TieredBilling class that implements BillingStrategy and swap it in at construction. Nothing else in the lot changes."

java
final class TieredBilling implements BillingStrategy {
    private final long freeMinutes;
    TieredBilling(long freeMinutes) { this.freeMinutes = freeMinutes; }
    public BigDecimal compute(long minutes, BigDecimal rate) {
        long chargeable = Math.max(0, minutes - freeMinutes);
        return rate.multiply(BigDecimal.valueOf(chargeable))
                   .setScale(2, RoundingMode.HALF_UP);
    }
}

Tradeoff: Strategies share one rate per vehicle type. If one tier needs a different rate, promote rates into the strategy.

2. "Now we need handicapped-accessible spots and EV charging spots." ​

You answer: "That is two sub-axes of the spot — a base type plus capabilities. I model capabilities as flags on Spot and upgrade AllocationStrategy to be preference-aware. The entry API grows a preferences parameter."

java
final class Spot {
    final String spotId;
    final VehicleType type;
    final Set<SpotFeature> features;     // HANDICAPPED, EV_CHARGER
    boolean occupied = false;
    // ...
}

interface AllocationStrategy {
    Spot pick(Deque<Spot> available, Set<SpotFeature> preferred);
}

final class PreferredFirstAllocation implements AllocationStrategy {
    public Spot pick(Deque<Spot> available, Set<SpotFeature> preferred) {
        for (Spot s : available) {
            if (s.features.containsAll(preferred)) {
                available.remove(s);
                return s;
            }
        }
        return available.pollFirst(); // fallback
    }
}

Tradeoff: Linear scan when preferences exist. If preferences dominate, we index spots by capability. Avoid premature optimization.

3. "We need multi-floor support." ​

You answer: "A Floor holds its own availableByType bucket. ParkingLot becomes a composite of floors and picks a floor-allocation strategy (fill lowest floor first, round-robin, nearest-to-entrance)."

java
final class Floor {
    final String floorId;
    final Map<VehicleType, Deque<Spot>> available;
    // allocate / release scoped to this floor
}

final class ParkingLot {
    private final List<Floor> floors;
    private final FloorSelectionStrategy floorPicker;
    // enter() asks floorPicker which floor, then delegates to that Floor
}

Tradeoff: Two-level strategy composition adds a layer of indirection. Worth it once you actually have multiple floors; overkill for a single lot.

What is Expected at Each Level ​

LevelExpectations
JuniorIdentifies Vehicle, Spot, Ticket, ParkingLot. Writes a working enter/exit with hardcoded vehicle-type handling. May use if/else on type and needs a nudge toward the strategy pattern.
Mid-levelCleanly separates allocation and billing. Picks the Strategy pattern before being asked. Chooses an efficient data structure (deque/queue per type) for O(1) allocation. Handles the lot-full case with a clear exception.
SeniorDrives the conversation. Surfaces the "what are our axes of change?" question out loud, then justifies Strategy on allocation and billing. Discusses thread safety explicitly (synchronized on enter/exit, or a per-type lock to reduce contention). Proactively walks through multi-floor, EV, and tiered billing as extensibility stories — showing the diff is a few new classes and no touched existing code. Google signal: the refactoring instinct is visible — they start with a simple working version, then out loud say "the two things that will change are X and Y, so let me pull them behind interfaces now rather than later."

Frontend interview preparation reference.