Amazon Interview Question
Software Engineer / DevelopersVery nice question and answer, I guess we can say that for any number of chairs 2^n+2^m+1 we can choose either 2^n+1 either 2^m+1 as an initial chair considering they are numbered from 1,2,... to 2^n+2^m+1.
No 5, will not work. Nor will any odd numbered seat. If you have correct answers apart from 9 and 17, pls prove your point instead of posting trash.
Let us assume someone sat in seat 5.
Person number 2 will sit in seat 25.
Person number 3 will sit in seat 15.
Person number 4 will sit in either seat 10 or 20.
Thats enough to prove 5 will not work. If anyone sits in an even-numbered seat, thats not optimal.
Mr. ruralclimber... first of all ur answer is wrong and it shouldnt be "both 3".. it should "all 3" :P
Why don't those that think it is a solution other than 9 or 17 actually test their theory. You will find it to be wrong...
e.g. start at 1...next person will sit at 25....third will sit at 13....fourth will sit at either 7 or 19 (already an undesirable result as no further people will sit after these two are taken).
Similar argument for any other odd number other than 9 or 17...
Consider a general case. If the number of seats is n = (2^k)+1 for some k, then, the maximum possible seating of (n/2)+1 can be achieved by having the first person sit at position 1 or n or ceil(n/2).
This is true since when n=(2^k)+1, then, when someone sits in the first or middle or the last seat then all the other gaps are of length in powers of 2 (as suggested above by Vinay).
This implies that for this problem, with n=25, we need to split it into n1 and n2 such that: n1 = (2^k1)+1 and n2 = (2^k2)+1, for some k1, k2. Note that n1+n2 = n+1 = 26 (since they both share a common seat).
Thus, the only possible values are 9 or 17.
The Answer 9 & 17 are correct. But I couldn't understand the reason explained above.
The solution to this problem can be thought recursively.
The stop condition is when there are just 3 seats; that is there’s just 1 seat between the end seats. The series is like …1,3,7,15,31,63...That is, when the number of seats between the end seats is one of these numbers, the division will be perfect.
For 25 seats, when I select 9 as first seat 1...9....25 , the number of 'in between seats' in the first half is 7 and that of second half is 15. Both of these numbers appear in the above series I mentioned. I don't think it is possible to get a general formula for solution. Some numbers for which a perfect division exists is given below
1 2 3 4 5 6 7 : 3/5
1 2 3 4 5 6 7 8 9 10 11 :3/9
1 2 3 4 5 6 7 8 9 10 11 12 13 : 5/9
1..5..17..21
1...9....17...25
A password consists of five digits, in this format “ABCDE”.
Given: D = 3B.. and A + B + C + D + E = A*D
Also you have three sets:
1 2 7 4 5 where only one correct number but wrong position
2 6 8 5 7 with two correct numbers, one of them is in the right position
6 1 7 4 2 with two correct numbers and positions..
What is the password?
Guys in case you are bored at home.. give this brain teaser 5 min of your time..
A password consists of five digits, in this format “ABCDE”.
Given: D = 3B.. and A + B + C + D + E = A*D
Also you have three sets:
1 2 7 4 5 where only one correct number but wrong position
2 6 8 5 7 with two correct numbers, one of them is in the right position
6 1 7 4 2 with two correct numbers and positions..
What is the password?
I would agree with the above answer: either seat 9 or 17 for the first customer. Here's how I figured it out:
- Vinay Kuruvila July 19, 2006The best possible end scenario the owner can expect is persons sitting in every other seat; 13 people in seats 1, 3,5,7,9,11,13,15,17,19,21,23,25. We know that whenever a new customer enters the room, she is going to find the biggest gap between any two old customers, divide it in half and sit right between them. So, to be really efficient about this we need to make sure that when she can easily divide at half at every stage. If you cannot perfectly divide a gap by 2, a seat is going to get wasted.
And this needs to be done repeatedly. Therefore, at every point, we need to make sure that the length of the gaps between seats are powers of two. So, how should we start out? Well if we select 9 as the first person's seat: then the first gap is 9-1= 8 seats wide (power of 2). The second gap is 25-9= 16 seats wide (another power of 2). So it works!
Similarly, seat 17 for the first patron would also be acceptable.