[Challenge] Egg Dropper đŸ„š

HQ Announcements & Events
1

Code Challenge #17: August 2, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Microsoft:

Basic Difficulty

Suppose that you had 100 eggs in a 100-floor skyscraper, and you wanted to conduct an experiment to find out the highest floor (criticalFloor) from which you could drop an egg without breaking it
 but you’re also really hungry so you don’t want to waste any eggs.

Write a function, minEggDropper100, that will determine the minimum number of egg drops (minDrops100) you’d need to find the criticalFloor.

  • Function Name: minEggDropper100
  • Output: minDrops100 – an integer representing the minimum number of drops needed to find the criticalFloor
  • An egg that survives a fall can be used again.
  • A broken egg must be discarded.
  • The eggs are all incredibly similar – the effect of a fall from a particular floor is the same for all eggs.
  • If an egg survives a fall from floor n, then it would also survive a fall from the floors below it: floor n-1, floor n-2, etc.
  • If an egg does not survive a fall from floor n, then it would also not survive a fall from the floors above it: floor n+1, floor n+2, etc.
  • You should not presume that an egg would survive a fall from the first floor, nor should you presume that it would not survive a fall from the 100th floor!
  • Much of the challenge in this problem is in formulating your strategy for egg dropping – interviewers want to see how you think in breaking down and solving this problem. Perhaps consider first how you would solve this problem with only one egg. Then think how you’d solve this problem with infinite eggs without any code. After that, think how you can use coding to find criticalFloor more efficiently.
    • Remember: the challenge is not to find criticalFloor itself! Your function should return the minimum number of egg drops you need to find criticalFloor.
  • Try not to Google for help or check other responses online for solutions or help – see how you can solve this problem yourself!

Don’t forget: you must explain your thought processes and solution!

Find out more about basic challenges.

Intermediate difficulty

You’re at another 100-floor skyscraper and want to perform another experiment but this time you have only two eggs.

Write a function, minEggDropper2, that will determine the minimum number of egg drops (minDrops2) you’d need to find the highest floor (criticalFloor2) from which you could drop an egg without breaking it.

  • Function Name: minEggDropper2
  • Output: minDrops2 – an integer representing the minimum number of drops needed to find criticalFloor2
  • Don’t forget to explain your work!
Find out more about intermediate challenges.

Hard Difficulty

Write minEggDropperX that will test for x many eggs and y many floors. Please write this as efficiently as possible!

  • Don’t forget to explain your work!
Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, it is vital that you walk us through your thought processes, including how you made your strategy for testing egg dropping. As always, please abide by our other simple rules.

As is the case in interview settings, solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.

The fine print:

Click the links to find out more about:

2

Basic / Intermediate / Hard Challenge Python 3.6 -

def minEggDropperX(y, x=0):
    if(x <= 0 or y <= 0):
        return inf
    floors = y      # Number of floors
    minDropsX = 0
    eggs = x        # Number of eggs
    while eggs > 2:    # Divide the floor from middle in two parts for each egg untill two egg remains
        floors //= 2
        eggs -= 1
        minDropsX += 1
        if floors == 0:  # If all floors are checked, return number of drops
            return minDropsX
    minDropsX += (floors+eggs)//eggs if eggs == 2 else floors//eggs     # Dropping egg from floors in the increment of number of remaining eggs
    return minDropsX   # Number of drops until reached critical floor

https://repl.it/JuDA/9
Please open the above link to find complete script.
Use below link to see the process :-
https://repl.it/Jutc/9

EDIT :
Removed Basic challenge and added Hard.
Added another python programme(extra) to show the process.

EDIT 2:
Improved both the programmes further and made efficient.

1 Like
3

Hey @star3lord, don’t forget to explain your work! Submissions with code alone and no explanation aren’t eligible to win.

1 Like
4

Yeah sorry about that, it was late night here so I just quickly posted the basic challenge (cause I wanted to be the first one :wink: ). I will edit it with all explained challenges.

2 Likes
5

repl https://repl.it/JveD

import random

