Here is solutions for Police Parking Garage.

1. Understand the problem

• You are managing a police garage with these rules:

  • Cars are parked in a stack-like system (last checked in blocks others).

  • Checkout rule: The last checked-in car is always checked out first (LIFO).

  • Return rule: All cars are checked out for the same fixed time, so:

    • Cars are checked back in in the same order they were checked out (FIFO).

  • A variable number of cars are used each day.

  • At the end of the day, all cars are checked in.

  • getNextCars(n) must predict the next n cars that will be checked out the next day, assuming all cars eventually return.

So operationally:

• Checkout → Stack (LIFO)

• Check-in → Queue order from earlier checkouts

• Forecasting requires simulating future LIFO pops after all returns

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. What if cars could be checked out whenever, for however long, but the duration of the usage must be specified when checked out? so checkoutCar now takes in int hours

2. Would need to use a min heap where the key is the return time

3. How would your answer change if there were different vehicle types?

4. Maps of vehicle type to queue/stack

1. Candidates asks good questions to clarify constraints

2. Are there different vehicle types?

• To start, we can assume only 1 type

1. Can we assume a realistic number of cars (don’t need to worry about a million cars)?

• Yes

1. Can an officer end their shift early?

• No

1. What happens when getNextCars is run in the middle of cars being checked out?

• getNextCars always assumes all cars are checked back in before any more are checked out, since that is when they do their maintenance

Edge cases to consider

• No cars checked out

• All cars checked out

• n > number of cars

• n == 0

• n < 0

3. Explore examples.

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Solution 1 — Naive (Full Simulation Each Time) - Time O(N)

• Maintain:

  • A stack for available cars.

  • A queue for checked-out cars.

For getNextCars(n):

- Copy both structures.

- Simulate all remaining check-ins.

- Then pop n times from copied stack.

• Time O(N) per query, extra memory copy

4.2. Solution 2 — Optimized Simulation (Still O(N), Cleaner)

• Same idea but:

  • Use Deque for stack and queue.

  • Avoid modifying original structures.

  • Copy references into temporary deques.

• This is optimal because forecasting must examine ordering of all cars anyway.

• Time: O(N + n).

• Space: O(N)

5. Implement solutions.

from collections import deque
from typing import List

class PoliceGarage:
    def __init__(self, carIds: List[str]):
        # Stack of available cars (right = top)
        self.stack = deque(carIds)

        # Queue of checked-out cars (order they will return)
        self.checked_out = deque()

    def checkoutCar(self) -> str:
        if not self.stack:
            raise Exception("No cars available for checkout")

        car = self.stack.pop()
        self.checked_out.append(car)
        return car

    def checkInCar(self) -> str:
        if not self.checked_out:
            raise Exception("No cars to check in")

        # The first car check out will the first check-in
        car = self.checked_out.popleft()
        self.stack.append(car)
        return car

    def getNextCars(self, n: int) -> List[str]:
        # --- Create copies so real state is untouched ---
        temp_stack = deque(self.stack)
        temp_queue = deque(self.checked_out)

        # --- Simulate end-of-day: all checked-out cars return ---
        while temp_queue:
            temp_stack.append(temp_queue.popleft())

        # --- Predict next n checkouts (LIFO) ---
        result = []
        for _ in range(min(n, len(temp_stack))):
            result.append(temp_stack.pop())

        return result

6. Dry run testcases.