A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

1. The subject

They also have buckets of liquid, and one of them contains poison and the others are water. They all look the same from the outside. To find out which bucket contains the poison, you can feed some pigs and see if they die. Unfortunately, you only have minutest minutes to determine which bucket of fluid is toxic.

The rules for feeding pigs are as follows:

  • Select a number of live pigs for feeding
  • Piglets can be allowed to drink any number of buckets of water at the same time, and the process does not take time.
  • Minudie must be given a minute cooldown after the pigs drink. During this time, you are only allowed to observe and not feed the pig.
  • Minudie: All the pigs that drink the poison are dead. All the other pigs live.
  • Repeat the process until time runs out.

You are given buckets, minutestdie, and minutest. return the minimum number of pigs needed to determine which bucket is toxic in the specified time.

Example 1: input: buckets = 1000, minutestdie = 15, minutesttest = 60 Output: 5 Example 2: input: Buckets = 4, minutestdie = 15, minutesttest = 15 Output: 2 Example 3: input: buckets = 4, minutestdie = 15, minutesttest = 30 Output: 2Copy the code

2.

For example:

Assumptions: Total time minutesToTest = 60, the time of death minutesToDie = 15, pow (x, y) x y power, ceil (x) x rounded up There is a pig, the current Can drink at most times = minutesToTest/minutesToDie = 4 times water can drink at most four times, capable of carrying the base = + 1 = 5 times the amount of information, which is readily understandable (start from 0) : (1) drink no. 0 dead, no. 0 bucket of water toxic (2) drink no. 1 dead, no. 1 bucket of water toxic (3) drink no. 2 dead, no. 2 bucket of water toxic (4) drink no. 3 dead, no. 3 bucket of water toxic (5) drink all the above water is still alive and jumping, no. 4 bucket of water toxic

The answer is 1 when the buckets are less than or equal to 5. So what is the maximum range that two little pigs can verify? We think of the information carried by each piglet as base, and the information carried by two piglets is POw (base, 2) = POw (5, 2) = 25, so when 5 ≤ buckets ≤ 25, anwser = 2. Then we can get the formula: POW (base, ANS) ≥ buckets. After the logarithm is taken, it is: Ans ≥ log(buckets)/log(base), because ans is an integer, so ANS = Ceil (log(buckets)/log(base))

So how does the pig feed the water? The following GIF shows the entire water feeding process:

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        int states = minutesToTest / minutesToDie + 1;
        return ceil(log(buckets) / log(states)); }};Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast