How should I practice Bus Station Seat Allotment?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi phone screen problems in FastPrep.

Is Bus Station Seat Allotment associated with InMobi?

FastPrep tags this as a InMobi phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Bus Station Seat Allotment

Learn this problem

● Medium

InMobiFULLTIMEPHONE SCREEN

Problem statement

A bus has infinitely many seats numbered with positive integers. There are n people in a queue. Person i initially requests seat desiredSeats[i].

Repeatedly process the person at the front of the queue:

If their currently requested seat is empty, assign that seat to the person and remove them from the queue.
If the seat is occupied, increase their requested seat number by 1 and move them to the back of the queue.

Return an array assigned in the original queue order, where assigned[i] is the final seat assigned to person i.

Function

allotSeats(desiredSeats: int[]) → int[]

Examples

Example 1

desiredSeats = [1,1,2]return = [1,3,2]

The first person takes seat 1. The second person finds it occupied and moves behind the third person with a request for seat 2. The third person takes seat 2, so the second person eventually takes seat 3.

Example 2

desiredSeats = [3,1,3,2]return = [3,1,4,2]

The first, second, and fourth people take seats 3, 1, and 2 on their first turns. The third person first finds seat 3 occupied, then takes seat 4.

Constraints

1 <= desiredSeats.length <= 10^5
1 <= desiredSeats[i] <= desiredSeats.length