Last Person to Fit in the Bus - Practice Coding Problems

Last Person to Fit in the Bus - Problem

Database Medium

You are given a table Queue representing people waiting to board a bus. The bus has a weight limit of 1000 kilograms.

Each person has:

person_id - unique identifier
person_name - name of the person
weight - weight in kilograms
turn - boarding order (1 = first to board)

Write a SQL query to find the name of the last person who can board the bus without exceeding the weight limit of 1000kg.

Note: People board in order of their turn value, and the first person is guaranteed to fit on the bus.

Table Schema

Queue

Column Name	Type	Description
`person_id` PK	int	Unique identifier for each person
`person_name`	varchar	Name of the person
`weight`	int	Weight of person in kilograms
`turn`	int	Boarding order (1 = first, n = last)

Primary Key: person_id

Note: Turn values range from 1 to n where n is total number of people

Input & Output

Example 1 — Basic Bus Loading

Input Table:

person_id	person_name	weight	turn
5	Alice	250	1
4	Bob	175	5
3	Alex	350	2
6	John Cena	400	3
1	Winston	500	6
2	Marie	200	4

Output:

person_name
John Cena

💡 Note:

When ordered by turn: Alice (250) → Alex (350) → John Cena (400) → Marie (200) → Bob (175) → Winston (500). Cumulative weights: 250 → 600 → 1000 → 1200. John Cena is the last person whose cumulative weight (1000kg) doesn't exceed the limit.

Example 2 — Early Weight Limit

Input Table:

person_id	person_name	weight	turn
1	Alice	800	1
2	Bob	175	2
3	Charlie	80	3

Output:

person_name
Bob

💡 Note:

Cumulative weights in order: Alice (800) → Bob (975) → Charlie (1055). Since Charlie would exceed 1000kg, Bob is the last person who can board.

Constraints

1 ≤ n ≤ 1000 where n is the number of people
1 ≤ person_id ≤ n
1 ≤ weight ≤ 1000
1 ≤ turn ≤ n
All person_id and turn values are unique
The first person (turn=1) will not exceed the weight limit

Visualization

Tap to expand

Understanding the Visualization

Input

Queue table with people and weights

Calculate

Running sum of weights by turn order

Filter

Last person under 1000kg limit

Key Takeaway

🎯 Key Insight: Use window functions to calculate running totals and filter by business constraints

Asked in

A Amazon 15 M Microsoft 12 G Google 8

Use window function with SUM() OVER(ORDER BY turn) to calculate running weight totals, filter by 1000kg limit, then select the person with maximum turn value.

Table Schema

Queue

Column Name	Type	Description
`person_id` PK	int	Unique identifier for each person
`person_name`	varchar	Name of the person
`weight`	int	Weight of person in kilograms
`turn`	int	Boarding order (1 = first, n = last)

Primary Key: person_id

Note: Turn values range from 1 to n where n is total number of people

Common Approaches

Approach	Time	Space	Notes
✓ Window Function with Running Total	O(n log n)	O(n)	Use window function to calculate cumulative weight and filter by limit

Window Function with Running Total — Algorithm Steps

Step 1: Order people by their turn (boarding order)
Step 2: Calculate running total of weights using SUM() OVER window function
Step 3: Filter people whose cumulative weight ≤ 1000kg
Step 4: Select the person with maximum turn (last to board)

Visualization

Tap to expand

Step-by-Step Walkthrough

Order

Sort by turn value

Sum

Calculate running weight total

Filter

Keep weights ≤ 1000kg

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting by turn for window function ordering

⚡ Linearithmic

Space Complexity

O(n)

Window frame storage for running totals

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~12 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Table Schema

Input & Output

Constraints

Visualization

Related Problems

Table Schema

Common Approaches

Window Function with Running Total — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler