Cracking The Coding Interview Together – Problem 6.1: The Heavy Pill

Imagine you are on call, and a critical alert fires: one of your 20 identical background worker nodes is corrupting data. The corruption is subtle—a slight, fractional drift in floating-point calculations. You have a diagnostic tool that can run a comprehensive, deep-packet inspection on any batch of jobs, but running this tool is incredibly resource-intensive. In fact, due to strict rate limits and performance budgets, you can only run this diagnostic tool exactly once.

How do you pinpoint the exact worker node that is misbehaving without disrupting the entire cluster?

This real-world debugging nightmare is the modern software engineer's equivalent of the classic brain teaser: Problem 6.1: The Heavy Pill from Cracking the Coding Interview. At first glance, the constraint of a single measurement feels mathematically impossible. It forces us to rethink how we encode identity into our data. Today, we are going to tackle this problem together, analyze the underlying mathematical trick, and write a production-ready, robust Java simulation that avoids common floating-point pitfalls.

Problem Statement

Let's lay out the parameters of the puzzle clearly:

• You have 20 bottles of pills.
• 19 of these bottles contain pills that weigh exactly 1.0 gram each.
• Exactly 1 bottle contains "heavy" pills that weigh exactly 1.1 grams each.
• You are given an analytical scale that provides an exact, high-precision measurement.
• Constraint: You can only use the scale exactly once.

Our goal is to design an algorithm (and a corresponding software implementation) that identifies the index of the heavy bottle with 100% accuracy using only a single weighing operation.

Analyze the Problem Together

Let's put on our systems architect hats and break down the constraints. Why is this hard?

If we could use the scale multiple times, the solution would be trivial. We could perform a binary search, or simply weigh pills from each bottle one by one. That would yield an $O(\log N)$ or $O(N)$ complexity in terms of scale uses. But our constraint is $O(1)$ scale uses.

This means we cannot use a sequential, feedback-driven approach. We must gather all our samples, place them on the scale simultaneously, and extract the identity of the faulty bottle from a single scalar value (the total weight).

Let's look at a comparative table of potential approaches:

The "Aha!" moment lies in information encoding. If we take a uniform number of pills from each bottle, we lose the mapping between the pill and its origin. To preserve this mapping, we must vary the quantity of pills we draw from each bottle. By taking a unique number of pills from each bottle, we encode the bottle's index directly into the weight contribution of that bottle.

Let's formalize this: we take 1 pill from Bottle 1, 2 pills from Bottle 2, 3 pills from Bottle 3, and so on, up to 20 pills from Bottle 20.

The total number of pills on the scale will be:

$$\sum_{i=1}^{20} i = \frac{20 \times (20 + 1)}{2} = 210 \text{ pills}$$

If all bottles contained standard 1.0g pills, the expected weight would be exactly 210.0 grams. However, because one bottle contains 1.1g pills, every pill we took from that specific bottle will contribute an extra 0.1 grams to the total weight.

Therefore, the formula to find the heavy bottle index ($X$) is:

$$X = \frac{\text{Actual Weight} - \text{Expected Weight}}{0.1}$$

For example, if Bottle 7 is the heavy one, we will have contributed 7 heavy pills. The scale will read $210.0 + (7 \times 0.1) = 210.7$ grams. The formula yields $(210.7 - 210.0) / 0.1 = 7$. It works perfectly!

Questions for the Interviewer

Before jumping into the code, a senior engineer always clarifies the boundaries of the system. Here are the questions we should ask our interviewer:

1. Do we have an adequate supply of pills in each bottle? (To support this algorithm, the $i$-th bottle must contain at least $i$ pills. For 20 bottles, Bottle 20 must have at least 20 pills. We will assume yes, but our code should validate this.)
2. What are the precision limits of the scale? (In the real world, scales have measurement errors. In software, floating-point arithmetic suffers from precision loss. We must design our code to handle floating-point inaccuracies safely.)
3. Can the number of bottles scale dynamically? (We should write our solution to support $N$ bottles, not just a hardcoded 20.)

Think About the Solution

To build a clean, production-grade simulation of this problem, we need to design a few key components:

