Safenet Interview Question
Software Engineer / DevelopersI am copying here a solution from a website:
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
But, i am still confused, about how the climb rate be decided.
252 DROPS. What I do is start drop the egg at 1st floor. If not break, go to 8 floor and drop it. If not break go to floor 9th and drop, got 16 and drop if it survive the 9th floor. If it break at 8x floor then dthis mean somewhere between 8(x-1) + 1 and 8x be the limit. Go down to 8x - 4 to drop the second egg. If break, down to 8x - 4 -2 floor and drop your last egg. This mean for every 8 floor we drop 2 times 8x and 8x + 1 for x=0,...,124. so it is 125x2 + 2 = 252 drops.
45 drops would be required for a 1000 storied building
N(N+1)/2 >= 1000
For instance take a 100 storied building
the no of drops required would be 14
Drop Floor
#1 14
#2 27
#3 39
#4 50
#5 60
#6 69
#7 77
#8 84
#9 90
#10 95
#11 99
#12 100
Hence worst case drop would be 14
Similarly for 1000 floors , worst case drop would be 45
Whereas if we have 3 eggs then the min no of drop would be 19
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
I found it in a link..but I can't understand it...pls someone explain..
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
I found it in a link..but I can't understand it...pls someone explain..
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
I found it in a link..but I can't understand it...pls someone explain..
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
I found it in a link..but I can't understand it...pls someone explain..
With a 1000 story building and three eggs the approach is
the same: You want a climb rate that reduces the required
number of drops by one each time you take a drop until you
reach the lower limit. It seems clear (I wish I could tell
you why it's clear - this is why I could never be a teacher)
that the step rate will be equal to the summation. The sum
of the sums that is equal to or more than 1000 is for n = 18
(it's actually the sum of the sums plus n). So the answer
is 19 drops:
Additional
Two Egg Drops if
Drop Building Egg Breaks Total
Floor Height (2 Egg Solution) Drops
172 171 18 19
326 153 17 19
463 136 16 19
584 120 15 19
690 105 14 19
782 91 13 19
861 78 12 19
928 66 11 19
984 55 10 19
1030 45 9 19
1067 36 8 19
1096 28 7 19
1118 21 6 19
1134 15 5 19
1145 10 4 19
1152 6 3 19
1156 3 2 19
1158 1 1 19
I found it in a link..but I can't understand it...pls someone explain..
First drop the egg from 500th level. If it breaks jump to 750 otherwise jump to 250.
- Anonymous June 26, 2011Do this repeatdily.