Multi-Floor Parking Lot

Park a vehicle, hand back a ticket, charge a fee on the way out. Alongside Splitwise this is the machine-coding round companies set most often, and it is set specifically because the naive solution falls apart on cue: spot allocation is a check-then-act pair that two entry gates can race on, "which spot" and "what fee" are policies that evaluators change mid-round ("motorcycles can take car spots", "weekend rates"), and the ticket has a lifecycle with real invalid states. The design that survives is small: a model with compatibility built in, two strategies, per-floor locking, and a stress test that would catch a double booking.

Target behaviour

Build until your program prints this.

> init floors=2 motorcycle=3 car=3 truck=2
> park car KA-01-AB-1234
ticket T-1  car KA-01-AB-1234  spot F1-CAR-1
> park motorcycle KA-05-MN-2
ticket T-2  motorcycle KA-05-MN-2  spot F1-MCY-1
> unpark T-1
KA-01-AB-1234  stayed 2h 15m  fee 65.00  spot F1-CAR-1 free
> status
F1  cars 2/3  motorcycles 3/3  trucks 2/2   FULL for motorcycles
F2  cars 3/3  motorcycles 3/3  trucks 2/2

Model with compatibility built in

Which vehicle fits in which spot is domain data, so it lives in the types, not in if chains sprinkled through services. A motorcycle takes a motorcycle spot and falls back to a car spot; a car never takes a motorcycle spot; a truck only a truck spot.

public enum SpotType { MOTORCYCLE, CAR, TRUCK }

public enum VehicleType {
    MOTORCYCLE(EnumSet.of(SpotType.MOTORCYCLE, SpotType.CAR)),
    CAR(EnumSet.of(SpotType.CAR)),
    TRUCK(EnumSet.of(SpotType.TRUCK));

    final Set<SpotType> fits;
    VehicleType(Set<SpotType> fits) { this.fits = fits; }
    boolean fitsIn(SpotType s) { return fits.contains(s); }
}

EnumSet iterates in declaration order, so "prefer the tightest spot" is free: try MOTORCYCLE before CAR for a bike. A floor keeps one TreeSet of free spots per type, ordered by spot number, so pollFirst is the lowest free spot — O(log n) instead of a scan.

public final class Floor {
    private final int number;
    private final Map<SpotType, TreeSet<Spot>> free = new EnumMap<>(SpotType.class);
    // constructor creates one TreeSet per type, ordered by Comparator.comparing(Spot::number)
}

Tickets and lifecycle

A ticket is immutable except that it is either active or redeemed — model that as two types or one record plus an active-tickets map, never a mutable isPaid flag everyone can set.

public record Ticket(String id, VehicleType type, String plate,
                     Spot spot, Instant enteredAt) {}

public record Vehicle(VehicleType type, String plate) {}

Active tickets live in a Map<String, Ticket>; unpark validates the ticket exists (unknown id is a clean error, not a null dereference), returns the spot to the floor it came from, and computes the fee. Ticket ids come from an AtomicLong — sequential, sortable, and safe across gates. Note the spot id encodes its floor (F1-CAR-1): returning a spot to the wrong floor's TreeSet is the classic unpark bug.

Two policies, two strategies

"Which spot" and "what fee" are the two things evaluators change mid-round, so both are interfaces with a default implementation. Allocation walks floors and types in order; the interface makes "fill floor 1 first so floor 2 can close" or "nearest to the exit" a new class, not a rewrite.

public interface AllocationStrategy {
    Optional<Spot> allocate(List<Floor> floors, Vehicle vehicle);
}

Pricing is where integer math and boundary conditions bite. Fees are cents per hour, rounded up to the next started hour — with the boundary decided and tested: exactly 60 minutes is one hour, 61 is two.

public final class HourlyFee implements FeeStrategy {
    private final Map<VehicleType, Long> centsPerHour;

    public HourlyFee(Map<VehicleType, Long> centsPerHour) { this.centsPerHour = centsPerHour; }

    @Override
    public long feeCents(VehicleType type, Duration stay) {
        long hours = (stay.toMinutes() + 59) / 60;    // ceil division: 60m -> 1h, 61m -> 2h
        return hours * centsPerHour.get(type);
    }
}

A weekend rate becomes a decorator around any FeeStrategy, which is a stronger interview answer than an if (weekend) inside the class.

Thread safety: the check-then-act trap

Finding a free spot and claiming it must be one atomic step. If two gates scan the floor list and then claim independently, both hand out F1-CAR-2. The lock must cover find-plus-claim, and it belongs on the floor, not the whole lot: gates on different floors should not contend.

