Last Person to Fit in the Bus

Last Person to Fit in the Bus

1. What is this problem about?

The Last Person to Fit in the Bus is a database (SQL) interview question. You are given a Queue table containing details of people waiting for a bus (name, weight, and turn). The bus has a weight limit of 1000 kgs. People board the bus in the order of their turn. You need to find the name of the last person who can board the bus without exceeding the weight limit.

2. Why is this asked in interviews?

This is a common SQL question at companies like Microsoft and Amazon to test a candidate's ability to use Window Functions. Specifically, it tests your knowledge of "Running Totals" (cumulative sums). It evaluates whether you can perform sequential analysis within a declarative language like SQL, which is crucial for financial and log-based data analysis.

3. Algorithmic pattern used

The core pattern used here is the Database Window Function pattern. You must calculate a cumulative_weight for each person by summing the weights of all people whose turn is less than or equal to theirs. This is achieved using SUM(weight) OVER (ORDER BY turn). Once you have the running total, you filter for all rows where the total is <= 1000 and select the person with the highest turn.

4. Example explanation

Queue:

• Alice (turn 1, weight 300) -> Running Sum: 300
• Bob (turn 2, weight 500) -> Running Sum: 800
• Charlie (turn 3, weight 300) -> Running Sum: 1100 (Limit Exceeded!)
• Dave (turn 4, weight 100) -> Running Sum: 1200 Filtered (Sum <= 1000): Alice, Bob. The person with the largest turn in the filtered list is Bob. Result: Bob.

5. Common mistakes candidates make

A common mistake is not ordering by turn inside the window function, which results in a total sum for every row rather than a running sum. Another error is trying to use a complex self-join instead of a window function, which is less readable and often slower. Some also forget to handle the limit (1000) correctly in the WHERE or HAVING clause.

6. Interview preparation tip

For "Database, SQL interview pattern" questions, always keep Window Functions like SUM() OVER, RANK(), and ROW_NUMBER() in your toolkit. They are the standard way to solve sequential or ranking problems in SQL. Practice writing these queries on platforms that support modern SQL versions like PostgreSQL or SQL Server.