Jobs

Interviews

Discussions

Airplane Seat Assignment Probability

#691 Most AskedMedium

Airplane Seat Assignment Probability #691 Most Asked

Medium

Google

45 views

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of the passengers will:

Take their own seat if it is still available, and
Pick other seats randomly when they find their seat occupied

Return the probability that the n^th person gets his own seat.

Example 1:

Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.

Example 2:

Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Constraints:

1 <= n <= 10⁵

Try coding it in LeetCode

Airplane Seat Assignment Probability

#691 Most AskedMedium

Airplane Seat Assignment Probability #691 Most Asked

Medium

Google

45 views

n passengers board an airplane with exactly n seats. The first passenger has lost the ticket and picks a seat randomly. But after that, the rest of the passengers will:

Take their own seat if it is still available, and
Pick other seats randomly when they find their seat occupied

Return the probability that the n^th person gets his own seat.

Example 1:

Input: n = 1
Output: 1.00000
Explanation: The first person can only get the first seat.

Example 2:

Input: n = 2
Output: 0.50000
Explanation: The second person has a probability of 0.5 to get the second seat (when first person gets the first seat).

Constraints:

1 <= n <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the number of passengers (N)?
Does N include the first passenger who misplaces their ticket?
Is N always a valid positive integer, or should I handle cases where N is zero or negative?
If the first passenger sits in their own seat, what is the expected output?
Are there any other scenarios besides the first passenger picking a random seat that would lead to a passenger sitting in the wrong seat?

Brute Force Solution

Approach

To solve this problem with brute force, we will simulate every single seating arrangement that can occur. Then, for each arrangement, we can check if the last person sits in their assigned seat. Finally, we count the number of times the last person sits in their seat and divide by the total number of possible seating arrangements to get the probability.

Here's how the algorithm would work step-by-step:

Imagine the first passenger gets on the plane.
The first passenger has a choice of any of the seats.
For each seat the first passenger could pick, we look at what happens next.
Now consider the second passenger. If the first passenger took the second passenger's seat, then the second passenger also gets to choose any remaining seat.
Otherwise, the second passenger will sit in their assigned seat.
We keep doing this for every passenger, one after another. At each step we need to consider the different seat choice possibilities.
Once everyone is seated, we check if the last passenger ended up in their own seat.
We repeat this whole process many, many times, for every possible seat choice the first passenger could make, and then for every choice the second passenger could make, and so on.
After trying every single possible seating arrangement, we count how many times the last passenger ended up in their own seat.
Finally, we divide the number of times the last passenger was in their seat by the total number of seat arrangements we tried. That's our probability.

Code Implementation

def airplane_seat_assignment_probability(number_of_seats):
    total_arrangements = 0
    last_person_correct = 0

    def simulate_seating(seats_available, current_passenger):
        nonlocal total_arrangements, last_person_correct
        
        # Base case: all passengers are seated
        if current_passenger > number_of_seats:
            total_arrangements += 1
            if seats_available[number_of_seats - 1] == 1:
                last_person_correct += 1
            return

        # Simulate first passenger's choice
        if current_passenger == 1:
            for seat_choice in range(number_of_seats):
                seats_copy = seats_available[:]
                seats_copy[seat_choice] = 1
                simulate_seating(seats_copy, current_passenger + 1)

        # For other passengers:
        else:
            # If seat is available, passenger sits in assigned seat
            if seats_available[current_passenger - 1] == 0:
                seats_copy = seats_available[:]
                seats_copy[current_passenger - 1] = 1
                simulate_seating(seats_copy, current_passenger + 1)

            # If seat is taken, passenger chooses a random seat
            else:
                available_seats_indices = [i for i, seat in enumerate(seats_available) if seat == 0]

                for seat_choice_index in range(len(available_seats_indices)):
                    seats_copy = seats_available[:]

                    chosen_seat_index = available_seats_indices[seat_choice_index]
                    seats_copy[chosen_seat_index] = 1
                    simulate_seating(seats_copy, current_passenger + 1)

    # Initialize available seats
    available_seats = [0] * number_of_seats

    # Start simulation
    simulate_seating(available_seats, 1)

    # Calculate and return probability
    return last_person_correct / total_arrangements

