Free lesson · Low Level Design Interviews

Step 4: Code Implementation

Hard13 min readlldinterview-prepoop

Step 4 - Code Implementation

by Olena Marchenko - Software Engineer II, Microsoft Azure Developer Tools.

The first three steps produced the design. Scope committed, eight entities modeled, ParkingLot as orchestrator with ReentrantLock at lot-level, two Strategy interfaces injected, sealed ExitResult for typed outcomes. Step 4 implements it.

About 10 minutes from minute 27 to minute 37. The implementation has more surface area than LRU Cache because parking lot has more entities, more methods per entity, and more orchestration flow. The strategy is to implement the central operations (enter, exit) with continuous narration, skeleton the supporting entities, and protect time for verification.

This step is also where lock discipline matters most. enter and exit each have multiple sub-steps that must execute atomically. The pattern from Step 3 (lot-level ReentrantLock with try-finally) becomes reflexive code. Get this wrong and the whole concurrency story falls apart.

The Interviewer's Perspective

When the candidate transitions to implementation, my evaluation shifts to the code.

Did they implement enter and exit correctly? These are the central flows. Each has the lock pattern, the strategy call, the entity state transitions, the counter updates. Strong candidates produce both correctly. Weak candidates produce one of them and run out of time.

Did they handle the ticket lifecycle correctly? Active on entry. Paid after payment success. Closed on exit completion. Each transition through the validated transitionTo method. Missing the lifecycle is a junior signal.

Did they update the counters correctly? Decrement on occupy; increment on release. Inside the lock. Strong candidates produce this reflexively; weak candidates either skip counter updates or update them outside the lock.

Did they call strategies cleanly? allocationStrategy.allocate(this, vehicle) for entry. pricingStrategy.calculateFee(ticket, duration) for exit. The Strategy injections being used demonstrates the design's coherence.

Did they narrate continuously? Each method, each non-obvious choice articulated. The narration is the signal density.

Did they protect verification time? Hard cutoff at minute 37. Whatever isn't done is skeletoned with articulation.

The implementation phase generates about 15-18% of the interviewer's signal on parking lot - slightly less than on LRU Cache because the design has already been so consequential. The implementation confirms; the design produced the signal.

The Candidate's Perspective

Implementation for parking lot has specific shape:

Implement enter and exit first. They're the central flows. Everything else supports them.

Skeleton the supporting classes. Vehicle subclasses, ParkingTicket with state validation, Level with counters, ParkingSpot with canFit. Show the structure; fill in the obvious parts; skeleton or annotate the rest.

Implement one strategy implementation fully. FirstAvailableCompatibleStrategy. Skeleton or annotate alternatives ("similar pattern for nearest-to-entrance").

Implement one pricing strategy. HourlyByTypePricing. Skeleton alternatives.

Use the lock pattern reflexively. ReentrantLock with try-finally on every public method.

Narrate continuously. Silent stretches are signal-loss windows.

Hard cutoff at minute 37. Stop implementing. Pivot to verification.

The candidate's job is to produce correct, idiomatic code for the central flows with visible reasoning, while skeleton-ing the supporting code without losing time.

Applied to Parking Lot

The implementation, beginning with the central flows.

Constructor

public class ParkingLot {
    private final List<Level> levels;
    private final SpotAllocationStrategy allocationStrategy;
    private final PricingStrategy pricingStrategy;
    private final PaymentProcessor paymentProcessor;
    private final Map<String, ParkingTicket> activeTickets;
    private final ReentrantLock lock = new ReentrantLock();
    
    public ParkingLot(
        List<Level> levels,
        SpotAllocationStrategy allocationStrategy,
        PricingStrategy pricingStrategy,
        PaymentProcessor paymentProcessor
    ) {
        if (levels == null || levels.isEmpty()) {
            throw new IllegalArgumentException("ParkingLot must have at least one level");
        }
        this.levels = List.copyOf(levels);
        this.allocationStrategy = Objects.requireNonNull(allocationStrategy);
        this.pricingStrategy = Objects.requireNonNull(pricingStrategy);
        this.paymentProcessor = Objects.requireNonNull(paymentProcessor);
        this.activeTickets = new HashMap<>();
    }
    
