## Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
1
of 1 vote

I would agree with the above answer: either seat 9 or 17 for the first customer. Here's how I figured it out:

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

nice wrap-up... :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

9 or 17

Comment hidden because of low score. Click to expand.
0
of 0 vote

why not 5? how are you assuming 9 and 17

5-1=4(power of 2)this meets our criteria of atleast one seat apart.

Comment hidden because of low score. Click to expand.
0
of 0 vote

actually any odd number seat will work

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

actually, the first person can seat on 1 or 13 or 25.

both 3 gives the best results

Comment hidden because of low score. Click to expand.
0

Mr. ruralclimber... first of all ur answer is wrong and it shouldnt be "both 3".. it should "all 3" :P

Comment hidden because of low score. Click to expand.
0

thats why he's ruralClimber not urbanCliber like me...

Comment hidden because of low score. Click to expand.
0
of 0 vote

well .. 9 and 17 are the only answer .. ppl just don't read question clearly

Comment hidden because of low score. Click to expand.
0
of 0 vote

if 9 the there are two sets 1-8 and 10-25 which is a power of 2

the other case is when it is 17 where the two sets are 1-16 and 18-25 both of which are powers of two

power of tow is important so that it can be divided in two perfect halfs

Comment hidden because of low score. Click to expand.
0
of 0 vote

Thank you vinay kuruvila.

Comment hidden because of low score. Click to expand.
0
of 0 vote

9 or 17 are the only solutions

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

Why can't more people sit after 7 or 19 are taken? There are still seats which are adjacent to nobody right.

Comment hidden because of low score. Click to expand.
0
of 0 vote

8,9,10,16,17,18, I wrote a program to get these

Comment hidden because of low score. Click to expand.
0
of 0 vote

OOps, my fault, the answer should be 9,17

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Must add that seating the first person in the middle position i.e. ceil(n/2) works only when n=(2^k)+1 where k=2,3,... It does not work for k=1 i.e., just 3 seats.

But seating the first person in seat number 1 or n works for all k >=0.

Comment hidden because of low score. Click to expand.
0
of 0 vote

9 and 17 are correct answer

Comment hidden because of low score. Click to expand.
0
of 0 vote

9 & 17

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

can't it be 13 ?

.............13............
1...........13...........25
1....7......13...........25
.
.
.
1 3 5 7 ...........21 23 25

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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.

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