Quick Overview

A coding exercise that simulates a parking lot with fixed numbers of big, medium and small spaces, where each arriving car either takes a free space of its own size or is turned away. It tests careful state tracking and returning exactly one result per arrival, in arrival order.

Parking Lot With Big, Medium and Small Spaces: Accept or Reject Each Arriving Car

Company: Microsoft

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

A parking lot has three kinds of spaces, big, medium and small, with a fixed number of each. Cars arrive one at a time, and each car has a type: `1` for big, `2` for medium and `3` for small. A car can park only in a space of its own kind. If such a space is free, the car parks and the space stays occupied for the rest of the sequence; otherwise the car is turned away and nothing changes. Given the number of spaces of each kind and the sequence of arriving car types, return whether each car was able to park. The report describes this only as an easy parking-lot design problem. It is usually posed as a class whose constructor takes the three capacities and whose method is called once per arriving car; this console tests the same behavior through a single function that replays the arrivals in order. ### Function Signature ```python def park_cars(big: int, medium: int, small: int, car_types: list[int]) -> list[bool]: ``` ### Rules - `big`, `medium` and `small` are the numbers of free spaces of each kind before the first car arrives. - Process `car_types` from first to last. For a car of type `t`, if at least one space of kind `t` is free, the car parks, one space of that kind becomes occupied, and the answer for that car is `True`; otherwise the answer is `False` and no space changes. - A car never uses a space of a different kind, larger or smaller, and parked cars never leave. - Return a list with exactly one boolean per car, in arrival order. ### Constraints - `0 <= big, medium, small <= 1000` - `1 <= len(car_types) <= 10^4` - Every element of `car_types` is `1`, `2` or `3`. ### Examples **Example 1** ```text Input: big = 2, medium = 0, small = 1, car_types = [3, 1, 2, 3, 1, 1] Output: [True, True, False, False, True, False] ``` The first small car takes the only small space, so the second small car is turned away. The lot has no medium spaces, so the medium car is turned away. The first two big cars take the two big spaces, and the third big car is turned away. **Example 2** ```text Input: big = 1, medium = 0, small = 0, car_types = [3, 2, 1] Output: [False, False, True] ``` The small and medium cars are turned away even though a big space is free, because a car parks only in a space of its own kind. The big car then takes the big space.

Overview: A coding exercise that simulates a parking lot with fixed numbers of big, medium and small spaces, where each arriving car either takes a free space of its own size or is turned away. It tests careful state tracking and returning exactly one result per arrival, in arrival order.

A parking lot has three kinds of spaces, big, medium and small, with a fixed number of each. Cars arrive one at a time, and each car has a type: `1` for big, `2` for medium and `3` for small. A car can park only in a space of its own kind. If such a space is free, the car parks and the space stays occupied for the rest of the sequence; otherwise the car is turned away and nothing changes. Given the number of free spaces of each kind and the sequence of arriving car types, implement `park_cars(big, medium, small, car_types)`, which replays the arrivals in order and returns whether each car was able to park. ### Rules - `big`, `medium` and `small` are the numbers of free spaces of each kind before the first car arrives. - Process `car_types` from first to last. For a car of type `t`, if at least one space of kind `t` is free, the car parks, one space of that kind becomes occupied, and the answer for that car is `True`; otherwise the answer is `False` and no space changes. - A car never uses a space of a different kind, larger or smaller, and parked cars never leave. - Return a list with exactly one boolean per car, in arrival order. ### Constraints - `0 <= big, medium, small <= 1000` - `1 <= len(car_types) <= 10^4` - Every element of `car_types` is `1`, `2` or `3`. No value can exceed 2^31 - 1, so 32-bit integers suffice in every language. ### Example 1 ```text Input: big = 2, medium = 0, small = 1, car_types = [3, 1, 2, 3, 1, 1] Output: [True, True, False, False, True, False] ``` The first small car takes the only small space, so the second small car is turned away. The lot has no medium spaces, so the medium car is turned away. The first two big cars take the two big spaces, and the third big car is turned away. ### Example 2 ```text Input: big = 1, medium = 0, small = 0, car_types = [3, 2, 1] Output: [False, False, True] ``` The small and medium cars are turned away even though a big space is free, because a car parks only in a space of its own kind. The big car then takes the big space.

Constraints

  • 0 <= big, medium, small <= 1000
  • 1 <= len(car_types) <= 10^4
  • Every element of car_types is 1, 2 or 3.

Examples

Input: (2, 0, 1, [3, 1, 2, 3, 1, 1])

Expected Output: [True, True, False, False, True, False]

Explanation: Source Example 1: the second small car, the medium car (no medium spaces) and the third big car are turned away.

Input: (1, 0, 0, [3, 2, 1])

Expected Output: [False, False, True]

Explanation: Source Example 2: the small and medium cars never take the free big space; the big car then parks.

Hints

  1. Spaces of the same kind are interchangeable and parked cars never leave. What is the least you need to remember about each kind to decide whether the next car of that kind can park?
  2. A turned-away car changes nothing, so only cars that actually park affect later answers, and only for their own kind.
  3. Double-check the mapping from type numbers to kinds before indexing anything: 1 is big, 2 is medium, 3 is small.

Loading coding console...

Show the approach

Approach

Keep one counter of free spaces per kind, indexed by car type (1 = big, 2 = medium, 3 = small) and initialised to big, medium and small. Replay the arrivals in order: for a car of type t, if the counter for t is positive, decrement it and record True; otherwise record False and leave every counter unchanged. Invariant: before each car, the counter for kind k equals the initial number of kind-k spaces minus the number of earlier kind-k cars that parked, and it never drops below 0. Correctness: spaces of one kind are interchangeable and parked cars never leave, so whether a car can park depends only on how many spaces of its own kind are still free, which is exactly that counter; a refused car changes nothing, matching the rule that no space changes. Edge cases: a capacity of 0 refuses every car of that kind from the start; once a type's arrivals exceed its capacity, every later car of that type is refused while other kinds keep accepting cars; a car never falls back to a free space of another kind; the result always holds exactly one boolean per car in arrival order.

Time complexity:
O(n), where n = len(car_types)
Space complexity:
O(n) for the returned list; O(1) extra