Validated Vehicle Exit Sequence — Problem Statement & Solution Guide

StackMediumMixed

TimeO(n)

SpaceO(k)

Problem Description

A parking facility processes a chronological stream of vehicle access events. Each event is represented as a pair [id, action], where id is a unique integer identifier for a vehicle and action is a string, either "entry" or "exit". The facility enforces a strict First-In-First-Out (FIFO) policy for departures: a vehicle is permitted to exit only if it is currently inside the facility and is the earliest vehicle that entered among all currently present vehicles. If an "exit" event is encountered for a vehicle that is not the next in the FIFO queue, the event is ignored (treated as invalid), and the vehicle remains inside. If an "exit" event is encountered for a vehicle that has not yet entered, the event is also ignored. Your task is to simulate this process and return the sequence of vehicle IDs that successfully exit the facility in the order they depart.

Input: A list of events, where each event is a list containing an integer ID and a string action.

Output: A list of integers representing the IDs of vehicles that successfully exit, in the order of their departure.

DSA Pattern Breakdown

"Validated Vehicle Exit Sequence"

medium

WHY DOES IT MATTER?

Queue validation appears in many systems that enforce ordering guarantees, such as transaction logs, message brokers, and rate‑limited APIs. Mastery of this pattern demonstrates a candidate's ability to translate abstract ordering constraints into concrete data‑structure operations.

OPTIMIZATION CHALLENGE

The key insight is recognizing that FIFO constraints map directly to a queue's head‑tail contract, allowing constant‑time checks for each exit instead of scanning the entire history.

REAL-WORLD CONNECTION

Think of a toll booth lane where cars must leave in the same order they entered; any car trying to cut the line triggers an alarm. Distributed systems like Kafka also enforce FIFO per partition, and validating consumer offsets follows the same principle.

During an interview, implement the queue with a simple array and two pointers (head, tail) or use a built‑in deque. Focus on edge‑case handling—duplicate IDs, premature exits, and leftover vehicles at the end—to showcase robustness.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(k)

Core Theory — Why This Approach?

The problem models a classic queue validation scenario where a stream of entry and exit events must obey First‑In‑First‑Out semantics. The naive solution would scan the list and, for each exit, search the entire history to confirm that the vehicle entered earlier and that no other vehicle entered after it and is still waiting—this leads to O(n²) time in the worst case. The optimal paradigm leverages the intrinsic properties of a queue: when a vehicle enters, it is appended to the tail; when it exits, it must match the head of the queue. By maintaining a real‑time queue of currently parked vehicles, each event can be processed in O(1) amortized time, yielding an overall linear solution. This approach also naturally detects illegal exits (e.g., exiting a vehicle that never entered or exiting out of order) and ensures the final state is consistent.

Interview Questions on This Problem

Q1How would you modify the algorithm to support a "priority exit" rule where certain vehicles (e.g., emergency services) can bypass the FIFO order?

Introduce a secondary priority queue (or a deque) for privileged IDs. On entry, push regular vehicles to the main queue and privileged ones to the front of the priority queue. On exit, first check the priority queue; if it’s non‑empty, the exiting ID must match its front, otherwise fall back to the regular queue. This preserves O(1) operations while handling two ordered streams.

Q2What is the time and space complexity if the input stream is extremely large and cannot fit into memory all at once?

Process the stream in a single pass using a sliding window: keep only the current queue of active vehicles, which at most equals the maximum concurrent occupancy. Thus memory usage stays O(k) where k is the peak number of vehicles, independent of total events n, and time remains O(n) as each event is handled once.

Q3Can you design a functional (immutable) solution for this validation without mutable data structures?

Yes—represent the queue as a list and, for each event, return a new list: on entry, concatenate the ID at the end; on exit, verify the head matches and return the tail. Although each step creates a new list, using persistent data structures (e.g., ropes or linked lists) ensures O(1) amortized updates, preserving linear overall time while keeping the API pure.

Examples

Example 1

Input

[[1, "entry"], [2, "entry"], [1, "exit"], [2, "exit"]]

Output

[1, 2]

Explanation: 1. Event [1, "entry"]: Vehicle 1 enters. Queue: [1]. 2. Event [2, "entry"]: Vehicle 2 enters. Queue: [1, 2]. 3. Event [1, "exit"]: Vehicle 1 is at the front of the queue. It exits successfully. Queue: [2]. Output: [1]. 4. Event [2, "exit"]: Vehicle 2 is at the front of the queue. It exits successfully. Queue: []. Output: [1, 2].