• PillBottle: A class representing a bottle, holding its index, the weight of its individual pills, and the current stock of pills.
• Scale: A class representing our physical scale. It should expose a single method: weigh(List<Pill> pills). To enforce the constraint, we can implement a usage counter or design the API such that it is clear we only invoke it once.
• HeavyBottleDetector: The orchestrator containing our detection algorithm.

Edge Cases to Handle:

• Floating-Point Drift: In Java, double arithmetic like 210.7 - 210.0 can result in 0.6999999999999886 instead of 0.7. If we divide this by 0.1, we might get 6.999999999999886, which casts to an incorrect index of 6 instead of 7. We must use BigDecimal or a safe rounding mechanism to prevent this.
• Insufficient Pills: If a bottle does not have enough pills to satisfy the sample size, we must throw a clear, descriptive exception.

Write Code and Explain

Let's write the complete, self-contained Java implementation. We will use BigDecimal to ensure absolute mathematical precision, mirroring how a financial or high-precision scientific system would be built.

package com.thedevlearnings.puzzle;

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;

public class HeavyBottleDetector {

    // Domain model representing a single Pill
    public static class Pill {
        private final BigDecimal weight;

        public Pill(BigDecimal weight) {
            this.weight = weight;
        }

        public BigDecimal getWeight() {
            return weight;
        }
    }

    // Domain model representing a Pill Bottle
    public static class PillBottle {
        private final int id;
        private final BigDecimal pillWeight;
        private int pillCount;

        public PillBottle(int id, BigDecimal pillWeight, int initialPillCount) {
            this.id = id;
            this.pillWeight = pillWeight;
            this.pillCount = initialPillCount;
        }

        public int getId() {
            return id;
        }

        public List<Pill> dispense(int count) {
            if (count > pillCount) {
                throw new IllegalArgumentException(String.format(
                    "Bottle %d has insufficient pills. Requested: %d, Available: %d", 
                    id, count, pillCount
                ));
            }
            List<Pill> dispensed = new ArrayList<>();
            for (int i = 0; i < count; i++) {
                dispensed.add(new Pill(pillWeight));
            }
            this.pillCount -= count;
            return dispensed;
        }
    }

    // Scale simulator enforcing the single-use constraint
    public static class AnalyticalScale {
        private boolean hasBeenUsed = false;

        public BigDecimal weigh(List<Pill> pills) {
            if (hasBeenUsed) {
                throw new IllegalStateException("Security Violation: Scale can only be used once!");
            }
            hasBeenUsed = true;

            BigDecimal totalWeight = BigDecimal.ZERO;
            for (Pill pill : pills) {
                totalWeight = totalWeight.add(pill.getWeight());
            }
            return totalWeight;
        }
    }

    /**
     * Detects the ID of the heavy bottle using a single scale measurement.
     * 
     * @param bottles List of pill bottles
     * @param scale The analytical scale
     * @return The ID of the heavy bottle
     */
    public int detectHeavyBottle(List<PillBottle> bottles, AnalyticalScale scale) {
        if (bottles == null || bottles.isEmpty()) {
            throw new IllegalArgumentException("Bottle list cannot be empty.");
        }

        List<Pill> scalePan = new ArrayList<>();
        int expectedPillCount = 0;

        // Step 1: Collect 'i' pills from the i-th bottle (1-based indexing)
        for (int i = 0; i < bottles.size(); i++) {
            PillBottle bottle = bottles.get(i);
            int sampleSize = i + 1; // Bottle 1 gives 1 pill, Bottle 2 gives 2, etc.
            
            scalePan.addAll(bottle.dispense(sampleSize));
            expectedPillCount += sampleSize;
        }

        // Step 2: Perform the single allowed measurement
        BigDecimal actualWeight = scale.weigh(scalePan);

        // Step 3: Calculate expected weight if all pills were standard (1.0g)
        BigDecimal standardWeight = new BigDecimal("1.0");
        BigDecimal expectedWeight = standardWeight.multiply(BigDecimal.valueOf(expectedPillCount));

        // Step 4: Calculate the weight delta
        BigDecimal weightDelta = actualWeight.subtract(expectedWeight);

        // Step 5: Identify the heavy bottle index
        // Formula: Index = Delta / (Heavy Weight - Standard Weight)
        // Here, heavy weight is 1.1, standard is 1.0, so difference is 0.1
        BigDecimal weightDifferencePerPill = new BigDecimal("0.1");
        
        if (weightDelta.compareTo(BigDecimal.ZERO) == 0) {
            throw new IllegalStateException("No heavy bottle detected. All pills weighed exactly 1.0g.");
        }

        BigDecimal calculatedIndex = weightDelta.divide(weightDifferencePerPill, 0, RoundingMode.HALF_UP);

        return calculatedIndex.intValue();
    }
}