Big(O) Analysis

Time Complexity

O(n!) – The provided brute force approach involves simulating every possible seating arrangement. The first passenger has n choices, the second passenger can have up to n choices, the third up to n choices, and so on. This generates a decision tree where each level has up to n branches. Therefore, the total number of possible arrangements explored is proportional to n * (n-1) * (n-2) * ... * 1, which is n factorial. Checking if the last person is in their seat for each arrangement takes O(1) time. Thus the total time complexity is O(n!).

Space Complexity

O(N) – The brute force approach involves simulating every seating arrangement, which requires keeping track of the current arrangement of passengers. This can be represented using an array of size N, where N is the number of passengers, to store the seat assignment for each passenger in a given simulation. Furthermore, the recursive calls to explore different seating possibilities will create a call stack. In the worst-case scenario where the first passenger chooses a seat other than their own multiple times, the depth of the recursion can reach N. Therefore, the auxiliary space is dominated by the call stack, leading to a space complexity of O(N).

Optimal Solution

Approach

This problem seems complicated, but there's a surprising shortcut. Instead of tracking every passenger's path, we realize most of the time, things go smoothly. We only care about the situations where things go wrong.

Here's how the algorithm would work step-by-step:

Imagine the first person picks a random seat.
Consider what happens if the first person picks their own seat: the last person gets their assigned seat.
Consider what happens if the first person picks the last person's seat: the last person definitely won't get their seat.
Consider what happens if the first person picks someone else's seat (let's say the 'k'th person's seat): then persons 2 through k-1 will get their own seats.
Then, the 'k'th person is in the same situation as the first person: they must pick a random seat.
The 'k'th person can either pick their own seat, the last person's seat, or someone else's seat.
Notice that this process continues until either the 'k'th person picks their own seat or the last person's seat.
This means only two outcomes are possible: either the first or last person gets their assigned seat.
Because the first person can either pick their own seat or the last person's seat, the last person only has a 50% chance of getting their seat.

Code Implementation

def airplane_seat_assignment_probability(number_of_passengers):
    if number_of_passengers <= 1:
        return 1.0

    # If first passenger picks their own seat,
    # last passenger will get theirs.

    # If first passenger picks last passenger's seat,
    # last passenger won't get theirs.

    # Because of the probabilistic 'chain reaction',
    # the last passenger has a 50% chance.
    return 0.5

Big(O) Analysis

Time Complexity

O(1) – The provided solution doesn't involve iterating through the passengers or seats. It relies on a probabilistic argument that the last person has a 50% chance of getting their seat unless n is 1, which is a base case. There are no loops, recursions, or data structure traversals dependent on the number of passengers (n). Therefore, the time complexity is constant.

Space Complexity

O(1) – The provided explanation focuses on a logical process rather than a concrete algorithm. It does not explicitly describe the creation of any data structures like arrays, hash maps, or lists. The reasoning involves tracking seat assignments conceptually, and making decisions based on comparisons. Therefore, the space complexity is constant because no auxiliary space dependent on the number of passengers (N) is utilized.

Edge Cases

Case	How to Handle
n = 1 (only one passenger)	The first passenger will always take their own seat, thus the last passenger has 0 probability of sitting in their own seat, which means the probability of sitting in the assigned seat is 0 in the problem, but the problem only cares the probability of last passenger sitting in their assigned seat, which is 1 for n = 1.
n = 2 (two passengers)	The first passenger either takes their own seat (probability 1/2, last passenger gets own seat) or the second passenger's seat (probability 1/2, last passenger doesn't get own seat), resulting in a 50% chance.
Large n (scalability)	The probability converges to 0.5 regardless of the size of n for n > 1; thus, the solution will be O(1) in time and space, and scales perfectly.
Zero or negative input for n	Return 0 as there are no passengers or seats in such scenarios, indicating an invalid input.
Integer overflow for very large n	The problem doesn't require storing intermediate results depending on n, and the problem definition doesn't include dealing with extremely large integer, thus we can ignore the integer overflow situation.
Floating-point precision with extremely large n (although it is constant)	The resulting value of probability is either 0 or 0.5 or 1, so floating-point precision is not a significant concern.
n close to the upper limit of integer representation	Although the problem states to only calculate based on 'n', the calculation simplifies and does not require manipulation of 'n', therefore the integer limit is unlikely to be reached and is not a main issue.
The last passenger's assigned seat is already taken by a previous passenger	The process continues by randomly assigning seats until either the last passenger finds their seat or all seats are taken, and such intermediate cases are handled correctly by the recursive or iterative structure of the solution which ultimately converges to probability of 0.5 for n > 1 and 1 for n = 1.

