You only have 3 free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

A building has 100 floors. One of the floors is the highest floor an egg can be dropped from without breaking.

If an egg is dropped from above that floor, it will break. If it is dropped from that floor or below, it will be completely undamaged and you can drop the egg again.

Given two eggs, find the highest floor an egg can be dropped from without breaking, with as few drops as possible.

Gotchas

We can do better than a binary

A binary search algorithm finds an item in a sorted array in O(lg(n))O(lg(n)) time.

A brute force search would walk through the whole array, taking O(n)O(n) time in the worst case.

Let's say we have a sorted array of numbers. To find a number with a binary search, we:

  1. Start with the middle number: is it bigger or smaller than our target number? Since the array is sorted, this tells us if the target would be in the left half or the right half of our array.
  2. We've effectively divided the problem in half. We can "rule out" the whole half of the array that we know doesn't contain the target number.
  3. Repeat the same approach (of starting in the middle) on the new half-size problem. Then do it again and again, until we either find the number or "rule out" the whole set.

We can do this recursively, or iteratively. Here's an iterative version:

  int binarySearch(int target, const int *nums, size_t numsLength)
{
    // see if target appears in nums

    // we think of floorIndex as leftmost edge of the possible positions
    // of our target and ceilingIndex as "wall" on the right of it
    size_t floorIndex = 0;
    size_t ceilingIndex = numsLength;

    // if there isn't at least 1 index between floor and ceiling,
    // we've run out of guesses and the number must not be present
    while (floorIndex < ceilingIndex) {
        // find the index ~halfway between the floor and ceiling
        // we use integer division, so we'll never get a "half index"
        size_t distance = ceilingIndex - floorIndex;
        size_t halfDistance = distance / 2;
        size_t guessIndex = floorIndex + halfDistance;
        int guessValue = nums[guessIndex];

        if (guessValue == target) {
            return 1;
        }

        if (guessValue > target) {
            // target is to the left, so move ceiling to the left
            ceilingIndex = guessIndex;
        }
        else {
            // target is to the right, so move floor to the right
            floorIndex = guessIndex + 1;
        }
    }

    return 0;
}

How did we know the time cost of binary search was O(lg(n))O(lg(n))? The only non-constant part of our time cost is the number of times our while loop runs. Each step of our while loop cuts the range (dictated by floorIndex and ceilingIndex) in half, until our range has just one element left.

So the question is, "how many times must we divide our original array size (nn) in half until we get down to 1?"

n12121212...=1 n * \frac{1}{2} * \frac{1}{2} * \frac{1}{2} * \frac{1}{2} * ... = 1

How many 12\frac{1}{2}'s are there? We don't know yet, but we can call that number xx:

n(12)x=1 n * (\frac{1}{2})^x = 1

Now we solve for xx:

n1x2x=1 n * \frac{1^x}{2^x} = 1 n12x=1 n * \frac{1}{2^x} = 1 n2x=1 \frac{n}{2^x} = 1 n=2x n = 2^x

Now to get the xx out of the exponent. How do we do that? Logarithms.

Recall that log10100\log_{10}{100} means, "what power must we raise 10 to, to get 100"? The answer is 2.

So in this case, if we take the log2\log_{2} of both sides...

log2n=log22x \log_{2}{n} = \log_{2}{2^x}

The right hand side asks, "what power must we raise 22 to, to get 2x2^x?" Well, that's just xx.

log2n=x \log_{2}{n} = x

So there it is. The number of times we must divide nn in half to get down to 1 is log2nlog_{2}n. So our total time cost is O(lg(n))O(lg(n))

Careful: we can only use binary search if the input array is already sorted.

approach, which would have a worst case of 50 drops.

We can even do better than 19 drops!

We can always find the highest floor an egg can be dropped from with a worst case of 14 total drops.

Breakdown

Start your free trial!

Log in or sign up with one click to get immediate access to 3 free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Solution

Start your free trial!

Log in or sign up with one click to get immediate access to 3 free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

What We Learned

Start your free trial!

Log in or sign up with one click to get immediate access to 3 free mock interview questions

Where do I enter my password?

Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?

  1. It's easy and quick. No "reset password" flow. No password to forget.
  2. It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
  3. It makes it harder for one person to share a paid Interview Cake account with multiple people.

Do you have an answer?

. . .