Adobe Interview Question for Member Technical Staffs


Team: Illustrator
Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 9 vote

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.

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.

- PKT July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 votes

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 Gupta July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@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.

- Chih.Chiu.19 July 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

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.

- eugene.yarovoi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
3
of 5 vote

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

- LinhHA05 July 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)).

- curios.N August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nevermind -- LinhH has a better O(sqrt n) solution above incrementing steps with i^2 to get the same result without the need to know n.

- curios.N August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)?

- game October 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no. first, we don't know "n" (infinite number of floors). second, if the egg breaks, we can't use it again, so it disqualifies binary search

- Miguel Oliveira October 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- anonymus July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks. What will be the optimal value of m so that we have minimal number of tries for finite floors say 100.

- Sandip Bhoir July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

@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.

- eugene.yarovoi July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- PKT July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Miguel Oliveira July 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- sarath s pillai July 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 4 votes

It is simply wrong, the function grows almost as fast as doubling function.

- LinhHA05 July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

Please, when you claim something that is not at all obvious, justify your answer. In trying to come up with a justification, you might discover that what you're claiming is not correct.

- eugene.yarovoi July 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

let nth be the floor where egg breaks.
so m=n/(least no divisible by n except 1).
Hence m is the minimal no of tries.

- manish27.p July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

- masterjaso July 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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).

- eugene.yarovoi July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I do agree with Eugene. But that's the best you can do. Do you have better idea?

- pavi.8081 July 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 July 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@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.

- eugene.yarovoi July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

In the case of real egg it should get broken falling from a table, shouldn't it?

- Anonymous August 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

what will be the optimized number of throws??

- Nitin Gupta July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Murali Mohan July 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good argument. Thumbs up!

- Murali Mohan July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

=> eugene.yarovoi

What's your solution then?

- Anonymous July 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More