Amazon Interview Question Quality Assurance Engineers
Country: India
Interview Type: In-Person
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)
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.
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
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...
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.
The answer is 10 slaves.
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).
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. :)
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.
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
Hi,
- baskartrk January 22, 2014The answer is 2.
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