Cracking The Coding Interview Together – Problem 6.10: Poison

Imagine you are running a critical production system, and a single, silent bug has corrupted one of your database records. You have the tools to run diagnostic batches, but each batch run is incredibly expensive and takes a full week to return results. This is not just a hypothetical nightmare; it is the exact software engineering equivalent of the classic Poison puzzle from Cracking the Coding Interview.

The core conflict of this problem lies in the brutal latency constraint. We have 1000 bottles of soda, exactly one of which is poisoned, and only 10 test strips. A single test takes seven days to return a result. If we test bottles one by one, or even in simple sequential groups, we will run out of time or resources. Our shared goal today is to design an optimal, mathematically guaranteed testing strategy that identifies the poisoned bottle in the absolute minimum number of days. Along the way, we will discover how information theory and binary representation turn a seemingly impossible physical constraint into an elegant, single-round algorithmic solution.

Problem Statement

Let us formally define the operational parameters of our challenge:

• The Inventory: 1000 bottles of soda, labeled 1 to 1000. Exactly one bottle contains a highly potent poison.
• The Detectors: 10 test strips. A single drop of poison will turn a strip positive permanently.
• The Constraints:
  • You can apply any number of drops from any number of bottles to a single test strip simultaneously.
  • Once a strip turns positive, it is permanently ruined and cannot be reused.
  • You can only run tests (apply drops) once per day.
  • It takes exactly seven days for a test strip to show a result after drops are applied.
• The Goal: Identify the exact poisoned bottle in the fewest number of days possible.

Analyze the Problem Together

When we first look at this problem, our instinct might be to try a naive divide-and-conquer approach. Let's break down why that fails and how we can find a better path.

If we group the bottles into 10 batches of 100, put drops from each batch onto a corresponding strip, and wait 7 days, we will indeed find which batch of 100 contains the poison. But now we have used up one or more test strips, and we still have 100 bottles to search. If we repeat this process, it will take another 7 days, and another, quickly blowing past our goal of minimizing the total days.

The "Aha!" moment comes when we stop thinking of the test strips as sequential buckets and start thinking of them as bits of information.

Let's look at the mathematical capacity of our resources. We have 10 test strips. Each test strip can exist in one of two binary states at the end of a test cycle: 0 (negative/clean) or 1 (positive/poisoned).

With 10 binary bits, how many unique states can we represent?

2^10 = 1024 states

Since 1024 is greater than our 1000 bottles, we have exactly enough information capacity to uniquely identify any single bottle from 1 to 1000 in a single round of testing! This means we can solve the entire problem in exactly 7 days (the minimum latency of a single test run).

Questions for the Interviewer

As senior engineers, we never jump straight into coding without clarifying the boundaries of our system. Here are the questions we should ask our interviewer:

• Q1: Can we mix an unlimited number of drops on a single strip?
  Expected Answer: Yes, physical dilution is not an issue. A single molecule of poison is enough to trigger a positive result.
• Q2: Is it guaranteed that exactly one bottle is poisoned? What if zero are poisoned?
  Expected Answer: Yes, exactly one is poisoned. However, our binary system can easily handle the "zero poisoned" case (all strips remain negative, representing state 0).
• Q3: Are we allowed to run tests across multiple days to save strips if we had fewer than 10?
  Expected Answer: Yes, but since we have 10 strips and want to minimize days, the single-round 7-day approach is the absolute global minimum.

Think About the Solution

Let's design the mapping mechanism. We will assign each bottle a unique ID from 1 to 1000. We then represent this ID as a 10-digit binary number. For example:

• Bottle 1: 0000000001
• Bottle 2: 0000000010
• Bottle 42: 0000101010
• Bottle 1000: 1111101000

We have 10 test strips, which we label from 0 to 9. Each strip corresponds to a bit position in our 10-bit binary ID.

On Day 1, we perform the following distribution:

For every bottle i from 1 to 1000, we look at its binary representation. If the j-th bit of bottle i is set to 1, we take a drop from bottle $i$ and place it on test strip j.

After waiting 7 days, we inspect the 10 strips. If strip j is positive, we set the j-th bit of our result to 1. If it is negative, we set it to 0. The resulting 10-bit binary number will point directly and unambiguously to the poisoned bottle!

Write Code and Explain

Let's implement a clean, production-ready Java simulation of this binary testing system. We will design this with clear object-oriented principles so that it is easy to read and maintain.

import java.util.ArrayList;
import java.util.List; 

public class PoisonDetector {

    // Represents a single bottle of soda
    public static class Bottle {
        private final int id;
        private final boolean isPoisoned;

        public Bottle(int id, boolean isPoisoned) {
            this.id = id; 
            this.isPoisoned = isPoisoned;
        }

        public int getId() {
            return id;
        }

        public boolean isPoisoned() {
            return isPoisoned;
        }
    }

