## Amazon Interview Question for Quality Assurance Engineers

Country: India
Interview Type: In-Person

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

Hi,

to find out the the bottles has to be arranged in 25 X 40 grid.
and totally 65 slaves has to be used. Slaves has to sip rum from a column or a row.
so if a slave sip the rum from row i will die similarly column j will die. so the ith row jth column contains poisoned bottle

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

Question is not asking minimum persons to die. It is asking minimum people to use. 1000 in binary can be represented in 8 bits. Take 8 soldiers and make them drink for bottle rows having 1. On the basis of which soldiers died, it can be found out.
So minimum 8 persons can be used(not 65)

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

Although, nice approach for minimum persons to die

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

Minimum person to die is 0 (though with prob 0.001), or 1 with prob 0.999. Have 999 slaves drink each from one bottle. Etc.

Minimum number of slaves to use is 10, since 1024=2^10.
Since 4=2^2=100 in binary, for 3 bottles you would need 2 slaves; since 8=2^3=1000b, for 7 bottles you would need 3 slaves, etc.

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

The answer is still 10. (2 power 10 = 1024) List numbers until 1000 in binary format vertically. Each 1 represents a slave and with the combination of slaves you can find the poisoned rum.
8 = 2 power 3. So three slaves

``````Eg:        1 2 3 4 5 6 7 8
Slave 1:     0 0 0 1 1 1 1 0
Slave 2:     0 1 1 0 0 1 1 0
Slave 3:     1 0 1 0 1 0 1 0``````

from the above combination you can find the rum bottle based on which slaves died

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

10 slaves.
Name slaves from 0 to 9. Give the each bottle a number from 1 to 1000 and represent the number in binary format. If the ith digit of the binary number is 1, let ith slave to drive this bottle. After an hour, if the ith slave die, the ith digit of poisoned bottle is 1, otherwise 0.

For example, assume bottle number 3 contains poison,

3 = 0000000011

Then slave 0 and slave 1 need to drive this bottle. After an hour, they die...

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

Divide the 1000 bottles into 2 halves and accumulate drops of each half two form two glasses of wine. Have a slave drink each glass. Check which one of them dies. Take the corresponding half and repeat the process.

No of slaves = log2(1000) ~ log2(1024) =10

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

There might be many ways to solving this problem but main idea is to identify poisonous bottle with minimum slaves and time.
My solution will take 10 prisoner and 1hour time.

Name 10 prisoners as P0 to P10
Name 1000 bottles in binary Ex bottle 1 as 0001, bottle as 0101....bottle 10 as 1010 etc

Ask prisoner P0 to drink from Bottle 1 (00000000001)
Ask prisoner P1 to drink from Bottle 1 and 2 (00000000001,00000000010)
.
.
.
Ask prisoner P10 to drink from Bottle 1...Bottle1000

Finally after 1 hour see which prisoner has died suppose if prisoner 1,4 has died the poisoned bottle is 5.

This solution will even hold good for 1024 prisoners.

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

Hi Anon123, your approach might be correct, but don't think the answer is. As per your solution, would need to wait for the slave to die in each of 10 iterations which might be more than 1 hr.

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

suppose

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

To visualize this, imagine arranging the 1000 rum bottle samples in a 10 x 10 x 10 cubic grid.
Now, allow 10 slaves (Name them as Slave1,2,3...10) to drink all bottles in the corresponding named column rum samples first (say x-axis columns). And with the same order of slave arrangement, immediately allow them to drink all column bottles on y-axis. Repeat it for z-axis as well. Then wait for an hour.
If Slave 2 (while drinking by x-axis), slave 4 (y-axis), slave 6 (z-axis) dies, then, the rum is located at 2 x 4 x 6th location.
With this solution, at the max 3 slaves would die and at the min 1 slave would die (if the rum is located at 5 x 5 x 5 location).

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

I appreciate all the responses in technical angle. But my approach is to cater to King's safety along with the the slaves. Given are 1000 bottles , 1000 slaves , 1 hr time to find. Also mentioned is "any slave who even takes a sip of the poison, dies within an hour." - meaning it would not take less than a hour.
I would ask all the 1000 slaves to pick up the bottle and take only a sip of rum from bottle in hand. In less than an hour, 1 slave, 1 bottle will fall - saving 999 slaves and the king along with some time in hand and also 999 bottles of Rum.
This makes me use only 1 slave to know poisoned bottle. :)

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

Well, you are still using a 1000 slaves to validate each bottle..

How about using 999 salves for 999 bottles, if none of them die at the end of an hours, then the 1000th bottle is poisoned..

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

The answer is 65 (they are asking how many slaves the king needs to use, not how many die).
We know that there are 1000 bottles. We can arrange these bottles into a grid. We locate the various factors of 1000 (which are 1, 1000, 2, 500, etc.). We want to find the combo that adds to the smallest sum.

This gives us the combo of 25 and 40. You line up 25 slaves in the rows, and you line up 40 in the columns. You tell each slave to drink a bottle from their respective row/column. You can then determine which bottle contains the poison by which two slaves die from poisoning.

25 + 40 = 65 slaves.

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

From my perspective, the grid is 25*40 in which the rum is placed and the slave tries it in row there are 40 slaves who drinks in the first minute and in column there will be 24 slaves(1 will be included in row so excluding that slave) who will have their sip in the second minute. It would take less time if we take row wise. So making the remaining 39 slaves to have their drink in remaining 24 columns in third minute and so on.. So within an hour who dies according to time given the position will be calculated..
so, 40+24=64 slaves

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

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

Question to ask - Does the slave die right immediately after taking the sip or dies after how many minutes?

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

1

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

If they have to decide within one hour, then they need 1000 salves to decide after 1 hr who is afftected with poision?

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.