We use cookies to personalize content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners. By clicking "Accept Cookies," scrolling this page, clicking a link or continuing to browse otherwise, you agree to the use of cookies. Privacy and Cookie Policies
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.
You're in!
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 sortedarray in O(lg(n)) time.
A brute force search would walk through the whole array, taking 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:
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.
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.
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:
intbinarySearch(int target,constint*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 presentwhile(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){return1;}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;}}return0;}
How did we know the time cost of binary search was 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 (n) in half until we get down to 1?"
n∗21∗21∗21∗21∗...=1
How many 21's are there? We don't know yet, but we can call that number x:
n∗(21)x=1
Now we solve for x:
n∗2x1x=1n∗2x1=12xn=1n=2x
Now to get the x out of the exponent. How do we do that? Logarithms.
Recall that log10100 means, "what power must we raise 10 to, to get 100"? The answer is 2.
So in this case, if we take the log2 of both sides...
log2n=log22x
The right hand side asks, "what power must we raise 2 to, to get 2x?" Well, that's just x.
log2n=x
So there it is. The number of times we must divide n in half to get down to 1 is log2n. So our total time cost is 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
Actually, we don't support password-based login. Never have. Just the OAuth methods above. Why?
It's easy and quick. No "reset password" flow. No password to forget.
It lets us avoid storing passwords that hackers could access and use to try to log into our users' email or bank accounts.
It makes it harder for one person to share a paid Interview Cake account with multiple people.
“I was able to binge-learn the patterns of coding interviewing questions through Interview Cake really easily. It is by far the most well-organized site that I've found. 100% worth the investment!
—
Joshua