public final class Floor {
    synchronized Optional<Ticket> tryPark(Vehicle v, Instant at, LongSupplier nextId) {
        for (SpotType type : v.type().fits.stream().sorted().toList()) {
            Spot spot = free.get(type).pollFirst();
            if (spot != null)
                return Optional.of(new Ticket("T-" + nextId.getAsLong(), v.type(), v.plate(), spot, at));
        }
        return Optional.empty();
    }

    synchronized void release(Spot spot) { free.get(spot.type()).add(spot); }
}

VehicleType.fits is an immutable EnumSet shared by all threads — read-only sharing is safe; a .sorted().toList() copy avoids relying on another thread's view of a shared set. ParkingLot.park scans floors outside any global lock because the floors list is immutable after init; each floor's own lock makes the claim atomic.

public Optional<Ticket> park(Vehicle v) {
    for (Floor floor : floors) {
        var ticket = floor.tryPark(v, clock.instant(), ids::incrementAndGet);
        if (ticket.isPresent()) return ticket;
    }
    return Optional.empty();   // lot full for this vehicle type
}

A Clock is injected and fixed in tests, so a two-hour stay is clock.advance instead of Thread.sleep — deterministic fees, fast tests.

Testing

Functional tests pin the boundaries: exact-hour fees, motorcycle fallback to a car spot, no car in a motorcycle spot, unknown ticket rejected, spot reusable after unpark. The test that earns the design points is the stress test: 120 concurrent gates, 100 spots, exactly 100 tickets, no spot twice.

@Test
void concurrentGatesNeverDoubleBook() throws Exception {
    ParkingLot lot = ParkingLot.init(2, 50, 50, 0);   // 100 car spots
    var start = new CountDownLatch(1);
    var tickets = new ConcurrentLinkedQueue<Ticket>();
    try (var pool = Executors.newFixedThreadPool(120)) {
        var futures = IntStream.range(0, 120).mapToObj(i -> pool.submit(() -> {
            start.await();
            lot.park(new Vehicle(VehicleType.CAR, "KA-" + i)).ifPresent(tickets::add);
        })).toList();
        start.countDown();
        futures.forEach(f -> f.get());
    }
    assertThat(tickets).hasSize(100);
    assertThat(tickets.stream().map(Ticket::spot).distinct()).hasSize(100);
}

If that second assertion ever fails with a bigger collection, you found a double booking — the single most convincing bug to catch in front of an evaluator.

Bugs you will hit

• Scanning for a spot outside the lock, claiming inside it. The race window is tiny and the demo works every time — right up until the stress test. Find and claim under one lock.
• Returning a spot to the wrong type. A motorcycle took a CAR spot as fallback; unpark code that releases into MOTORCYCLE "because it is a bike" silently grows the car pool. The spot knows its type; the vehicle does not decide.
• Truncating instead of rounding the stay. stay.toMinutes() / 60 makes a 59-minute stay free and a 61-minute stay one hour. Ceil division (m + 59) / 60 and a test at exactly 60 minutes.
• SimpleDateFormat or LocalDateTime for durations. A DST jump shifts wall-clock durations; Instant plus Duration.between is monotonic and correct. Parking across a DST night is a real interview follow-up.
• One global lock "to be safe". Correct but a throughput answer killer: it serializes all gates. Lock the floor, not the lot, and say why contention scope matters.

Interview angle

• Why strategies instead of an if on vehicle type? Policies are the stated requirements most likely to change (rates, spot preference, weekend pricing). Interfaces confine each change to one new class — and a decorator composes weekend pricing with any base fee without touching it.
• Why TreeSet and not a List of spots? pollFirst gives the lowest free spot in O(log n) inside the lock, and the set doubles as the free/occupied bookkeeping. A scanned List is O(n) per park and grows with the lot.
• Is per-floor locking correct? Yes, because a vehicle claims a spot on exactly one floor and the floor list is immutable after init. It is also the scalability answer: gates on different floors proceed in parallel.
• What breaks with two application instances? The in-memory free set: two JVMs each hand out F1-CAR-2. The honest answer is a shared store — spots as rows with a conditional update (UPDATE spot SET occupied=? WHERE id=? AND occupied=false) or a Redis lock — and it is worth volunteering before being asked.
• Why is unpark a state transition, not a delete? A redeemed ticket must not be redeemable again (double refund/free exit), and the audit trail of visits is business data. Same reasoning as a settled order: the event stays, the state changes.