    // Represents a physical test strip
    public static class TestStrip {
        private final int id;
        private boolean isPositive = false;

        public TestStrip(int id) {
            this.id = id;
        }

        public int getId() {
            return id;
        }

        public boolean isPositive() {
            return isPositive;
        }

        // Apply a drop from a bottle to this strip
        public void applyDrop(Bottle bottle) {
            if (bottle.isPoisoned()) {
                this.isPositive = true;
            }
        }
    }

    /**
     * Simulates the distribution of drops onto the test strips based on binary encoding.
     */
    public static void distributeDrops(List bottles, List strips) {
        for (Bottle bottle : bottles) {
            int id = bottle.getId();
            // Check each of the 10 bits of the bottle's ID
            for (int bit = 0; bit < 10; bit++) {
                if (((id >> bit) & 1) == 1) {
                    // If the bit is set, apply a drop to the corresponding strip
                    strips.get(bit).applyDrop(bottle);
                }
            }
        }
    }

    /**
     * Decodes the state of the test strips back into the poisoned bottle's ID.
     */
    public static int decodePoisonedBottleId(List strips) {
        int poisonedId = 0;
        for (int bit = 0; bit < 10; bit++) {
            if (strips.get(bit).isPositive()) {
                // Set the corresponding bit in our result
                poisonedId |= (1 << bit);
            }
        }
        return poisonedId;
    }

    public static void main(String[] args) {
        // Setup: 1000 bottles, let's poison bottle #423 arbitrarily
        int targetPoisonedId = 423;
        List<Bottle> bottles = new ArrayList<>();
        for (int i = 1; i <= 1000; i++) {
            bottles.add(new Bottle(i, i == targetPoisonedId));
        }

        // Setup: 10 test strips
        List<TestStrip> strips = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            strips.add(new TestStrip(i));
        }

        // Day 1: Distribute drops
        distributeDrops(bottles, strips);

        // Day 8 (7 days later): Decode the results
        int detectedId = decodePoisonedBottleId(strips);

        System.out.println("Actual Poisoned Bottle ID: " + targetPoisonedId);
        System.out.println("Detected Poisoned Bottle ID: " + detectedId);
        
        if (detectedId == targetPoisonedId) {
            System.out.println("SUCCESS: The poisoned bottle was correctly identified!");
        } else {
            System.out.println("FAILURE: Incorrect bottle identified.");
        }
    }
}

Code Walkthrough

Let's trace exactly what happens in our simulation:

1. Bitwise Distribution: In distributeDrops, we iterate through all 1000 bottles. For each bottle, we check which of its bits are set to 1 using the bitwise shift operator (id >> bit) and a mask (& 1). If the bit is set, we apply a drop to the corresponding TestStrip.
2. The Poison Effect: If the bottle being sampled is the poisoned one, any strip it touches will have its isPositive flag set to true.
3. Reconstruction: In decodePoisonedBottleId, we read the state of our 10 strips. If strip bit is positive, we use the bitwise OR operator (|=) to set that bit in our final integer result.

Time & Space Complexity

Let's analyze the efficiency of our algorithmic simulation:

Time Complexity:

Distribution Phase: O(B · S), where B is the number of bottles (1000) and S is the number of strips (10). Since S = log₂(B), this is effectively O(B log B) operations.

Decoding Phase: O(S) to read the strips, which is O(log B).

Overall Time Complexity: O(B) to process all bottles.

Space Complexity: O(B + S) to store the bottles and strips in memory. In a real-world physical scenario, the space complexity of our physical testing apparatus is O(S) (only 10 physical strips).

Why This Problem Matters (The Senior Perspective)

This problem is a beautiful demonstration of Information Theory and Error-Correcting Codes. In production software engineering, we use these exact principles daily:

• Batch Testing in CI/CD: If you have 1000 commits and one of them broke the build, running a full test suite on each commit sequentially is too slow. Instead, we can run batched builds (similar to our binary test strips) to isolate the breaking commit in parallel.
• Bloom Filters: A Bloom filter uses multiple hash functions to map elements to a bit array. Just like our test strips, a Bloom filter can tell us with absolute certainty if an element is *not* present, or with some probability if it *is* present, using minimal memory.
• Pipelined Execution: What if we had fewer than 10 strips? We could pipeline our tests across multiple days. By using the *day of detection* as an extra dimension of information, we can scale our search space exponentially. This is highly analogous to instruction pipelining in modern CPUs.

Final Thoughts

By shifting our perspective from physical sequential testing to binary representation, we solved a complex latency problem with mathematical elegance. The next time you face a high-latency, high-cost diagnostic problem in your production systems, remember the 1000 bottles of soda: look for ways to parallelize and encode your search space.

What did you think of this solution? Could you design a strategy to find the poisoned bottle if we only had 5 strips but were allowed to run tests over 10 days? Let's discuss in the comments below!

Until next time, happy coding!