Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in C++

Solution: Poor Pigs

Understand how to use rounds of tests and distinguishable outcomes to calculate the minimum number of pigs required to identify a poisonous bucket. This lesson breaks down the logic of leveraging time constraints and probability concepts to efficiently solve the problem with constant time and space complexity.

We'll cover the following...

Statement

You have buckets buckets of liquid, exactly one of which is poisonous. Your goal is to identify the poisonous bucket by feeding liquid to some number of pigs and observing whether they survive or die. You have a total of minutesToTest minutes to determine which bucket contains the poison.

The experiment proceeds in rounds according to the following rules:

  • Select any number of live ...