Adobe Interview Question
Member Technical StaffsTeam: Illustrator
Country: India
Interview Type: In-Person
How can you say that doubling floors each time is optimal solution ??
We can triple floors each time also...
For finite floors we can do load balancing as you have described...
but for infinite floors how can we do load balancing ?
@Nitin
Nice. I actually start to think that the question is ill-posed, for the following reason: we need to know the probability distribution for the breaking-egg drop-height in order to optimized the search process. In the finite number (N) of floor case the implicit assumption is that (I think) any number ranging between 1 to N is equally probable. However in the infinite number of floor case the "equal probable" assumption does not apply any more since it cannot be give a well-defined probability distribution density that sums up to 1. Having said this, I think the most probable interpreting of the problem is that "for any given and finite N, how to determine the breaking-egg drop-height". For this I do believe that except for extremely small N, the doubling scheme is better than the tripling scheme, since after you have broken the first egg which requires O(lg(N)) tries, you need to do a linear search using the (only left) second egg, which requires O(a^(i+1)-a^i) tries, with a being 2 or 3, but a=3 has a much larger "gap" to be filled than a=2.
The question is not ill-posed. Think of it like this: suppose you don't know the maximum floor number or anything about the probability distribution, but you want to give the best bound on the worst-case number of drops, expressed in terms of N where N is the lowest floor on which an egg breaks.
For example, using only the first egg and searching floors linearly is O(N). In that strategy, we would drop the egg from the 1st floor, then 2nd, then 3rd, and so on, and we stop when we reach the N-th floor and the egg breaks. We now know the answer is N, and it took us N drops to find out. We didn't need to have any upper bound on the answer to execute this strategy.
The strategy where we binary search with the first egg and then linearly search with the second afterwards is also O(N) in the worst case (the linear search could be expensive). The question would be asking about whether we can give better bounds, even if we don't know how large N will end up being.
Call the floor where the edge break is m.
The sub-optimal solution for the infinite problem for two eggs is to use the sequen 1, 2^2, 3^3, ,i^2, ... and start the second edge where the last value the first egg remains. So if the first edge remains at n^2, then the next one will do at most 2*n + 1 - 1 (minus 1 from the first) test to give the total of 3 * n in the worst case with n = sqrt(m). This is much better bound than the doubling strategy that result in log(m) + m/2 = 0(m) in the worst case.
The optimal solution if the number of floor is known is pointed out by PKT, but he is wrong in the first case
If n is finite and known, if you move in steps of sqrt(n) then when the first egg breaks, you are within sqrt(n) of the solution. Switching to linear with the second egg gets you there in less than sqrt(n) for an O(sqrt(n)) solution.
If N is unknown the worst case is O(n) since we cannot guess sqrt(n). Maybe some math gymnastics with limits can handle the case where n is an infinite but known quantity to give O(sqrt(n)).
isn't this a simple case of binary search? i.e search the right floor from where the egg will break?
so the complexity is log n (base 2)?
2 eggs and infinite floors can be solved like below I guess,
1) Lets say we have started from 10th floor
2)If the egg is not broken then go to 20th floor and continue by inreasing 10 floors
3) suppose if the egg breaks at 100th floor, then you can find the floor with the second egg in maximum 9 tries.
4) here the solution will be x+9 tries. , x is the number of tries to break the first egg.
5) Still generalised solution is x + (m-1), m is the number floors to increase each time and x is the number tries to break the first egg.
thanks. What will be the optimal value of m so that we have minimal number of tries for finite floors say 100.
Logic for infinite case:
as we dont know the no of floors and it is about infinite....
drop egg from 1st floor then
drop egg from 2nd floor then
drop egg from 4th floor then
drop egg from 8th floor then
double the no of floor each time.... where ever it got break... start dropping egg in sequence from previous non breakable floor.
@PKT: read my comment to masterjaso's answer. Your approach has the same issue of taking O(n) drops, where n is the answer. The initial binary search is not particularly effective because we end up having to do a potentially long linear search with the second egg afterwards.
@yarovoi: yeah.. u r right.....but...that's all I could think of it...... drop egg exponentially first and where ever got broken... start dropping sequentially from previous non breakable floor.
complexity is defiantly better then O(n)
Any sol for infinite no. of floors better then this is most welcome if possible.
With just one egg, we have to throw it at the highest floor it doesn't break to be sure about it. So, we can't skip floors because if it breaks, we don't know anything about the floors we skipped.
I don't see how you can do better with just one egg. Maybe the interviewer wanted you to justify properly why you can't optimize it further.
The best solution would be to go through fibonaacy sequence ...let me explane
drop egg at 1,2,3,5,8,13,21,34 etc until the first egg breaks
So the key to this question lies in the number of eggs you have to try.
Let's start with a brute force method:
1. Starting at ground floor (if it breaks, there is no answer)
2. Increment floors by the number of eggs you have
3. Repeat until your egg breaks
4. If you have eggs left go back to the last floor that didn't break eggs and increment by one until you find the first floor that causes a break.
5. MaxFloorWithoutBreakage = CurrentFloor - 1
So the running time of this algorithm is linear O(n/e) where e is the number of eggs you have.
To make this more efficient, you could make the assumption that eggs are always 2 or more at the start of the experiment. Then as long as you have 2 or more eggs, you do a binary search. This effectively cuts the number of available floors in half each time until you reach your final egg. On your final egg, you go back to your last 'safe' floor and start incrementing by 1 until it breaks.
In this instance the worst case is still O(n/2 - 1), but the average running time (assuming the break point is a different floor each time) becomes O(log n).
For the bonus round, if you actually code this in a sorted array that represents the floors, this also has a O(n) space complexity, which means it can run in place.
I would say that both the average and worst-case runtimes are O(n) for your solution. There is no guarantee the egg will break anywhere near the floors you know about from your binary search.
Let's say that you break your first egg finding out the egg doesn't break at floor m/2 and breaks at floor m. You now have no idea where it breaks between those two points, and since you only have one egg left, you'll have to try the remaining floors one-by-one. Considering an "average" case, it's just as likely to break only when you get to the higher end of that range as it is to break when you're at the lower end. The probability of it breaking at > 3m/4 would be 1/2, so there's a 1/2 probability you need to do more than 3m/4 - m/2 = m/4 drops. The expected runtime is therefore at least 1/2 * m/4 = O(m).
If we are given 2 eggs only, then yes you will encounter a linear search after the first one breaks, as when you get down to 1 egg, you can only find the best floor by going 1 floor at a time. But as long as you have 2 eggs or more, you can always binary search.
If you read my assumptions, it shows that I am assuming 2 'or more' eggs for the optimal search using the binary method (divide remaining possible floors in half and checking the mid-point). This solution works best for infinite number of eggs though.
Ultimately the most correct answer for 2 eggs and infinite floors was actually provided by PKT with the triangular number solution: t(t+1)/2 throws. The trick here is determining the proper number of floors to skip with each toss. In the case of the above formula t(t+1)/2, this quadratic equation. To minimize our number of throws, we must calculate the positive root for our quadratic equation. At each attempt thereafter, we reduce the number of floors we skip by 1. This means we eventually reduce our number of throws to a linear search at the very end, or only when we have found our first floor with a break. This ensures that you have ever decreasing gaps to minimize the number of linear attempts you have to make as you get to higher floors, but does increase the number of attempts it takes on the lower floors.
@masterjaso: The binary search strategy works if you have about 2*log N eggs, where N is the floor to be found. Otherwise, it is not optimal. That's the point I was trying to get across.
If you only have 2 eggs, binary searching with the first egg gives you an algorithm that is O(N) on average, since the linear search with the second egg will consume a lot of time. In the average case, the binary search is not asymptotically better than using only one egg and doing a linear search from the start -- it is only a constant factor better.
Since the number of floors, N is infinite, we can't quantify the optimal number of throws in terms of N, but can only specify a strategy.
Logic for infinite case:
- PKT July 20, 2013as we dont know the no of floors and it is about infinite....
drop egg from 1st floor then
drop egg from 2nd floor then
drop egg from 4th floor then
drop egg from 8th floor then
double the no of floor each time.... where ever it got break... start dropping egg in sequence from previous non breakable floor.
Logic for given no pf floors: (optimal sol)
drop egg from xth floor then
drop egg from (x)+(x-1) floor then
drop egg from (x)+(x-1)+(x-2) floor then
drop egg from (x)+(x-1)+(x-2)+(x-3) floor then
drop egg from prev floor+(x-3) floor then
..
..
drop egg from prev floor+1) floor.
in case egg broke in any floor mentioned above.. start dropping eff in sequence from prev non breakable floor.
lets calculate value of optimal x:
x + (x-1) + (x-2) + (x-3) + ...... 2 + 1 = no of floors
x(x+1)/2 = no. of floors
for no. of floors = 10
x = 4 in worst case we need only 4 drops.