Code Walkthrough

Let's trace how this code executes and why it is robust:

1. Encapsulation and Safety: The AnalyticalScale class contains a boolean flag hasBeenUsed. If any developer attempts to call weigh() a second time, it throws an IllegalStateException. This strictly enforces our architectural constraint at runtime.
2. The Dispensing Loop: We iterate through our list of bottles. For each bottle at index i, we request i + 1 pills. If a bottle runs out of pills, bottle.dispense() throws an exception immediately, preventing silent failures.
3. Precision Arithmetic: Instead of using double, we use BigDecimal initialized with string literals (e.g., new BigDecimal("1.0")). This prevents the JVM from introducing binary floating-point approximations.
4. The Division: We divide the weightDelta by 0.1 and use RoundingMode.HALF_UP with a scale of 0. This guarantees that even if there were microscopic physical variations in pill weights, the system would round cleanly to the nearest integer bottle ID.

Time & Space Complexity

Let's analyze the algorithmic complexity of our solution. Let $N$ be the number of bottles (in this case, 20).

• Time Complexity: $O(N)$. We must loop through all $N$ bottles to extract the samples. The mathematical calculation after weighing is $O(1)$. Thus, the overall time complexity to prepare and solve the puzzle is linear relative to the number of bottles.
• Space Complexity: $O(N^2)$ in terms of individual physical pill objects stored in memory. Since we collect $\frac{N(N+1)}{2}$ pills, the space complexity scales quadratically with the number of bottles. For $N = 20$, this is only 210 objects, which is negligible. However, if $N$ were $1,000,000$, we would need to optimize this by representing the sample collection as a metadata map rather than instantiating individual physical objects.

Why This Problem Matters (The Senior Perspective)

At first glance, this looks like a clever math trick you only use to show off in interviews. But as senior engineers, we must look deeper. The core pattern here is Single-Pass Weighted Aggregation.

This pattern is highly relevant in several real-world architectural domains:

1. Error-Correcting Codes and Checksums

In networking and data storage, we use similar mathematical approaches to detect and correct errors. For example, a checksum or a Hamming code combines data bits using specific mathematical weights. When a corruption occurs, we don't scan every bit one by one. Instead, we compute the syndrome (the difference between expected and actual checksums), which points directly to the corrupted bit index. This is exactly what we did with our pill weights!

2. Distributed Telemetry and Anomaly Detection

Imagine you have 100 microservices reporting metrics to a central aggregator. Instead of querying each service individually (which is slow and expensive), you can assign a unique prime number or weight to each service's metric payload. When you run a single aggregated query, the resulting composite value can be mathematically decomposed to identify exactly which service is experiencing an anomaly.

3. Load Balancing and Weighted Round Robin

Understanding how to distribute and reconstruct state using mathematical weights is fundamental to designing advanced load-balancing algorithms and traffic-shaping policies in high-throughput systems.

Final Thoughts

We solved the Heavy Pill puzzle not just by memorizing a riddle, but by treating it as a software engineering design challenge. We identified the core constraint, designed a strategy to encode identity into a single scalar measurement, and implemented a production-grade Java solution that handles real-world floating-point issues gracefully.

Next time you are faced with a strict constraint in your system design, ask yourself: "How can I encode more information into my existing data channels to avoid extra round-trips?"

What did you think of this approach? Have you ever used weighted aggregation to debug a production system? Let's discuss in the comments below!

Happy coding, and see you in the next post!