Amazon Interview Question: Binary Solution to the Poison Bottle Problem Explained

A Classic Amazon Interview Question

In algorithm interviews, some questions appear deceptively simple yet precisely test a candidate's abstract thinking and mathematical modeling skills. The "Poison Bottle Problem," which has appeared in Amazon interviews, is a prime example.

Here's the problem: You have n bottles, and exactly one of them contains poison. You can use mice to test — each mouse can drink from any number of bottles, but if any of the liquids it drinks contains poison, the mouse will die.

The question is: What is the minimum number of mice needed to identify the poisoned bottle?

The beauty of this problem is that it doesn't require complex data structures or advanced algorithms. Instead, it requires you to break free from the linear thinking pattern of "one mouse per bottle" and discover the essence of information encoding.

Start with the Simplest Case: 2 Bottles Need Only 1 Mouse

The classic approach to solving logic puzzles like this is to start reasoning from the smallest possible scenario.

Suppose we have only 2 bottles. We actually need just 1 mouse:

• Have the mouse drink from the first bottle;
• If the mouse dies, the first bottle is poisoned;
• If the mouse survives, the poison must be in the second bottle.

The key insight here is: a single mouse has two possible final states — alive or dead. These two states are exactly enough to distinguish between 2 bottles. In other words, one mouse carries "1 bit" of information.

Following this line of thinking, we naturally ask: if each mouse carries 1 bit of information, how many distinct outcomes can multiple mice express together?

Binary Encoding: The Core Solution to the Poison Bottle Problem

The answer lies in binary representation.

Each mouse has two states — "dead" and "alive" — which we can denote as 1 and 0 respectively. With k mice, the total number of state combinations is 2^k. Each combination uniquely corresponds to a bottle's number.

Therefore, to distinguish among n bottles, we need:

2^k ≥ n

Solving for k:

k = ⌈log₂(n)⌉

In other words, the minimum number of mice required equals the ceiling of the base-2 logarithm of n.

Step-by-Step Binary Encoding Procedure

In practice, here's how to set it up:

1. Assign each bottle a number starting from 0, and write it in binary form;
2. The i-th mouse drinks from all bottles whose i-th binary digit is 1;
3. After the test, observe which mice have died;
4. Set the binary digits corresponding to dead mice to 1 and surviving mice to 0 — the resulting binary number is the poisoned bottle's number.

For example, if the mice at positions 0 and 3 die while the rest survive, the poisoned bottle's number is 1001 in binary, which is 9 in decimal.

Practical Verification: How Many Mice for 1,025 Bottles?

The video provides an excellent example: if there are 1,025 bottles, how many mice are needed?

Let's calculate:

• 2^10 = 1,024, which isn't enough to cover 1,025 bottles;
• 2^11 = 2,048, which is sufficient.

So the answer is 11 mice.

This result confirms the formula ⌈log₂(1025)⌉ = 11. Just 11 mice can pinpoint the single poisoned bottle among 1,025 — the information compression efficiency of binary encoding is truly remarkable.

Why This Question Is a Favorite at Top Tech Companies

There are three reasons why this problem frequently appears in interviews at companies like Amazon:

First, it tests abstract modeling ability. Candidates must recognize that "a mouse's life or death" is equivalent to "a binary bit" — this abstraction is the make-or-break moment in solving the problem.

Second, it embodies information theory principles. Each test gathers information, and log₂(n) represents the minimum amount of information needed to distinguish among n objects. Understanding this is key to seeing why the answer isn't n or n/2, but logarithmic.

Third, it's highly extensible. This problem has more complex variants, such as "multiple rounds of testing allowed" or "multiple poisoned bottles," all of which build upon this foundation. Mastering the encoding approach of the basic version is a prerequisite for tackling these variants.

Summary: Master Binary Encoding Thinking for Interviews

The Poison Bottle Problem is a classic "less is more" interview question: it doesn't rely on coding tricks but tests whether you can re-examine a problem through the lens of binary encoding.

The core conclusion fits in a single sentence — to distinguish among n bottles, you need at minimum ⌈log₂(n)⌉ mice.

If you're preparing for algorithm interviews, consider this problem excellent training material for abstract thinking. The next time you encounter a question about "distinguishing the maximum number of states with the fewest resources," remember to ask yourself: Can the information here be encoded in binary?