Quick Overview

A coding question about cars arriving one at a time on a one-way street, each trying its preferred parking spot first and moving only forward when that spot is taken. You decide whether every car manages to park, which tests careful rule-following and efficient handling of spot occupancy for large inputs.

Decide whether every car can park given preferred spots and forward-only overflow

Company: Mercor

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A one-way street has `n` parking spots in a row, numbered `0` to `n - 1` in the direction of travel. Cars arrive one at a time, in the order given by `preferences`, and car `i` prefers spot `preferences[i]`. Each car tries its preferred spot first and can only move forward from there. Decide whether every car manages to park. ### Function Signature ```python def can_all_park(n: int, preferences: list[int]) -> bool: ``` ### Rules - All spots start empty, and a parked car never moves. - An arriving car drives to its preferred spot. If that spot is empty, the car parks there. - Otherwise, the car continues forward and parks in the first empty spot with a larger index. - A car never moves backward. If there is no empty spot at or after its preferred spot, the car fails to park. - Return `True` if every car parks and `False` if at least one car fails. An empty `preferences` list returns `True`. ### Constraints - `1 <= n <= 10^5` - `0 <= len(preferences) <= 10^5` - `0 <= preferences[i] <= n - 1` - All values fit in a 32-bit signed integer. ### Examples **Example 1** ```text Input: n = 3, preferences = [0, 0, 1] Output: True ``` Car 0 parks in spot 0. Car 1 finds spot 0 taken and parks in spot 1. Car 2 finds spot 1 taken and parks in spot 2. **Example 2** ```text Input: n = 3, preferences = [1, 1, 2] Output: False ``` Car 0 parks in spot 1, and car 1 moves forward to spot 2. Car 2 finds spot 2 taken and has no spot after it, so it fails even though spot 0 is empty. **Example 3** ```text Input: n = 4, preferences = [2, 0] Output: True ``` Car 0 parks in spot 2 and car 1 parks in spot 0; spots 1 and 3 stay empty.

Overview: A coding question about cars arriving one at a time on a one-way street, each trying its preferred parking spot first and moving only forward when that spot is taken. You decide whether every car manages to park, which tests careful rule-following and efficient handling of spot occupancy for large inputs.

Read the full Mercor Machine Learning Engineer interview experience this question came from

A one-way street has `n` parking spots in a row, numbered `0` to `n - 1` in the direction of travel. Cars arrive one at a time, in the order given by the list `preferences`, and car `i` prefers spot `preferences[i]`. Each car tries its preferred spot first and can only move forward from there. Decide whether every car manages to park. Implement `can_all_park(n, preferences)`. **Rules** - All spots start empty, and a parked car never moves. - An arriving car drives to its preferred spot. If that spot is empty, the car parks there. - Otherwise, the car continues forward and parks in the first empty spot with a larger index. - A car never moves backward. If there is no empty spot at or after its preferred spot, the car fails to park. **Output** Return `True` (`true` in JavaScript, Java and C++) if every car parks, and `False` (`false`) if at least one car fails. An empty `preferences` list returns `True`. **Constraints** - `1 <= n <= 10^5` - `0 <= len(preferences) <= 10^5` - `0 <= preferences[i] <= n - 1` - All values fit in a 32-bit signed integer; no value can exceed 2^31 - 1, so `int` is sufficient in Java and C++. **Example 1** ``` Input: n = 3, preferences = [0, 0, 1] Output: True ``` Car 0 parks in spot 0. Car 1 finds spot 0 taken and parks in spot 1. Car 2 finds spot 1 taken and parks in spot 2. **Example 2** ``` Input: n = 3, preferences = [1, 1, 2] Output: False ``` Car 0 parks in spot 1, and car 1 moves forward to spot 2. Car 2 finds spot 2 taken and has no spot after it, so it fails even though spot 0 is empty.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(preferences) <= 10^5
  • 0 <= preferences[i] <= n - 1
  • All values fit in a 32-bit signed integer.

Examples

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

Expected Output: True

Explanation: Source Example 1: collisions push cars 1 and 2 forward into spots 1 and 2.

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

Expected Output: False

Explanation: Source Example 2: the last car finds spot 2 taken and cannot go back to empty spot 0.

Hints

  1. A car never moves backward, so a car that prefers spot p can only ever end up in one of the spots p through n - 1.
  2. Example 2 shows a car can fail even though a lower-numbered spot is still empty, so having no more cars than spots is not enough on its own.
  3. With up to 10^5 cars, walking forward one spot at a time for every car can get slow when many cars prefer nearby spots.

Loading coding console...

Show the approach

Approach

Let m = len(preferences). Count how many cars prefer each spot, then scan the spots from n - 1 down to 0 while keeping a running total s(j) = number of cars whose preferred spot is at least j. Return False as soon as s(j) > n - j for some j; if the scan finishes, return True.

Necessity: a car never moves backward, so a car preferring spot p can only park in spots p..n-1. All s(j) cars preferring a spot >= j must therefore fit into the n - j spots j..n-1; if s(j) > n - j, at least one of them fails.

Edge cases: an empty preferences list gives s(j) = 0 everywhere and returns True; more cars than spots gives s(0) = m > n and returns False; two cars preferring n - 1 give s(n - 1) = 2 > 1 and return False; a car can fail while lower spots are empty (Example 2), which the check captures because s(j) never counts cars preferring spots below j. Every running total is at most 10^5, so 32-bit integers suffice in every language.

Time complexity:
O(n + m)
Space complexity:
O(n)