Cracking The Coding Interview Together – Problem 7.4: Parking Lot

We have all been there. You are sitting in an interview, and the interviewer throws out a deceptively simple prompt: "Design a parking lot." Your mind immediately starts racing. Do we need to handle credit card payments? What about license plate recognition cameras? Should we track the exact GPS coordinates of every Tesla? Before you know it, you have built a massive, over-engineered distributed system in your head, but you haven't actually written a single line of clean, object-oriented code.

The "Parking Lot" is a classic Object-Oriented Design (OOD) problem because it tests your ability to manage complexity, establish clear boundaries, and apply core design principles like encapsulation, inheritance, and polymorphism. Today, we are going to tackle this challenge together. We will cut through the ambiguity, design a robust domain model, and write production-ready Java code that will impress even the most critical system architects. Let's dive in.

Problem Statement

Our goal is to design a parking lot using object-oriented principles. To make this exercise concrete and actionable, we must satisfy the following operational requirements:

• The parking lot has multiple levels.
• Each level has a designated number of parking spots.
• The parking lot must accommodate multiple vehicle types: Motorcycles, Cars, and Buses.
• Parking spots come in different sizes: Small (for motorcycles), Medium (for compact cars), and Large (for buses or large vehicles).
• A vehicle can only park in a spot that is equal to or larger than its own size (e.g., a car can park in a Medium or Large spot, but not a Small spot).
• The system must be able to dynamically allocate an available spot to an incoming vehicle, free up the spot when the vehicle leaves, and track the overall capacity of the lot.

Analyze the Problem Together

When we look at this problem, the core conflict lies in how we map Vehicles to ParkingSpots. A naive approach might be to treat all spots as a flat list and use a series of nested if-else statements to check sizes. But as senior engineers, we know that this violates the Open/Closed Principle (OCP). If we introduce a new vehicle type tomorrow (like an Electric Vehicle requiring a charging spot), our entire allocation logic would break.

Let's compare a flat-list approach with a structured, hierarchical design:

By grouping spots within Levels, we delegate the responsibility of finding a spot to the individual level. The ParkingLot class itself acts as a high-level orchestrator. This hierarchical structure keeps our classes small, focused, and highly cohesive.

Questions for the Interviewer

Before we write a single line of code, we must clarify the scope. In a real interview, asking these questions demonstrates that you think like a pragmatist, not just a coder:

1. "Do we need to handle payment processing, ticketing, and hourly rates?"
   Answer: No, let's focus purely on the allocation and deallocation of parking spots for now. Keep the core domain clean.
2. "Can a vehicle occupy multiple spots? For example, does a large bus take up 5 consecutive compact spots?"
   Answer: To keep our initial design clean and robust, let's assume 1 vehicle maps to exactly 1 spot of compatible size. We can discuss multi-spot allocation as an extension.
3. "Is this system running in a multi-threaded environment?"
   Answer: Yes, multiple entry gates could attempt to park cars simultaneously. We should ensure our design is thread-safe.

Think About the Solution

Let's map out our high-level architecture. We will use the following core components:

• VehicleSize (Enum): Defines MOTORCYCLE, COMPACT, and LARGE.
• Vehicle (Abstract Class): Base class containing a license plate and a size. Concrete implementations will be Motorcycle, Car, and Bus.
• ParkingSpot (Class): Represents an individual spot. It knows its size, whether it is occupied, and which vehicle is currently parked in it.
• Level (Class): Represents a single floor of the parking lot. It manages its own collection of spots and handles the logic of finding and freeing spots on that floor.
• ParkingLot (Class): A singleton class that manages all levels. It serves as the entry point for parking and unparking operations.

To handle edge cases, we must ensure that we gracefully handle scenarios where the lot is completely full, or when a user attempts to unpark a vehicle that does not exist in our system.

Write Code and Explain

Let's implement this design in Java. We will write clean, production-ready code with robust encapsulation and thread safety.

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.locks.ReentrantLock;

// 1. Define Vehicle Sizes
enum VehicleSize {
    MOTORCYCLE,
    COMPACT,
    LARGE
}

// 2. Abstract Vehicle Class
abstract class Vehicle {
    protected String licensePlate;
    protected VehicleSize size;

    public Vehicle(String licensePlate, VehicleSize size) {
        this.licensePlate = licensePlate;
        this.size = size;
    }

    public VehicleSize getSize() {
        return this.size;
    }

    public String getLicensePlate() {
        return this.licensePlate;
    }
}

// Concrete Vehicle Implementations
class Motorcycle extends Vehicle {
    public Motorcycle(String licensePlate) {
        super(licensePlate, VehicleSize.MOTORCYCLE);
    }
}

class Car extends Vehicle {
    public Car(String licensePlate) {
        super(licensePlate, VehicleSize.COMPACT);
    }
}

class Bus extends Vehicle {
    public Bus(String licensePlate) {
        super(licensePlate, VehicleSize.LARGE);
    }
}

// 3. Parking Spot Class
class ParkingSpot {
    private final int spotNumber;
    private final VehicleSize spotSize;
    private Vehicle parkedVehicle;

    public ParkingSpot(int spotNumber, VehicleSize spotSize) {
        this.spotNumber = spotNumber;
        this.spotSize = spotSize;
    }

    public boolean isAvailable() {
        return parkedVehicle == null;
    } 

    public boolean canFitVehicle(Vehicle vehicle) {
        // A vehicle can fit if the spot size is greater than or equal to the vehicle size
        return isAvailable() && this.spotSize.ordinal() >= vehicle.getSize().ordinal();
    }

