Questions d'entretien

Entretien pour Summer Trader

-

Jane Street

A bad king has 1000 bottles of wine. A neighboring king plots to kill the bad king, and sends a servant to poison the wine. the servant is able to poison only one of them before he is caught. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. At a minimum how many servants does he need to kill to find out the poisioned bottle of wine and will still be able to drink the rest of the wine in 5 weeks time?

Répondre

Réponses aux questions d'entretien

10 réponse(s)

8

Simply saying "binary search tree" does not solve this problem in its entirety because of the five week time limit. If you just naively used a binary search, you'd take four weeks for the first iteration alone (the problem says the poison's effects take a month to surface, so that definitely wouldn't work. 10 prisoners lined up. Number the bottles from 0 - 999. Now, divide the bottles into blocks of powers of 2. Prisoner 9 drinks from 0 - 511. Prisoner 8 drinks from 0 to 255 and 512 to 999. Prisoner 7 drinks from 0 to 127, 256 to 383, 512 to 639, 768 to 896 Prisoner 6 drinks from 0 to 63, 128 to 191, 256 to 319, 384 to 447, 512 to 575, etc. Prisoner 1 drinks from every second bottle A month later, line up the Prisoners and treat the dead ones as 1s and the living ones as 0s - you'll have the answer in binary and find the dreaded bottle!

nilkn le

3

10 servants

Utilisateur anonyme le

3

The way the question is phrased, doesn't the king only need to sacrifice 1? If 1000 servants each sip a little of one of the wines, then after 5 weeks, only 1 will die?

Anonymous le

2

@Reader : Your solution is nice, but as you said if the poison bottle is 110,first day prisoner 10 dies, second day prisoner 1 dies, third day no one else dies. Question I ask you is : what happens if the bottle 10 (010 in your system) which is poisoned ? I'd rather learn binary than risking my life with your method, sorry :)

Fergunil le

1

8

Utilisateur anonyme le

1

i think the question means to ask 'how many servants does he need to employ/use to find out the poisoned bottle?' in which case the answer is 10.

Utilisateur anonyme le

0

10 is the correct answer

Xinlong le

0

Can you explain?

Utilisateur anonyme le

1

The binary number solution is nice, but it's annoying. First of all, the king's people would need to know binary numbers. Second of all, maybe you dont get the idea right away. Third, you dont use the fact that it takes a month to die, but the king has 5 weeks to get an answer. I came across an ingenious solution: Label all bottles from 000 - 999 Day1: Prisoner 1 drinks all bottles that end in 1: XX1 Day 2:Prisoner 1 drinks all bottles that have 1 in the middle: X1X Day 3:Prisoner 1 drinks all bottles that begin with 1: 1XX Same for Prisoner 2, 3, 4, ... .drinking from bottles XX2,X2X,2XX, XX3,X3X,3XX, etc Prisoner 10 drinks from all bottles with 0, same reasoning. Now, you wait and observe the order of dying of these people. Example: poisoned bottle is 532. First day, prisoner 2 dies, then second day prisoner 3 dies, then 3-rd day, prisoner 5 dies. Example: poisoned bottle is 110: first day prisoner 10 dies, second day prisoner 1 dies, third day no one else dies. What's nice about this method is that if you have more than 3 days between the poison taking effect and the deadline for finding out which bottle ( say you have 5 days, a week extra, etc), you can sample with 10 people a much larger number of bottles.

Reader le

0

This is basically a binary search tree. if a prisoner drinks, the outcome is either die or live for the next round. The worst case is that all prisoners die at the first attempt. so the max depth of that tree is log2(1000) ~ 10.

Hainott le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.