How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute Turnstile Crossing Times | Google Coding Question

Compute Turnstile Crossing Times

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given `n` people waiting to use a single-door turnstile. Each person has: - `time[i]`: the time when person `i` arrives at the turnstile. - `direction[i]`: the direction person `i` wants to go, where `0` means enter and `1` means exit. The arrays are ordered by nondecreasing arrival time, and each index `i` represents a distinct person. At most one person can use the turnstile at each integer time unit. When multiple people are waiting at the same time, the turnstile chooses who goes next using these rules: 1. If the turnstile was used in the previous time unit, then people going in the same direction as the previous user have priority. 2. If the turnstile was not used in the previous time unit, then exiting people have priority. 3. If multiple people with the same priority are waiting, the person with the smaller index goes first. Return an array `answer` of length `n`, where `answer[i]` is the time when person `i` uses the turnstile. Your solution should run in `O(n)` time by jumping the current time forward when no one is waiting, instead of simulating every time unit between the minimum and maximum arrival times.

Quick Answer: This question evaluates proficiency in queue simulation, event-driven scheduling, and handling priority and tie-breaking rules while achieving linear time complexity.

You are given n people waiting to use a single-door turnstile. Person i arrives at time[i] and wants to use the turnstile in direction[i], where 0 means enter and 1 means exit. The arrays are ordered by nondecreasing arrival time, and each index represents a distinct person. At each integer time unit, at most one person can use the turnstile. A person is considered waiting if they have arrived and have not used the turnstile yet. When multiple people are waiting at the same time, choose who goes next using these rules: 1. If the turnstile was used in the previous time unit, then people going in the same direction as the previous user have priority. 2. If the turnstile was not used in the previous time unit, then exiting people have priority. 3. If multiple waiting people have the same priority, the person with the smaller index goes first. Return an array answer of length n, where answer[i] is the time when person i uses the turnstile. Your solution should run in O(n) time by jumping the current time forward whenever nobody is waiting, instead of simulating every time unit across idle gaps.

Constraints

0 <= n == len(time) == len(direction) <= 2 * 10^5
0 <= time[i] <= 10^9
direction[i] is either 0 or 1
time is sorted in nondecreasing order

Examples

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

Expected Output: [2,0,1,5]

Explanation: At t=0 the turnstile was idle, so exiting person 1 goes first. At t=1 person 2 also wants to exit and keeps priority. Person 0 enters at t=2, and after an idle gap person 3 enters at t=5.

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

Expected Output: [1,0,2]

Explanation: All arrive at t=0. Because the turnstile was idle, exiting person 1 goes first at t=0. Then persons 0 and 2 enter in increasing index order.

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

Expected Output: [2,3,10]

Explanation: At t=2 person 0 exits first, then person 1 enters at t=3. No one waits after that, so time jumps directly to t=10 and person 2 exits.

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

Expected Output: [2,1,3,4]

Explanation: Person 1 exits at t=1. Then person 0 enters at t=2. At t=3 both person 2 (enter) and person 3 (exit) are waiting, and enter has priority because the previous use was also enter.

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

Expected Output: [0,2,1,3,4]

Explanation: Person 0 exits at t=0, person 2 exits at t=1, then only entering people remain. Among entering people, smaller indices go first: person 1, then 3, then 4.

Input: ([0], [0])

Expected Output: [0]

Explanation: Only one person is present, so they use the turnstile immediately at t=0.

Input: ([], [])

Expected Output: []

Explanation: No people are waiting, so the result is an empty list.

Hints

Maintain two queues of waiting people: one for enter and one for exit. Because indices increase naturally, queue order also handles the smaller-index tie break.
When both queues are empty, jump the current time directly to the next person's arrival time and treat the previous second as unused.

Quick Overview

This question evaluates proficiency in queue simulation, event-driven scheduling, and handling priority and tie-breaking rules while achieving linear time complexity.