# I'm using a divide and conquer technique to search for the critical floor. We consider the floors a range from
# [lowest_floor : highest_floor]. We then drop an egg from the middle floor and see if it breaks. If it doesn't,
# we now know we have to look for the critical floor in [middle_floor : highest_floor]. If it does break, it's the
# other half [lowest_floor : middle_floor]. In a recursive process we keep narrowing down the test range until
# we find the critical floor.

# each time an egg breaks, we subtract 1 from the egg_pool


def minEggDropper100() -> int:

    num_floors: int = 100
    egg_pool: int = 100
    num_drops: int = 0

    # A random critical floor each time the function runs, so we have something unknown to search for
    critical_floor: int = random.randrange(1, num_floors + 1)

    # setting up the initial full range test window
    test_window = [1, num_floors]

    print('floors to test: %s' % test_window)
    print('--------------------------------')

    while True:
        # if we are out of eggs for testing, we can't go on
        if egg_pool == 0:
            print('Oh no! We are out of eggs :(')
            break

        num_drops += 1

        # handling cases between the first and last floor
        if test_window[1] > 2:
            middle_floor = int((test_window[0] + test_window[1]) / 2)

            # testing if the egg breaks or not

            # egg broke
            if middle_floor >= critical_floor:
                # narrowing down the test window
                test_window[1] = middle_floor
                egg_pool -= 1

            # egg didn't break
            else:
                # narrowing down the test window
                test_window[0] = middle_floor

        # special handling of lowest floors
        elif test_window == [1, 2]:

            # when we are down to floor 1 and 2, we check if the egg breaks at floor 1. If it does, we know the
            # critical floor is floor one. If it doesn't, we know it's floor 2
            if critical_floor == 1:
                test_window[1] = 1
                egg_pool -= 1
            else:
                test_window[1] = 2

            break

        print('%s Current testing window: %s' % (num_drops, test_window))

        # loop breaking logic
        if test_window[1] - test_window[0] <= 1 and test_window[1] > 2:
            break

    print()
    print('Critical floor suggested : %s' % test_window[1])
    print('Critical floor revealed  : %s' % critical_floor)
    print()
    print('Eggs left for eating: %s' % egg_pool)

    return num_drops


print('Num egg drops: %s' % minEggDropper100())


""" printed output for critical floor 31 """
floors to test: [1, 100]
--------------------------------
1 Current testing window: [1, 50]
2 Current testing window: [25, 50]
3 Current testing window: [25, 37]
4 Current testing window: [25, 31]
5 Current testing window: [28, 31]
6 Current testing window: [29, 31]
7 Current testing window: [30, 31]

Critical floor suggested : 31
Critical floor revealed  : 31

Eggs left for eating: 97
Num egg drops: 7
2 Likes
6

Minimum number of eggs required to find CriticalFloor is 1: starting from the 1st floor till an egg will brokes. So number of drops is equal to the given number of floors.
If there is one more egg, we can split a skyscraper dropping an egg from the middle. Now with one egg left we can find CriticalFloor checking only half of a skyscraper.
If there is one more egg, we can split a skyscraper again
 only quarter of a skyscraper left.

Here is Python 3 code:

def minEggDropperX(y, x=1):
    eggs_left = x
    # split floors until we have more than 1 egg and more than 1 floor
    # add ground-floor, because decision space is [0:y]
    floors_left = y+1
    while (eggs_left > 1) and (floors_left > 1):
        eggs_left -= 1
        floors_left = (floors_left+1)//2
    
    # here we made (x - eggs_left) drops
    # we have at least 1 egg to complete an experiment
    # remove ground-floor, we are checking all (floors_left) explicitly
    drops = x - eggs_left + floors_left - 1
    return drops

print(minEggDropperX(100, 100))
print(minEggDropperX(100, 2))

https://repl.it/Jvrz/2

2 Likes
7

Is splitting 50/50 really ideal if you have two eggs? minEggDropperX(100, 2) would need as many as 50 drops in a worst case scenario, if CriticalFloor = 49. Since losing your second-to-last egg is very costly (you have to switch to testing every single possible remaining floor until the last egg breaks) you want to use it somewhat conservatively.
Just transitioning to a 33/67 split improves your results tremendously (worst case 33 egg drops), and there are further gains to be made.

