Time Taken to Cross the Door

Time Taken to Cross the Door

What is this problem about?

Imagine a single door that can be used by only one person at a time, either to enter or to exit. You are given the arrival times of several people and whether they want to enter or exit. The door has specific rules to handle contention:

1. If the door wasn't used in the previous second, whoever wants to exit goes first.
2. If the door was used to exit in the previous second, the next person wanting to exit goes first.
3. If the door was used to enter in the previous second, the next person wanting to enter goes first. You need to return the time each person actually crosses the door.

Why is this asked in interviews?

This time taken to cross the door interview question is a hard-level simulation problem asked by companies like IMC, Amazon, and Google. it tests your ability to manage complex state transitions and multiple queues. It evaluates your attention to detail in following intricate priority rules and your ability to handle edge cases like multiple arrivals at the same time.

Algorithmic pattern used

This problem follows the Array, Queue, Simulation interview pattern.

1. Use two queues: enterQueue and exitQueue to store the indices of people who have arrived and are waiting.
2. Maintain a currentTime and a lastState (0 for enter, 1 for exit, or "unused").
3. While people are still waiting or arriving:
   • Add all people who arrive at or before currentTime to their respective queues.
   • If both queues are empty, jump currentTime to the next arrival time and reset lastState to "unused".
   • Determine who goes next based on the rules:
     • If lastState is "unused" or "exit", prioritize the exitQueue. If empty, use enterQueue.
     • If lastState is "enter", prioritize the enterQueue. If empty, use exitQueue.
   • Update the crossing time for the chosen person, increment currentTime, and update lastState.

Example explanation

Arrivals: Person 0 (Time 0, Exit), Person 1 (Time 0, Enter), Person 2 (Time 1, Exit).

1. Time 0: Both 0 and 1 arrive. State is "unused".
2. Rule: Priority to exit. Person 0 crosses. Time becomes 1. lastState = exit.
3. Time 1: Person 2 arrives. Now we have 1 (Enter) and 2 (Exit) waiting.
4. Rule: lastState was exit, so priority to exit. Person 2 crosses. Time becomes 2. lastState = exit.
5. Time 2: Only Person 1 is left. Person 1 crosses. Time becomes 3. lastState = enter. Result: [0, 2, 1].

Common mistakes candidates make

In "Time Taken to Cross the Door coding problem," the most common mistake is failing to handle the "jump" in time when the door is idle, leading to unnecessary iterations. Another error is incorrectly applying the priority rules, particularly when the door was unused in the previous second. Finally, managing the queues and the current time pointer can become confusing without a structured simulation loop.

Interview preparation tip

For complex simulations, always clearly define your state variables (like currentTime and lastState) and your priority logic before you start coding. Use descriptive variable names to keep track of the different queues. Practice with a small example to ensure your state transitions match the problem's requirements.