    public List<Level> getLevels() { return levels; }
}

Narration:

"Constructor validates non-empty levels. Uses List.copyOf to defensively copy - callers can't mutate the levels after construction. Null-checks all three strategies. Initializes the activeTickets map for tracking issued tickets between entry and exit."

enter - Central Operation 1

public Optional<ParkingTicket> enter(Vehicle vehicle) {
    Objects.requireNonNull(vehicle, "Vehicle cannot be null");
    
    lock.lock();
    try {
        Optional<ParkingSpot> spotOpt = allocationStrategy.allocate(this, vehicle);
        if (spotOpt.isEmpty()) {
            return Optional.empty();  // No compatible spot available
        }
        
        ParkingSpot spot = spotOpt.get();
        spot.occupy(vehicle);
        
        // Find the Level this spot belongs to and decrement its counter
        Level level = findLevelOf(spot);
        level.decrement(spot.getSpotType());
        
        // Create and store the ticket
        ParkingTicket ticket = new ParkingTicket(
            UUID.randomUUID().toString(),
            vehicle,
            spot,
            Instant.now()
        );
        activeTickets.put(ticket.getTicketId(), ticket);
        
        return Optional.of(ticket);
    } finally {
        lock.unlock();
    }
}

private Level findLevelOf(ParkingSpot spot) {
    for (Level level : levels) {
        if (level.getSpots().contains(spot)) {
            return level;
        }
    }
    throw new IllegalStateException("Spot not found in any level: " + spot.getId());
}

Narration:

"enter: null-check vehicle. Acquire lock with try-finally. Call allocationStrategy - it returns Optional<Spot>. If empty, return Optional.empty - no compatible spot, vehicle can't enter.

If a spot was found: mark it occupied with the vehicle. Find the level the spot belongs to - for now I'll use a linear scan; we could optimize by adding a back-reference from Spot to Level. Decrement the level's available counter for that spot type.

Create a ticket with a unique ID, the vehicle, the spot, and the entry time. Store it in activeTickets. Return Optional.of the ticket.

All under the lock - atomic. No interleaving with another gate's enter or exit."

exit - Central Operation 2

public ExitResult exit(String ticketId, PaymentMethod paymentMethod) {
    Objects.requireNonNull(ticketId, "Ticket ID cannot be null");
    Objects.requireNonNull(paymentMethod, "Payment method cannot be null");
    
    lock.lock();
    try {
        ParkingTicket ticket = activeTickets.get(ticketId);
        if (ticket == null) {
            return new ExitResult.Failure("Ticket not found: " + ticketId);
        }
        if (ticket.getStatus() != TicketStatus.ACTIVE) {
            return new ExitResult.Failure("Ticket is not active (status: " + ticket.getStatus() + ")");
        }
        
        // Calculate the fee
        Duration stayDuration = Duration.between(ticket.getEntryTime(), Instant.now());
        Money fee = pricingStrategy.calculateFee(ticket, stayDuration);
        
        // Attempt payment
        PaymentResult paymentResult = paymentProcessor.process(ticket, fee, paymentMethod);
        if (paymentResult instanceof PaymentResult.Failure failure) {
            return new ExitResult.Failure("Payment failed: " + failure.reason());
        }
        
        // Payment succeeded - transition ticket and release spot
        ticket.transitionTo(TicketStatus.PAID);
        
        ParkingSpot spot = ticket.getSpot();
        spot.release();
        
        Level level = findLevelOf(spot);
        level.increment(spot.getSpotType());
        
        ticket.transitionTo(TicketStatus.CLOSED);
        activeTickets.remove(ticketId);
        
        return new ExitResult.Success(ticket, fee);
    } finally {
        lock.unlock();
    }
}

Narration:

"exit: null-check arguments. Acquire lock.