3 Likes
8

I have attempted to solve this problem using a mathematical rather than a recursive method.

I needed to import the math library to be able to find logs and roundup numbers. I hope this is not against the rules!

Code with embedded explanation is here:

def minEggDropperX(floors, n):
  import math    #needed for find logarithms as well as for rounding up functions
  drops: float
  
  drops = math.ceil( math.log(floors+1) / math.log(2))  #with each egg drop we divide by two the number of floors on which the  critical floor might be. Number of drops required is found when: (no. of floors) / 2**(no. of drops) is less than 1

  if drops > n:   #if there are not enough eggs available for the above method then...
    drops = math.ceil(floors / 2 ** (n - 1))  #we keep halving the number of floors by droping eggs until we have 1 egg
                                              #left. 
    drops = max(drops - 1, math.ceil(floors / 2 ** (n - 2) - drops)) #This egg is then used to test each floor inbetween
                                                                     #the two levels established above. 
    drops = drops + n - 1       #answer is the sum of the intital n-1 drops and the number of incremental egg drops
  return drops

print(minEggDropperX(100, 100))
print(minEggDropperX(100, 2))
print(minEggDropperX(1000, 7))

https://repl.it/JwzD/3

9

Good thought, maybe there is better solution


10

Spot on 50/50 (a.k.a a binary search) is not the most efficient way to solve this.

3 Likes
11

Good point. I have failed to pick up on an all important point in the brief:

“An egg that survives a fall can be used again.”

Try again


12

Here is the my take on the Intermediate difficulty challenge.

The idea is similar to last week’s challenge in using dynamic programming.

def minEggDropper2(x):
    minEggDrops_with_1_egg = list(range(x+1))
    minEggDrops_with_2_egg = list(range(x+1))

    for i in range(2, x + 1):
        floorsBr = minEggDrops_with_1_egg[:i]; #Case egg breaks
        floorsBd = minEggDrops_with_2_egg[:i][::-1]; #Case egg don't break
        minEggDrops_with_2_egg[i] = 1 + min(map(max, zip(floorsBr, floorsBd)))
        
    print('minEggDrops_with_2_egg =', minEggDrops_with_2_egg)
    print('')
    print('minDrops2 =', minEggDrops_with_2_egg[-1])
    
minEggDropper2(100)

The link below has full explanation as well as the code.
https://repl.it/Jxy5/2

13

Well, I tried my best. Here is my solution. https://repl.it/Jy4o/1

Please let me know how I can improve my code. Thanks!

14

So, my previously posted solution is far from to be optimal, here is new:

While we have more than 2 eggs - use binary search (as it was), it’s the fastest way to reduce number of floors.

If we have only 2 eggs and X floors to check - use split jumps
The strategy of jumps
step1: ‘jump’ through H-1 floor and drop an egg (if it was 1st floor, drop from Hth floor);
step2: if we loose it - we have 1 egg and H-1 drops to check H-1 floors (total H drops); else we have 2 eggs, X-H floors and H-1 drops;
step3: repeat from step1 with reduced number of floors and jump size decreased by 1.

Each subsequent jump will be 1-floor smaller than previous
Floor afther i jumps: start + (H-1)+1 + (H-2)+1 + (H-3)+1 + 
 + (H-i)+1
Using arith. progression formula we can find last floor after jumps: (H-1)(0.5xH + 1) - compare it with number of floor and find number of drops for supposed H.
Check possible H and select best.

P.S. subject to further optimization - if my rough calc are not bad, best H is near SQR(2*number of floors)

Python3: https://repl.it/Jvrz/7