n = 1 (only one passenger)

How to Handle:

The first passenger will always take their own seat, thus the last passenger has 0 probability of sitting in their own seat, which means the probability of sitting in the assigned seat is 0 in the problem, but the problem only cares the probability of last passenger sitting in their assigned seat, which is 1 for n = 1.

n = 2 (two passengers)

How to Handle:

The first passenger either takes their own seat (probability 1/2, last passenger gets own seat) or the second passenger's seat (probability 1/2, last passenger doesn't get own seat), resulting in a 50% chance.

Large n (scalability)

How to Handle:

The probability converges to 0.5 regardless of the size of n for n > 1; thus, the solution will be O(1) in time and space, and scales perfectly.

Zero or negative input for n

How to Handle:

Return 0 as there are no passengers or seats in such scenarios, indicating an invalid input.

Integer overflow for very large n

How to Handle:

The problem doesn't require storing intermediate results depending on n, and the problem definition doesn't include dealing with extremely large integer, thus we can ignore the integer overflow situation.

Floating-point precision with extremely large n (although it is constant)

How to Handle:

The resulting value of probability is either 0 or 0.5 or 1, so floating-point precision is not a significant concern.

n close to the upper limit of integer representation

How to Handle:

Although the problem states to only calculate based on 'n', the calculation simplifies and does not require manipulation of 'n', therefore the integer limit is unlikely to be reached and is not a main issue.

The last passenger's assigned seat is already taken by a previous passenger

How to Handle:

The process continues by randomly assigning seats until either the last passenger finds their seat or all seats are taken, and such intermediate cases are handled correctly by the recursive or iterative structure of the solution which ultimately converges to probability of 0.5 for n > 1 and 1 for n = 1.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the number of passengers (N)?
Does N include the first passenger who misplaces their ticket?
Is N always a valid positive integer, or should I handle cases where N is zero or negative?
If the first passenger sits in their own seat, what is the expected output?
Are there any other scenarios besides the first passenger picking a random seat that would lead to a passenger sitting in the wrong seat?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the first passenger gets on the plane.
The first passenger has a choice of any of the seats.
For each seat the first passenger could pick, we look at what happens next.
Now consider the second passenger. If the first passenger took the second passenger's seat, then the second passenger also gets to choose any remaining seat.
Otherwise, the second passenger will sit in their assigned seat.
We keep doing this for every passenger, one after another. At each step we need to consider the different seat choice possibilities.
Once everyone is seated, we check if the last passenger ended up in their own seat.
We repeat this whole process many, many times, for every possible seat choice the first passenger could make, and then for every choice the second passenger could make, and so on.
After trying every single possible seating arrangement, we count how many times the last passenger ended up in their own seat.
Finally, we divide the number of times the last passenger was in their seat by the total number of seat arrangements we tried. That's our probability.

Code Implementation

