The Poor Pigs problem asks: given buckets buckets of liquid (one is poisonous), minutesToDie (time for poison to take effect), and minutesToTest (total test time), find the minimum number of pigs needed to identify the poisonous bucket. This hard coding problem has a surprising information-theoretic solution using base-(rounds+1) number systems. The math, combinatorics, and dynamic programming interview pattern is demonstrated.
Google asks this because the solution requires mathematical insight: each pig can test multiple rounds (rounds = minutesToTest / minutesToDie). In base (rounds+1) encoding, each pig can represent one "digit." The minimum pigs = ceil(log(buckets) / log(rounds+1)).
Information theory + base system. With rounds = minutesToTest // minutesToDie test rounds, each pig can encode rounds+1 states (it dies in round i, or survives all rounds). With p pigs, you can encode (rounds+1)^p distinct outcomes. Minimum pigs = smallest p where (rounds+1)^p >= buckets.
buckets=1000, minutesToDie=15, minutesToTest=60. rounds=60//15=4. Each pig encodes 5 states (die in round 1,2,3,4, or survive). With p pigs: 5^p ≥ 1000. 5^1=5, 5^2=25, 5^3=125, 5^4=625, 5^5=3125 ≥ 1000. Minimum = 5 pigs.
ceil(log2(buckets)) (only valid for 1 round).Poor Pigs is a brilliant information theory problem. The key insight: each pig encodes a "digit" in base (rounds+1). With multiple rounds, a single pig can distinguish many more outcomes than just "alive/dead." Practice similar information theory problems: "20 questions with limited guesses," "minimum coin weighings to find counterfeit coin." The formula ceil(log(N) / log(base)) solves all such "minimum tests to identify one out of N" problems.