Snapdeal Interview Question SDE1s
Country: India
Interview Type: Written Test
I think the answer is 24.
solve for integer k such that 150/k + k - 1 is minimum. k is 12 and min is 23.5 => 24
Divide 150 men into 12 groups of 12 people and the last group has 6 people. The worst case would be that he starts on the first group and then goes down all the way to the 12th group and the man said YES. Then he go to the start of the group and ask the rest of the 11 people. You can not do binary search because once there is a second YES, you are done done.
Let's say height of Blind man is 5.
people stand in
1, 1.5, 2, 2.5,3,3.5,4,4.5,6,6.5,7,7.5,8.0,8.5 = 14 total count
as he know total count, he will reach to middle (i.e. 4 and ask "Am I taller than you?" )
1st Yes,
(As NOs can be unlimited), he can iterate from 4.5 to 6.5, at 7 he gets asnwer last yes, gets placed. (so total iterations are less than n/2)
Answer : 17
The blind man will ask questions to in order 17, 33,(17+16), 48(17+16+15),.....,150(17+16+15+....+5+4+3).
Now lets say 17th man answer yes then he will ask question to each guy from 1st to 16th and worst case can be 1+16=17.
or lets say 48th man answer yes then he will ask question to each guy from 34th to 47th and worst case can be 3 + 14 = 17
in same way u go further and find worst case 17.
150/5=30+1(First)+2(yes)=33
He start asking every fifth to make it faster but start with the first in the line.
1=yes if no 5=yes then he gonna ask 2,3,4 until he one of them answer him yes again, so he have 2 YES. |worst case possible he taller than all of them or the last person answer him yes|
{1;5;10;15;20;25;... ...;145;150}=31+2(yes)=33
This sounds similar to the problem of having two eggs to find out from which floor they will break...Answer should be 17
- Coder... February 15, 2015