    public synchronized boolean park(Vehicle vehicle) {
        if (!canFitVehicle(vehicle)) {
            return false;
        }
        this.parkedVehicle = vehicle;
        return true;
    }

    public synchronized void unpark() {
        this.parkedVehicle = null;
    }

    public Vehicle getParkedVehicle() {
        return this.parkedVehicle;
    }

    public int getSpotNumber() {
        return this.spotNumber;
    }
}

// 4. Level Class
class Level {
    private final int floorNumber;
    private final List<ParkingSpot> spots;
    private int availableSpotsCount;
    private final ReentrantLock lock = new ReentrantLock();

    public Level(int floorNumber, int numSpots) {
        this.floorNumber = floorNumber;
        this.spots = new ArrayList<>(numSpots);
        this.availableSpotsCount = numSpots;

        // Distribute spot sizes evenly for demonstration purposes
        for (int i = 0; i < numSpots; i++) {
            VehicleSize size;
            if (i < numSpots / 3) {
                size = VehicleSize.MOTORCYCLE;
            } else if (i < (2 * numSpots) / 3) {
                size = VehicleSize.COMPACT;
            } else {
                size = VehicleSize.LARGE;
            }
            spots.add(new ParkingSpot(i, size));
        }
    }

    public boolean parkVehicle(Vehicle vehicle) {
        lock.lock();
        try {
            if (availableSpotsCount == 0) return false;

            for (ParkingSpot spot : spots) {
                if (spot.canFitVehicle(vehicle)) {
                    if (spot.park(vehicle)) {
                        availableSpotsCount--;
                        return true;
                    }
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public boolean unparkVehicle(Vehicle vehicle) {
        lock.lock();
        try {
            for (ParkingSpot spot : spots) {
                if (!spot.isAvailable() && spot.getParkedVehicle().equals(vehicle)) {
                    spot.unpark();
                    availableSpotsCount++;
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public int getAvailableSpotsCount() {
        return this.availableSpotsCount;
    }
}

// 5. ParkingLot (Singleton Orchestrator)
class ParkingLot {
    private static ParkingLot instance = null;
    private final List<Level> levels;
    private final ReentrantLock globalLock = new ReentrantLock();

    private ParkingLot(List<Level> levels) {
        this.levels = levels;
    }

    public static synchronized ParkingLot getInstance(List<Level> levels) {
        if (instance == null) {
            instance = new ParkingLot(levels);
        }
        return instance;
    }

    public boolean parkVehicle(Vehicle vehicle) {
        for (Level level : levels) {
            if (level.parkVehicle(vehicle)) {
                System.out.println("Successfully parked vehicle " + vehicle.getLicensePlate());
                return true;
            }
        }
        System.out.println("Failed to park vehicle " + vehicle.getLicensePlate() + ": No available spots.");
        return false;
    }

    public boolean unparkVehicle(Vehicle vehicle) {
        for (Level level : levels) {
            if (level.unparkVehicle(vehicle)) {
                System.out.println("Successfully unparked vehicle " + vehicle.getLicensePlate());
                return true;
            }
        }
        System.out.println("Vehicle " + vehicle.getLicensePlate() + " not found in the parking lot.");
        return false;
    }
}

Code Walkthrough

Let's trace how this works. When a vehicle arrives, we call ParkingLot.parkVehicle(vehicle). The ParkingLot iterates through its Levels. Each level uses a ReentrantLock to ensure thread safety. This prevents race conditions where two threads try to claim the same spot at the exact same millisecond.

Inside the Level, we iterate through the spots and check compatibility using spot.canFitVehicle(vehicle). We leverage Java's Enum.ordinal() to compare sizes cleanly (e.g., LARGE (2) >= COMPACT (1) is true, allowing a car to park in a large spot if no compact spots are free).

Time & Space Complexity

Let's analyze the efficiency of our design:

• Time Complexity:
  • parkVehicle(): O(L * S), where L is the number of levels and S is the number of spots per level. In the worst case, we scan all spots. We can optimize this to O(1) by maintaining separate queues of available spots for each size category.
  • unparkVehicle(): O(L * S) in our current implementation. We can easily optimize this to O(1) by keeping a Map<Vehicle, ParkingSpot> in the ParkingLot class to look up the spot instantly.
• Space Complexity: O(L * S) to store the state of all parking spots in memory. This is highly efficient and scales linearly with the physical capacity of the lot.

Why This Problem Matters (The Senior Perspective)

In a production environment, this design serves as a foundation for real-world enterprise architectures. Here is how a senior engineer would scale this system:

• Concurrency & Distributed Systems: In a real-world multi-gate parking garage, a single in-memory lock won't suffice if our application is scaled horizontally across multiple servers. We would replace our local ReentrantLock with a distributed lock manager like Redis (Redlock) to prevent double-booking across different API nodes.
• Persistence: Instead of keeping everything in memory, we would map these classes to a relational database using an ORM like Hibernate. The ParkingSpot would be a database row, and we would use pessimistic locking (SELECT ... FOR UPDATE) to handle concurrent reservation requests safely.
• Design Patterns: We utilized the Singleton Pattern for the ParkingLot orchestrator. We could also introduce a Factory Pattern to instantiate vehicles based on incoming license plate scans or ticket requests.

Final Thoughts

Designing a parking lot isn't about writing the most complex algorithm; it's about demonstrating clean modeling, solid encapsulation, and an understanding of real-world constraints. By breaking down the problem into logical layers (Lot -> Level -> Spot), we built a solution that is easy to read, test, and extend.

What optimizations would you add next? Would you implement the Map lookup for O(1) unparking, or perhaps add an electric vehicle charging spot subclass? Let us know in the comments below!

Happy coding, and we will see you in the next system design breakdown!