def airplane_seat_assignment_probability(number_of_seats):
    total_arrangements = 0
    last_person_correct = 0

    def simulate_seating(seats_available, current_passenger):
        nonlocal total_arrangements, last_person_correct
        
        # Base case: all passengers are seated
        if current_passenger > number_of_seats:
            total_arrangements += 1
            if seats_available[number_of_seats - 1] == 1:
                last_person_correct += 1
            return

        # Simulate first passenger's choice
        if current_passenger == 1:
            for seat_choice in range(number_of_seats):
                seats_copy = seats_available[:]
                seats_copy[seat_choice] = 1
                simulate_seating(seats_copy, current_passenger + 1)

        # For other passengers:
        else:
            # If seat is available, passenger sits in assigned seat
            if seats_available[current_passenger - 1] == 0:
                seats_copy = seats_available[:]
                seats_copy[current_passenger - 1] = 1
                simulate_seating(seats_copy, current_passenger + 1)

            # If seat is taken, passenger chooses a random seat
            else:
                available_seats_indices = [i for i, seat in enumerate(seats_available) if seat == 0]

                for seat_choice_index in range(len(available_seats_indices)):
                    seats_copy = seats_available[:]

                    chosen_seat_index = available_seats_indices[seat_choice_index]
                    seats_copy[chosen_seat_index] = 1
                    simulate_seating(seats_copy, current_passenger + 1)

    # Initialize available seats
    available_seats = [0] * number_of_seats

    # Start simulation
    simulate_seating(available_seats, 1)

    # Calculate and return probability
    return last_person_correct / total_arrangements

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine the first person picks a random seat.
Consider what happens if the first person picks their own seat: the last person gets their assigned seat.
Consider what happens if the first person picks the last person's seat: the last person definitely won't get their seat.
Consider what happens if the first person picks someone else's seat (let's say the 'k'th person's seat): then persons 2 through k-1 will get their own seats.
Then, the 'k'th person is in the same situation as the first person: they must pick a random seat.
The 'k'th person can either pick their own seat, the last person's seat, or someone else's seat.
Notice that this process continues until either the 'k'th person picks their own seat or the last person's seat.
This means only two outcomes are possible: either the first or last person gets their assigned seat.
Because the first person can either pick their own seat or the last person's seat, the last person only has a 50% chance of getting their seat.

Code Implementation

def airplane_seat_assignment_probability(number_of_passengers):
    if number_of_passengers <= 1:
        return 1.0

    # If first passenger picks their own seat,
    # last passenger will get theirs.

    # If first passenger picks last passenger's seat,
    # last passenger won't get theirs.

    # Because of the probabilistic 'chain reaction',
    # the last passenger has a 50% chance.
    return 0.5

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1 (only one passenger)	The first passenger will always take their own seat, thus the last passenger has 0 probability of sitting in their own seat, which means the probability of sitting in the assigned seat is 0 in the problem, but the problem only cares the probability of last passenger sitting in their assigned seat, which is 1 for n = 1.
n = 2 (two passengers)	The first passenger either takes their own seat (probability 1/2, last passenger gets own seat) or the second passenger's seat (probability 1/2, last passenger doesn't get own seat), resulting in a 50% chance.
Large n (scalability)	The probability converges to 0.5 regardless of the size of n for n > 1; thus, the solution will be O(1) in time and space, and scales perfectly.
Zero or negative input for n	Return 0 as there are no passengers or seats in such scenarios, indicating an invalid input.
Integer overflow for very large n	The problem doesn't require storing intermediate results depending on n, and the problem definition doesn't include dealing with extremely large integer, thus we can ignore the integer overflow situation.
Floating-point precision with extremely large n (although it is constant)	The resulting value of probability is either 0 or 0.5 or 1, so floating-point precision is not a significant concern.
n close to the upper limit of integer representation	Although the problem states to only calculate based on 'n', the calculation simplifies and does not require manipulation of 'n', therefore the integer limit is unlikely to be reached and is not a main issue.
The last passenger's assigned seat is already taken by a previous passenger	The process continues by randomly assigning seats until either the last passenger finds their seat or all seats are taken, and such intermediate cases are handled correctly by the recursive or iterative structure of the solution which ultimately converges to probability of 0.5 for n > 1 and 1 for n = 1.

n = 1 (only one passenger)

How to Handle:

n = 2 (two passengers)

How to Handle:

Large n (scalability)

How to Handle:

The probability converges to 0.5 regardless of the size of n for n > 1; thus, the solution will be O(1) in time and space, and scales perfectly.

Zero or negative input for n

How to Handle:

Return 0 as there are no passengers or seats in such scenarios, indicating an invalid input.

Integer overflow for very large n

How to Handle:

Floating-point precision with extremely large n (although it is constant)

How to Handle:

The resulting value of probability is either 0 or 0.5 or 1, so floating-point precision is not a significant concern.

n close to the upper limit of integer representation

How to Handle:

The last passenger's assigned seat is already taken by a previous passenger

How to Handle:

0/1916 Google questions completed

0/1916 completed