def minEggDropperX(y, x=1):
    # binary search with more than 2 eggs
    eggs_left = x
    floors_left = y
    while (eggs_left > 2) and (floors_left > 2):
        eggs_left -= 1
        floors_left = (floors_left)//2

    # drops made
    drops = x - eggs_left

    # subroutine to calc number of drops for 2-eggs search
    def egg2_drops(n, s):
        # n - number of elements (floors)
        # s - 1st split size
        return max(s, n + int(s-0.5*s*(s+1)))

    # 2eggs split search
    if (floors_left > 2) and (eggs_left > 1):
        egg2_vars = [egg2_drops(floors_left, H) for H in range(2, (floors_left+1)//2+1)]
        drops += min(egg2_vars)
    else:
        # trivial cases: 1 egg or 1 or 2 floors    
        drops += floors_left;
    return drops

print(minEggDropperX(100, 100))
print(minEggDropperX(100, 2))
print(minEggDropperX(7, 2))
print(minEggDropperX(7, 3))
15

Intermediate difficulty

We have to divide the 100 floors in n parts. The egg1 will be dropped from 100/n floor,
if it doesn’t break, it will be dropped from 2*(100/n) floor etc.

When the egg1 breaks, let this floor m*(100/n). Then we have to drop the egg2 from the (m-1)(100/n)+1, if it doesn’t break we drop it from the (m-1)(100/n)+2 floor
 etc.

To tell what is the optimum of n, we have to find where is the minimum of this function:
(100/n)+(n-1). After derivate we get n=10.

So we drop the egg1 from the 10. floor, if it doesn’t break, from the 20. floor, etc.
When it breaks, ie. from the 20. floor, we drop the egg2 from the 11., 12.
13. etc. In the worst case it will break in the 99. floor. In this case we dropped 19 times. (egg1: 10,20,30,40,50,60,70,80,90,100, egg2: 91,92,93,94,95,96,97,98,99)

16

I’m late to this challenge, but I wanted to post my solution too. Here it is https://repl.it/KHL9/9

public class Main
{
  static int criticalFloor = 30;
  
  public static void main(String[] args)
  {
    System.out.println(minEggDropperX(5,100));
  }
  
  public static int minEggDropperX(int x, int y)
  {
    int testCount = 0; // number of drops needed to identify the critical floor
    int pow = 0;
    int lastGoodFloor = 0, lastBadFloor = 0; // stopping condition is when lastBadFloor = lastGoodFloor + 1
    int currentFloor = 0;
    while(x > 0)
    {
      currentFloor += (int)Math.pow(x,pow); // choose a new floor to test
      if(currentFloor > y) // avoid testing floors that don't exist
      {
        currentFloor = y;
        pow --;
      }
      testCount ++;
      
      if(currentFloor > criticalFloor) // the egg breaks
      {
        lastBadFloor = currentFloor; // update the value of the last floor on which an egg broke. it will always be less than its previous value.
        currentFloor = lastGoodFloor; // go back to the last floor where an egg didn't break
        x --; // now there is one fewer egg
        pow --; // decrement the power to lower the risk of losing eggs.
      }
      else //the egg does not break
      {
        lastGoodFloor = currentFloor; 
        pow ++; // increment the power to reach the critical floor faster
      }
      if(lastBadFloor - lastGoodFloor == 1 || lastGoodFloor == y || lastBadFloor == 1) // the critical floor should be lastGoodFloor
        return testCount;
    }
    return -1; // this should not ever happen.
  }
}

My solution is inspired from the slow start method for congestion control by TCP that I learnt in a networking class.
I applied that with some modifications though.
My solution finds the critical floor by finding two successive floor where the egg breaks on one (lastBadFloor) and survives on the other one (lastGoodFloor).
I start by testing floor 1, and then test higher floors in leaps that are increasing powers of the number of remaining eggs until an egg breaks, then it goes back to the lastGoodFloor and continues the test with one fewer egg. The test also stops if the eggs don’t break on the highest floor or break on the first floor.
I think that this solution uses a lot of eggs, but at least the number of tests is low.
I hope the explanation was clear enough and would be happy to hear any suggestion that could improve the solution.

1 Like
17

I have started completely again since my last (flawed) effort. My new code determines the maximum number of floors that can be tested with any given combination of eggs and drops. When the number of testable floors exceeds the number of floors for the problem in question then the answer presents itself.

The method of solving is more thoroughly explained within the code in the below link

https://repl.it/KHKL/14

def minEggDropperX(floors, n):

  drops = [[0 for x in range(0,n+1)]for y in range(0,25)]  #the zero column of the array will store the sum of the previous results for each row. This figure is required to calculate the number of floors that can be tested  with sucessive number of eggs
  
  for b in range(1,25):
    for egg in range (1,n+1):
      drops [0] [egg] = drops [0] [egg]  + drops [b - 1] [egg]
      if b==1:   #one drop means one testable floor irrespective of the no. of eggs
        drops[1][egg]=1
      if egg==1: #for 1 egg the number of drops is equal to the number of floors that can be tested. This gives us a foothold for the subsequent calcs.
        drops[b][egg]=b 
      else:
        drops[b][egg] = drops[0][egg-1] + b # ta-da!!

    if drops[b][n] >= floors:  #the number of drops is now sufficient to test all the floors required so let's store the answer and stop our loop.
      answer = b 
      break

  return answer
  
print(minEggDropperX(100, 100))
print(minEggDropperX(100, 2))
print(minEggDropperX(1000, 4))
print(minEggDropperX(7654, 7))
18

Just curious, can you show the process of egg drop for 100 floors and 2 eggs with 57(just as an example) being the critical floor ?
I didn’t understand your approach to the problem so please explain with an full example.

You can take a look at my solution process here - https://repl.it/Jutc/9

19

The approach is the same irrespective of the critical floor (out of
necessity as we don’t know what it is!). Anyway, for the scenario of 100
floors and 2 eggs the first drop is from floor 14. If the egg breaks then
we know the critical floor is below but we only have a single egg left so
we have no choice but to test from floor 1 and work our way up. In the
worst case of the critical floor being 13 then we would have performed 14
total drops before this is established. If the egg had survived the first
drop then we still have 2 eggs left so we take our next drop at floor 27
(i.e. 13 floors further up) - if it smashes we use the final egg to test
the 12 floors between 15 and 26 (so again, upto 14 drops total). If the egg
survived the second drop at floor 27 we reuse this egg and drop from
floor 39 (i.e 12 floors further up). We carry on in this manner reducing
the floor increment by one each time to account for the fact that we have
one less drop available.

If in our example, the critical floor was 100 and thus our eggs kept
surviving the falls then the sequence of drops would be at floors:
14,27,39,50,60,69,77,84,90,95,99,100

But, you might say “that’s only 12 drops and your algorithm says the
minimum number of egg drops is 14!”. So what’s going on here?

Well actually, in my opinion, the title of minimum egg dropper is slightly
misleading. What we are actually trying to find out is the maximum number
of egg drops that would be required if you used the optimum testing method.
If you think about it, the minimum egg drops required for any problem is
just two - but this would require that the dropper is lucky enough to take
the 2 drops - on and immediately below the critical floor. I guess another
way to think of it is - the minimum number drops that is guaranteed to
reveal the critical floor (provided you follow the prescribed method).

So returning to our problem with 100 floors and 2 eggs. We have shown that
we can definitely find the critical floor if we take 14 drops. Now we need
to show that 13 drops is not sufficient. Using the same method as before
and if again we say that the critical floor is 100 then our drops would be
on the following floors:

13,25,36,46,55,63,70,76,81,85,88,90,91

Ah! So here we have taken 13 drops but we have only narrowed down the
possibilities to within 9 floors (92 to 100). Therefore the 14 drop method
is the minimum that is guaranteed to find the critical floor.

Just briefly returning to you example of the critical floor at 57 the
testing sequence would be

14,27,39,50,60s,51,52,53,54,55,56,57s = 12 drops (the ‘s’ suffix denotes a
smashed egg).

So this only required 12 drops. However, this does not mean the answer is
12 because this method might require 14 drops if the critical floor was
elsewhere (floor 59 for example).

Hope that helps


3 Likes
20

That is a ■■■■ good solution. And you explained quite well.