Example 2

Input

[[1, "entry"], [2, "entry"], [2, "exit"], [1, "exit"]]

Output

[1]

Explanation: 1. Event [1, "entry"]: Vehicle 1 enters. Queue: [1]. 2. Event [2, "entry"]: Vehicle 2 enters. Queue: [1, 2]. 3. Event [2, "exit"]: Vehicle 2 is not at the front (Vehicle 1 is). The exit is ignored. Queue remains [1, 2]. 4. Event [1, "exit"]: Vehicle 1 is at the front. It exits successfully. Queue: [2]. Output: [1]. Note: Vehicle 2 never gets a valid exit event after Vehicle 1 leaves, so it does not appear in the output.

Example 3

Input

[[5, "entry"], [3, "entry"], [5, "exit"], [3, "exit"], [5, "exit"]]

Output

[5, 3]

Explanation: 1. Event [5, "entry"]: Vehicle 5 enters. Queue: [5]. 2. Event [3, "entry"]: Vehicle 3 enters. Queue: [5, 3]. 3. Event [5, "exit"]: Vehicle 5 is at the front. It exits successfully. Queue: [3]. Output: [5]. 4. Event [3, "exit"]: Vehicle 3 is at the front. It exits successfully. Queue: []. Output: [5, 3]. 5. Event [5, "exit"]: Vehicle 5 is not in the facility. The exit is ignored. Output remains [5, 3].

Example 4

Input

[[10, "exit"], [10, "entry"], [10, "exit"]]

Output

[10]

Explanation: 1. Event [10, "exit"]: Vehicle 10 has not entered. The exit is ignored. 2. Event [10, "entry"]: Vehicle 10 enters. Queue: [10]. 3. Event [10, "exit"]: Vehicle 10 is at the front. It exits successfully. Queue: []. Output: [10].

Constraints

1 <= events.length <= 10^5
1 <= events[i][0] <= 10^9
events[i][1] is either "entry" or "exit
All vehicle IDs are unique integers

Optimal Approach & Strategy

Maintain a queue of currently parked vehicle IDs; on entry push, on exit verify the front matches and pop, achieving O(1) per event and O(n) total time.

Brute Force Approach

For every exit event, scan all previous entries to find the matching vehicle and ensure no later entered vehicle is still waiting, resulting in O(n²) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function validatedVehicleExitSequence(requests) {
   let entered = new Set();
   let exitOrder = [];
   for (let [vehicle, action] of requests) {
       if (action === 'entry') {
           entered.add(vehicle);
       } else if (action === 'exit' && entered.has(vehicle)) {
           exitOrder.push(vehicle);
       }
   }
   return exitOrder;
}

class Solution {
   public:
   vector<int> validatedVehicleExitSequence(vector<pair<string, string>>& requests) {
       set<string> entered;
       vector<int> exitOrder;
       for (auto& request : requests) {
           if (request.second == 'entry') {
               entered.insert(request.first);
           } else if (request.second == 'exit' && entered.find(request.first) != entered.end()) {
               exitOrder.push_back(stoi(request.first));
           }
       }
       return exitOrder;
   }
}

class Solution {
   public int[] validatedVehicleExitSequence(String[][] requests) {
       Set<String> entered = new HashSet<>();
       List<String> exitOrder = new ArrayList<>();
       for (String[] request : requests) {
           if (request[1].equals('entry')) {
               entered.add(request[0]);
           } else if (request[1].equals('exit') && entered.contains(request[0])) {
               exitOrder.add(request[0]);
           }
       }
       return exitOrder.stream().mapToInt(Integer::parseInt).toArray();
   }
}

def validated_vehicle_exit_sequence(requests):
   entered = set()
   exit_order = []
   for vehicle, action in requests:
       if action == 'entry':
           entered.add(vehicle)
       elif action == 'exit' and vehicle in entered:
           exit_order.append(vehicle)
   return exit_order

function validatedVehicleExitSequence(requests) {
   let entered = new Set();
   let exitOrder = [];
   for (let [vehicle, action] of requests) {
       if (action === 'entry') {
           entered.add(vehicle);
       } else if (action === 'exit' && entered.has(vehicle)) {
           exitOrder.push(vehicle);
       }
   }
   return exitOrder;
}

Asked in Top Tech Interviews

basic-data-structuresmediumstack-and-queue

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Validated Vehicle Exit Sequence Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Stack

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Validated Vehicle Exit Sequence — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor