Katkat
Back

Compute Turnstile Crossing Times

GoogleSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage state in a queue-based simulation and implement complex tie-breaking logic using data structures like heaps or prioritized queues.

Problem: Turnstile Traffic Simulation

A single-lane turnstile allows people to pass through either entering or exiting. The turnstile has specific rules for processing traffic:

  1. At any second t, a person at the turnstile can either enter or exit.
  2. If multiple people are waiting to use the turnstile, the turnstile follows these priority rules:
    • If the turnstile was used at time t-1 (either entering or exiting), it prefers the same direction as the previous usage.
    • If the turnstile was idle at time t-1, or if only one type of request exists, the turnstile gives priority to the 'exit' direction.
  3. A person arrives at the turnstile at a specific time times[i]. If they arrive, they join a queue for their specific direction (0 for entering, 1 for exiting).

Given two arrays, times and direction, where times[i] is the arrival time of the i-th person and direction[i] is their requested direction, return an array results where results[i] is the time the i-th person passes through the turnstile.

Constraints

  • 1 <= times.length <= 10^5
  • times is sorted in non-decreasing order.
  • 0 <= times[i] <= 10^9
  • direction[i] is either 0 (enter) or 1 (exit).

Example 1

Input: times = [0, 0, 1, 5], direction = [0, 1, 1, 0] Output: [2, 0, 1, 5]

Example 2

Input: times = [0, 1, 1, 3, 3], direction = [0, 1, 0, 0, 1] Output: [0, 1, 2, 3, 4]

Function Signature

def get_turnstile_times(times: list[int], direction: list[int]) -> list[int]:

Hints

Hint 1

Use two separate queues or min-heaps to track people waiting to enter and people waiting to exit, sorted by their original index to maintain order.

Hint 2

Maintain a variable to track the 'previous state' (was the last person an enterer, exiter, or was the turnstile idle?).

Hint 3

Simulate the process time step by time step, but jump ahead to the next arrival time if the queues are empty to avoid an O(max_time) complexity.

Follow-up questions

  • How would you modify your solution if the turnstile took 0.5 seconds to process each person instead of 1?
  • If the turnstile had a 'cooldown' period after 10 consecutive people in the same direction, how would you incorporate that into the state machine?
  • What is the time and space complexity of your solution, and can you explain why using heaps/queues is necessary compared to a simple loop?