Consecutive Available Seats

Consecutive Available Seats

What is this problem about?

The Consecutive Available Seats interview question is a SQL-based challenge that focuses on identifying patterns in tabular data. You are given a table representing seats in a cinema, where each row contains a seat ID and a flag indicating if the seat is free or occupied. Your task is to find all seat IDs that are free and part of a sequence of at least two consecutive free seats.

Why is this asked in interviews?

This Consecutive Available Seats coding problem is a staple at Amazon and other tech companies because it evaluates a candidate's proficiency with relational databases beyond basic filtering. It tests your ability to compare a row with its neighbors, a common requirement in data analysis and scheduling applications.

Algorithmic pattern used

This follows the Database interview pattern. To solve this, you typically use one of two methods:

1. Self-Join: Joining the table with itself on the condition that the seat IDs are adjacent (a.id = b.id + 1 or a.id = b.id - 1) and both are free.
2. Window Functions: Using LAG() or LEAD() to check the status of the previous or next seat without performing a full join.

Example explanation

Imagine a small row of seats:

• Seat 1: Free
• Seat 2: Free
• Seat 3: Occupied
• Seat 4: Free
• Seat 5: Free

The query should identify that Seats 1 and 2 are a consecutive pair, and Seats 4 and 5 are another. Seat 3 is skipped because it's occupied. The final result would be the list [1, 2, 4, 5].

Common mistakes candidates make

• Only returning the first seat of a pair: Forgetting that all seats in the consecutive block must be returned.
• Ignoring non-sequential IDs: Assuming IDs are always 1, 2, 3... without gaps. A robust solution should handle the logic carefully if seat IDs aren't perfectly incremental.
• Not using DISTINCT: If a seat is part of a triplet (e.g., 1, 2, 3 are free), a simple self-join might return seat 2 twice (once for pairing with 1 and once for pairing with 3).

Interview preparation tip

When dealing with "consecutive" logic in SQL, always consider Window Functions. They are more modern, readable, and often more performant than self-joins for sequence detection.