Look up the ticket. If not found, return Failure. If not in ACTIVE state, return Failure with the current status - guards against double-exit, lost-ticket flows, etc.

Calculate the fee: stay duration between entry time and now; pricingStrategy.calculateFee handles the actual computation.

Attempt payment through the PaymentProcessor. Pattern-match on the result: Failure returns ExitResult.Failure with the reason.

On Success: transition the ticket to PAID. Release the spot. Increment the counter. Transition the ticket to CLOSED. Remove from activeTickets. Return ExitResult.Success.

All under the lock. The four-step transition - pay, release spot, increment counter, close ticket - is atomic."

enter Sequence Visualized

sequenceDiagram
    actor Gate
    participant Lot as ParkingLot
    participant Lock as Lock
    participant Strategy as AllocationStrategy
    participant Spot as ParkingSpot
    participant Level as Level
    participant Tickets as activeTickets
    
    Gate->>Lot: enter(vehicle)
    Lot->>Lock: lock()
    Lot->>Strategy: allocate(this, vehicle)
    Strategy-->>Lot: Optional<Spot>
    
    alt Spot found
        Lot->>Spot: occupy(vehicle)
        Lot->>Level: decrement(spotType)
        Lot->>Lot: create Ticket
        Lot->>Tickets: put(ticketId, ticket)
        Lot->>Lock: unlock()
        Lot-->>Gate: Optional.of(ticket)
    else No spot
        Lot->>Lock: unlock()
        Lot-->>Gate: Optional.empty()
    end

Supporting Classes

Vehicle hierarchy:

public abstract class Vehicle {
    private final String licensePlate;
    
    protected Vehicle(String licensePlate) {
        this.licensePlate = Objects.requireNonNull(licensePlate);
    }
    
    public abstract VehicleType vehicleType();
    public String getLicensePlate() { return licensePlate; }
}

public final class Car extends Vehicle {
    public Car(String licensePlate) { super(licensePlate); }
    @Override public VehicleType vehicleType() { return VehicleType.CAR; }
}

public final class Bike extends Vehicle {
    public Bike(String licensePlate) { super(licensePlate); }
    @Override public VehicleType vehicleType() { return VehicleType.BIKE; }
}

public final class Truck extends Vehicle {
    public Truck(String licensePlate) { super(licensePlate); }
    @Override public VehicleType vehicleType() { return VehicleType.TRUCK; }
}

public enum VehicleType { CAR, BIKE, TRUCK }

Narration: "Vehicle abstract with license plate. Three final concrete subtypes, each returning its VehicleType from the enum. Final because we're committing to a closed set; extensions go through composition, not subclassing."

ParkingSpot:

public class ParkingSpot {
    private final String id;
    private final SpotType spotType;
    private SpotStatus status;
    private Vehicle vehicleParked;
    
    public ParkingSpot(String id, SpotType spotType) {
        this.id = Objects.requireNonNull(id);
        this.spotType = Objects.requireNonNull(spotType);
        this.status = SpotStatus.AVAILABLE;
    }
    
    public boolean canFit(Vehicle vehicle) {
        if (status != SpotStatus.AVAILABLE) return false;
        return switch (spotType) {
            case COMPACT -> vehicle.vehicleType() == VehicleType.BIKE;
            case REGULAR -> vehicle.vehicleType() == VehicleType.BIKE 
                         || vehicle.vehicleType() == VehicleType.CAR;
            case LARGE -> true;  // any vehicle fits
            case HANDICAP -> vehicle.vehicleType() == VehicleType.CAR 
                          || vehicle.vehicleType() == VehicleType.BIKE;
        };
    }
    
    void occupy(Vehicle vehicle) {
        if (status != SpotStatus.AVAILABLE) {
            throw new IllegalStateException("Spot " + id + " is not available");
        }
        this.status = SpotStatus.OCCUPIED;
        this.vehicleParked = vehicle;
    }
    
    void release() {
        if (status != SpotStatus.OCCUPIED) {
            throw new IllegalStateException("Spot " + id + " is not occupied");
        }
        this.status = SpotStatus.AVAILABLE;
        this.vehicleParked = null;
    }
    
    // getters
    public String getId() { return id; }
    public SpotType getSpotType() { return spotType; }
    public SpotStatus getStatus() { return status; }
}

public enum SpotType { COMPACT, REGULAR, LARGE, HANDICAP }
public enum SpotStatus { AVAILABLE, OCCUPIED, OUT_OF_SERVICE }

Narration: "ParkingSpot with id, type, status, currently-parked vehicle. canFit uses a switch over SpotType - clear and exhaustive. occupy and release are package-private - only the Lot's flow calls them. Both validate state to enforce the invariant that occupy moves from AVAILABLE to OCCUPIED and release moves the reverse."

Level:

public class Level {
    private final int levelNumber;
    private final List<ParkingSpot> spots;
    private final Map<SpotType, Integer> availableCounts;
    
    public Level(int levelNumber, List<ParkingSpot> spots) {
        this.levelNumber = levelNumber;
        this.spots = List.copyOf(spots);
        this.availableCounts = computeInitialCounts(spots);
    }
    
    public Optional<ParkingSpot> findAvailable(Vehicle vehicle) {
        return spots.stream()
            .filter(spot -> spot.canFit(vehicle))
            .findFirst();
    }
    
    void decrement(SpotType type) {
        availableCounts.merge(type, -1, Integer::sum);
    }
    
    void increment(SpotType type) {
        availableCounts.merge(type, 1, Integer::sum);
    }
    
    public int getAvailableCount(SpotType type) {
        return availableCounts.getOrDefault(type, 0);
    }
    
    public List<ParkingSpot> getSpots() { return spots; }
    
    private Map<SpotType, Integer> computeInitialCounts(List<ParkingSpot> spots) {
        Map<SpotType, Integer> counts = new HashMap<>();
        for (ParkingSpot spot : spots) {
            counts.merge(spot.getSpotType(), 1, Integer::sum);
        }
        return counts;
    }
}

Narration: "Level holds spots and the per-type counters. findAvailable does a stream-based scan; for our scope, the spots-per-level count is small enough that O(n) is fine. decrement and increment are package-private - only the Lot's flow updates counters. getAvailableCount is the O(1) public query."

ParkingTicket:

public class ParkingTicket {
    private final String ticketId;
    private final Vehicle vehicle;
    private final ParkingSpot spot;
    private final Instant entryTime;
    private TicketStatus status;
    
    public ParkingTicket(String ticketId, Vehicle vehicle, ParkingSpot spot, Instant entryTime) {
        this.ticketId = ticketId;
        this.vehicle = vehicle;
        this.spot = spot;
        this.entryTime = entryTime;
        this.status = TicketStatus.ACTIVE;
    }
    
    public void transitionTo(TicketStatus next) {
        if (!isValidTransition(this.status, next)) {
            throw new IllegalStateException(
                "Invalid transition: " + this.status + " -> " + next);
        }
        this.status = next;
    }
    
    private boolean isValidTransition(TicketStatus from, TicketStatus to) {
        return switch (from) {
            case ACTIVE -> to == TicketStatus.PAID || to == TicketStatus.LOST;
            case PAID -> to == TicketStatus.CLOSED;
            case LOST -> to == TicketStatus.CLOSED;
            case CLOSED -> false;  // terminal state
        };
    }
    
    // getters
    public String getTicketId() { return ticketId; }
    public Vehicle getVehicle() { return vehicle; }
    public ParkingSpot getSpot() { return spot; }
    public Instant getEntryTime() { return entryTime; }
    public TicketStatus getStatus() { return status; }
}

public enum TicketStatus { ACTIVE, PAID, CLOSED, LOST }

Narration: "ParkingTicket with the four fields plus status. transitionTo validates the transition using a switch over the from state. CLOSED is terminal - no transitions out. Invalid transitions throw - defensive against state corruption."

Strategy Implementations

FirstAvailableCompatibleStrategy:

public class FirstAvailableCompatibleStrategy implements SpotAllocationStrategy {
    @Override
    public Optional<ParkingSpot> allocate(ParkingLot lot, Vehicle vehicle) {
        for (Level level : lot.getLevels()) {
            Optional<ParkingSpot> spot = level.findAvailable(vehicle);
            if (spot.isPresent()) {
                return spot;
            }
        }
        return Optional.empty();
    }
}

Narration: "FirstAvailableCompatibleStrategy iterates levels in order, calls findAvailable on each. Returns the first compatible spot. Alternatives like NearestToEntrance would walk levels in entrance-distance order with spots within each level sorted by distance - same pattern, different ordering."

HourlyByTypePricing:

public class HourlyByTypePricing implements PricingStrategy {
    private final Map<SpotType, Money> hourlyRates;
    private final Money dailyCap;
    
    public HourlyByTypePricing(Map<SpotType, Money> hourlyRates, Money dailyCap) {
        this.hourlyRates = Map.copyOf(hourlyRates);
        this.dailyCap = dailyCap;
    }
    
    @Override
    public Money calculateFee(ParkingTicket ticket, Duration stayDuration) {
        long hours = (long) Math.ceil(stayDuration.toMinutes() / 60.0);
        Money baseRate = hourlyRates.get(ticket.getSpot().getSpotType());
        Money fee = baseRate.multiply(hours);
        return fee.compareTo(dailyCap) > 0 ? dailyCap : fee;
    }
}

Narration: "HourlyByTypePricing computes hours as ceiling of stay duration in minutes divided by 60 - partial hour rounds up. Looks up the rate by spot type. Multiplies. Caps at the daily maximum. Returns the lesser of computed fee and cap."

Sealed ExitResult

public sealed interface ExitResult permits Success, Failure {
    record Success(ParkingTicket ticket, Money feeCharged) implements ExitResult {}
    record Failure(String reason) implements ExitResult {}
}

Narration: "Sealed result type. Two variants. Callers must handle both via pattern matching. Java records make the variants compact."

The Conversation

What implementation actually sounds like when narrated well versus when not.

Strong Candidate

Interviewer: "Design is committed. Implementation."

Candidate: "Starting with the constructor and entry flow.

Constructor takes levels and the three strategies. Validates non-empty levels. Null-checks strategies. Defensive-copies levels. Initializes the activeTickets map."

[Types constructor]

Candidate: "Now enter. Null-check vehicle, acquire lock with try-finally.

Inside: call allocationStrategy.allocate - returns Optional<Spot>. If empty, return Optional.empty - no compatible spot.

If a spot was found: spot.occupy(vehicle), find the Level the spot belongs to and decrement its counter, create a ParkingTicket with a unique ID and entry time, store in activeTickets, return Optional.of the ticket. All atomic under the lock."

[Types enter]

Candidate: "Now exit. Look up the ticket; if missing or not ACTIVE, return ExitResult.Failure. Otherwise calculate fee via pricingStrategy, attempt payment via paymentProcessor.

If payment fails, return Failure with the reason. If payment succeeds, transition the ticket to PAID, release the spot, increment the counter, transition to CLOSED, remove from activeTickets, return Success with the ticket and fee."

[Types exit]

Candidate: "Supporting classes briefly. Vehicle abstract with three final subtypes - Car, Bike, Truck - each returning their VehicleType from the enum. Final because we're committing to a closed set.

ParkingSpot with id, type, status, currently-parked vehicle. canFit uses a switch over SpotType - clear and exhaustive. occupy and release are package-private.

Level holds spots and per-type counters. findAvailable scans spots. decrement/increment are package-private for counter updates.

ParkingTicket with status and transitionTo. Valid transitions: ACTIVE → PAID or LOST, PAID → CLOSED, LOST → CLOSED. Invalid transitions throw.

FirstAvailableCompatibleStrategy iterates levels; finds first compatible spot. HourlyByTypePricing computes hours-ceiling times rate, caps at daily max. Both injected into ParkingLot."

[Types supporting code]

About 10 minutes. Central flows complete with narration. Supporting code skeletal but correct. The lock pattern reflexive. The Strategy injections visible in use.

Weak Candidate

Interviewer: "Design is committed. Implementation."

Candidate: [Types in silence for 90 seconds]

public class ParkingLot {
    List<Level> levels;
    
    public Ticket parkVehicle(Vehicle vehicle) {
        for (Level level : levels) {
            for (ParkingSpot spot : level.getSpots()) {
                if (spot.canFit(vehicle) && spot.isAvailable()) {
                    spot.setVehicle(vehicle);
                    return new Ticket(vehicle, spot);
                }
            }
        }
        return null;
    }
}

Interviewer: "What about the lock?"

Candidate: "Oh, right." [adds synchronized to the method]

Interviewer: "What about the strategy?"

Candidate: "I have the strategy interface but... let me use it." [refactors to call allocationStrategy.allocate]

Interviewer: "And the counter update?"

Candidate: "I forgot the counter." [adds level.decrement(spot.getSpotType())]

Interviewer: "What about activeTickets?"

Candidate: "Right." [adds activeTickets.put]

Interviewer: "Now exit?"

Candidate: [Begins writing exit, makes similar piecemeal corrections]

About 10 minutes. Both methods produced but with multiple interviewer-prompted corrections. The lock, the strategy injections, the counters, the active ticket tracking all added incrementally rather than from the start.

Strong vs Weak: Implementation Patterns

Common Mistakes

The parking lot implementation failures:

Skipping the lock pattern. Producing the operations without lock acquisition. Catastrophic for concurrent gates; surfaces immediately if probed.

Forgetting counter updates. Implementing occupy without decrement. Counter drifts; display becomes unreliable.

Forgetting activeTickets management. Issuing tickets without storing them. Exit can't find them later.

Hardcoded allocation logic. Bypassing the strategy and doing the iteration inline. Defeats the design.

Hardcoded pricing. Computing fee inline. Same.

Returning null instead of Optional. Modern Java idiom. Missing it signals language fluency gap.

No invariant validation in transitionTo. Allowing any state transition. Loses the lifecycle protection.

Skipping the supporting classes. Implementing only ParkingLot's central methods. The interviewer needs to see the entity classes too, even skeletally.

Warning: The most damaging implementation mistake on parking lot is forgetting to update the counters atomically with the spot status change. The counters drift silently; the display board shows wrong availability; the bug doesn't surface until the system is in production.

What "Good" Looks Like

Concrete signals I score positively:

Constructor validation and defensive copying. Non-null checks, defensive collection copies.

Lock pattern reflexive. ReentrantLock with try-finally on every public method.

Both enter and exit complete. With strategy calls, counter updates, lifecycle transitions, ticket management.

Supporting classes skeletal but correct. Vehicle hierarchy, ParkingSpot, Level, ParkingTicket, two Strategy implementations.

Optional and sealed ExitResult. Modern return types.

Validated transitions in ParkingTicket. Lifecycle enforcement.

Continuous narration. Each non-obvious choice articulated.

Time discipline. Central flows complete by minute 35-37; pivot to verification cleanly.

A candidate hitting seven or more of these signals has produced senior implementation work.

Try It

Exercise: Drill the implementation phase for parking lot:

1. Implement the constructor and enter from scratch. With validation, lock pattern, strategy call, counter update. Time it - should land in 4 minutes.

2. Implement exit. With ticket lookup, status validation, fee calculation, payment, lifecycle transitions, release. Another 3-4 minutes.

3. Drill the supporting classes. Vehicle hierarchy, ParkingSpot.canFit, ParkingTicket.transitionTo, Level counters. Until each is skeletonable in 90 seconds.

4. Practice the continuous narration. Record yourself. Listen for silent stretches over 30 seconds.

5. Drill the strategy implementations. FirstAvailableCompatible and HourlyByType. Until reflexive.

The next step (Step 5) covers edge cases and tests - verifying the design under specific scenarios and surfacing failure modes. The implementation here becomes the substrate.

Back to Low Level Design Interviews