ML Interview Q Series: Probability of Last Apple Drawn: A Combinatorial Approach
Browse all the Probability Interview Questions here.
A box contains 7 apples and 5 oranges. The pieces of fruit are taken out of the box, one at a time and in a random order. What is the probability that the bowl will be empty after the last apple is taken from the box?
Short Compact solution
There are 12! possible ways to order the 12 pieces of fruit. Among these, there are 7 × 11! sequences where the last piece of fruit is an apple. Therefore, the probability that the last apple is taken precisely at the end (thus leaving the bowl empty) is
Comprehensive Explanation
Reasoning with possible orders of fruit is a standard combinatorial approach. Each distinct permutation of the 12 pieces is equally likely. Since there are 7 apples and 5 oranges, there are 12! total permutations. We want the probability that the final apple is the very last piece of fruit drawn from the box. Equivalently, we ask: among all the permutations of these 12 fruits, how many end specifically with an apple?
To count the number of ways that the last position is an apple, fix one apple in that last slot. There are 7 ways to choose which apple ends up last. Once we fix an apple in that last position, the remaining 11 fruits (6 apples and 5 oranges) can be permuted in 11! ways. Consequently, the total number of permutations where the last piece is an apple is 7 × 11!.
Hence, the required probability is (7 × 11!) / 12!. Because 12! = 12 × 11!, we get (7 × 11!) / (12 × 11!) which simplifies to 7/12.
Another intuitive way to see this is to argue symmetry: each piece of fruit is equally likely to occupy each position in the random ordering. So the chance that the last piece is an apple (regardless of what else happens in the earlier draws) should be 7/12, reflecting the 7 apples out of 12 total fruits.
Using a direct “run out of apples exactly at the end” interpretation: for the bowl to be empty exactly after the last apple is taken, that last apple must happen at the final draw of all fruit. As reasoned above, each fruit is equally likely to be the last piece drawn, so the probability is 7/12.
In practice, this question can appear in many probability scenarios where you want the distribution of positions of a certain type of item among all permutations. The uniform randomness of permutations simplifies the final ratio-based argument.
Potential Follow-Up Question: Alternative Counting Methods
Some interviewers might ask how else we could arrive at 7/12 without directly invoking permutations. One could imagine labeling the apples A1, A2, …, A7 and oranges O1, O2, …, O5, and then considering each piece equally likely to appear at the last position. Because each fruit has the same chance of being last, the probability is simply 7 out of 12.
A more in-depth alternative is to use conditional probability. For example, define a random variable for the index of the last apple among the draws, and calculate the probability that its position is 12. If you sum up probabilities of “the last apple is at position k” for k = 7 through 12 and compare it to the probability that it is at exactly k = 12, you again recover 7/12.
Potential Follow-Up Question: Simulation in Python
One might be asked to outline a quick simulation approach. This verifies the result empirically and demonstrates familiarity with practical checks.
import random
def simulate(num_trials=10_000_00):
import math
success_count = 0
fruits = ['A']*7 + ['O']*5 # 7 apples, 5 oranges
for _ in range(num_trials):
# Shuffle the list randomly
random.shuffle(fruits)
# Check if the last fruit is an apple
if fruits[-1] == 'A':
success_count += 1
return success_count / num_trials
prob_estimate = simulate()
print(prob_estimate)
Running a large number of trials will yield a result close to 7/12 ≈ 0.5833..., confirming the analytical result.
Potential Follow-Up Question: Extensions or Variations
Sometimes, interviewers extend the problem. For instance, they might ask the probability that the last orange is also the last fruit overall, or the probability that a certain fruit type appears in the middle position. The same symmetry argument applies: the probability that an orange is last is 5/12, and so on.
They might also ask what happens if we want the bowl empty after the last apple, but we have more complicated conditions (such as a second container or partial knowledge of intermediate draws). In such variations, the principle is the same: either each fruit or each permutation is equally likely, and we can count or reason proportionally. If the distribution of draws is uniform over permutations, we always reduce to a simple ratio.
Lastly, an interviewer could ask about the assumption of uniform randomness. In real scenarios where fruit might be drawn with some bias, the uniform permutation argument might not hold, and we’d need a model reflecting that bias. In purely combinatorial problems, though, the uniform permutation assumption usually stands.
Below are additional follow-up questions
1) What if we want the probability that the last apple is drawn in the 10th position, not necessarily the 12th?
One way to approach this is to count how many permutations place the final apple at position 10 and ensure there are no apples in positions 11 or 12. The reasoning is as follows:
First, choose which apple is the “last apple” at position 10. There are 7 ways to do this since there are 7 apples.
For positions 1 through 9, we must have the remaining 6 apples and some subset of oranges, while positions 11 and 12 must contain only the remaining oranges (because no apples can be after the last apple).
Specifically, in positions 11 and 12, both must be oranges. We have 5 oranges total, so we place 2 of them in positions 11 and 12. There are C(5,2) ways to choose which oranges occupy those last two positions, though once chosen, these oranges can permute among themselves in 2! ways (if you consider oranges distinguishable). If oranges are considered indistinguishable, then we don’t multiply by 2!, but typically in combinatorial treatments, we often label them to keep track of permutations.
The remaining 9 positions (1 to 9) must include the 6 remaining apples and the remaining 3 oranges. These 9 positions can be arranged in 9! ways if each piece is distinct.
Putting this together in detail:
• Pick which apple goes into position 10 (7 ways). • Pick which 2 oranges go into positions 11 and 12 (C(5,2) ways if each orange is labeled). • Permute those 2 chosen oranges (2! ways). • Permute the remaining 9 fruits (6 apples + 3 oranges) in the first 9 positions (9! ways).
Hence the total permutations with the last apple at position 10 are: 7 * C(5,2) * 2! * 9!.
Divide that by 12! to get the probability. If apples and oranges are not labeled distinctly among themselves, the factor counting changes, but the overall approach—count valid permutations, then divide by total permutations—still holds.
Potential pitfalls:
Mixing up labeled vs. unlabeled permutations can lead to overcounting or undercounting.
Forgetting that no apples can appear after position 10 in this scenario.
2) How can we find the expected position of the last apple?
To calculate the expected (average) position of the last apple, consider the random variable L = the position at which the last apple appears among the 12 draws.
There is a known result for the expected maximum of k randomly placed “items” among n positions: E[the maximum position] = (k(n+1))/(k+1). But to derive it more directly:
Let X_j be an indicator variable that is 1 if position j (from 1 to 12) contains at least one apple in positions up to j. In other words, X_j = 1 if the maximum apple index is at least j. Then L = sum_{j=1 to 12} (X_j). You can compute E[L] by summing E[X_j].
Alternatively, you can do a combinatorial argument for P(L >= j): that is the probability that there is an apple in or after position j. You can use the complement: P(L < j) = the probability that all 7 apples appear among the first j-1 positions. Then summing from j=1 to 12 gives E[L].
In simpler terms, you can also reason that each of the 12 positions is equally likely to be the last apple’s location, weighted by the chance that the last apple is indeed at that location. Summing j * P(L = j) from j=1 to 12 would yield the expected value.
Potential pitfalls:
Relying on memorized formulas without understanding can lead to mistakes if the problem changes slightly.
Confusion between the expected position of the last apple vs. the probability distribution for each possible position.
3) What if there was an additional type of fruit, say bananas, making it 7 apples, 5 oranges, and 3 bananas? How do we compute the probability the last apple is still the overall last piece?
With three types of fruit, the total number of fruits is 7 + 5 + 3 = 15. When each piece is equally likely to be in any given position in a random permutation:
The probability that a randomly chosen piece (from the 15) ends up last is 1/15 for that piece.
Since there are 7 apples total, the probability that the last piece in the entire sequence is an apple is 7/15.
So the probability that the last apple is also the overall last piece is 7/15.
We did not even need to do extensive combinatorial counting if each piece is considered equally likely to land in the final draw. This direct ratio argument is often simpler. If each piece is equally likely to occupy the last position, then the chance it’s an apple is simply (number of apples)/(total pieces).
Potential pitfalls:
If bananas or oranges are not distinct from each other but the apples are, or vice versa, it can complicate counting. Always clarify whether each piece of fruit is uniquely labeled.
Failing to notice that uniform permutations naturally yield a simple ratio for which type is last.
4) How does the answer change if each piece is not equally likely to be drawn at each step? For instance, suppose each apple is twice as likely to be picked as an orange when we draw at random without replacement.
When a draw is biased, the model is no longer a simple uniform permutation of all pieces. Each draw is influenced by some selection probability that might depend on the ratio of apples to oranges remaining, or a global weighting scheme. If each apple is assigned weight wA and each orange weight wO, then the probability of drawing an apple at any step is [number_of_apples * wA] / [number_of_apples * wA + number_of_oranges * wO]. This changes dynamically as pieces are removed.
In that scenario, we can’t simply use “number of permutations.” One approach is to systematically use conditional probabilities:
Let A_i be the event that an apple is drawn at the i-th step.
Let M = the final piece drawn. We want P(M is an apple).
We can sum or recursively calculate the probability that the last piece is an apple, given that at each step we choose an item with probability proportional to its weight.
The formula can get complicated, but typically:
• If wA = 2 and wO = 1, at the start, the probability of picking any apple is 72 / (72 + 5*1) = 14/19. After each draw, the composition and total weight changes.
A simpler approach is sometimes possible if the same weighting factor applies consistently to each fruit of the same type, because there is a known result that under certain random-draw-without-replacement weighting schemes, the probability a particular piece is drawn last is still proportional to its weight. This is related to the “Polya’s Urn” style reasoning or sampling without replacement from a weighted set. If all apples share the same weight, each apple collectively has total weight 7wA, each orange collectively has total weight 5wO, so the probability that an apple is last can be 7wA / (7wA + 5*wO). For wA=2 and wO=1, that would be 14 / (14 + 5) = 14/19. This means 14/19 is the probability any apple ends up last. It is a generalization of the uniform argument.
Potential pitfalls:
Confusing “weight-based selection at each draw” with simply enumerating permutations.
Overcomplicating the calculation if you forget the known result for sampling from a weighted set without replacement (each item’s chance of occupying a given position is proportional to its weight).
5) What if we partially observe which fruit is drawn at some positions? For example, we know that at position 1 and position 3, the fruit drawn was an apple. How does that affect the probability that the last apple is drawn last?
Partial observations alter the set of possible permutations. If we observe some draws, the distribution for the rest of the positions is no longer uniform over all permutations but restricted to those permutations consistent with the observation. The basic approach is:
Identify how many apples are left after the observed draws and how many positions remain.
If the positions we observed are known, we condition on those outcomes and recalculate. For instance, if we have 7 apples and 5 oranges initially, and see that the 1st and 3rd draws are apples, then after these observations, we have 5 apples and 5 oranges left for the remaining 10 positions.
Now we ask: conditional on the event that positions 1 and 3 are apples, what is the probability that the last apple is the 12th position overall? Given that the draws are otherwise random among the remaining 10 positions, the probability that the final position (12th) is also an apple is effectively 5/10 if the draws remain uniformly random among what’s left, because 5 apples remain and 5 oranges remain.
More formally, use conditional probability: P(Last apple is in position 12 | Observed draws at positions 1 and 3 are apples) = (Number of ways to arrange 5 apples, 5 oranges in positions 2,4,5,...,12 such that position 12 is an apple) / (Number of ways to arrange 5 apples, 5 oranges in positions 2,4,5,...,12 with no restriction on the 12th).
In a uniform scenario, this ratio is 5/10 = 1/2.
Potential pitfalls:
Forgetting to update the count of remaining fruit after partial observations.
Failing to note that once some draws are fixed, the problem effectively restarts with a smaller set of fruit, preserving uniformity among those remaining.