King and Poison Puzzle-Asked in Amazon interviews.

Question:

A bad king has a cellar of 1000 bottles of delightful and very expensive wine.

A neighboring queen plots to kill the bad king and sends a servant to poison the wine.
Fortunately (or say unfortunately) the bad king’s guards catch the servant after he has only poisoned one bottle.
Alas, the guards don’t know which bottle but know that the poison is so strong that even if diluted 100,000 times it would still kill the king.

Furthermore, it takes one month to have an effect. The bad king decides he will get some of the prisoners in his vast dungeons to drink the wine. Being a clever bad king he knows he needs to murder as few prisoners as possible — believing he can fob off such a low death rate — and will still be able to drink the rest of the wine (999 bottles) at his anniversary party in 5 weeks time.

In the worst case, what is the minimum number of prisoners he would have to kill in order to find out the poisoned bottle?

Do note that the king wants to minimize the number of prisoners involved in the experiment. He might decide to kill every prisoner involved in the experiment if he feels that they may tell the world about his evil plans.

Solution: 9 Prisoners

Number the bottles 1 to 1000 and write the number in binary format.bottle 1 = 0000000001 (10 digit binary)
bottle 2 = 0000000010
bottle 500 = 0111110100
bottle 1000 = 1111101000
Now take 10 prisoners and number them 1 to 10, now let prisoner 1 take a sip from every bottle that has a 1 in its least significant bit. Let prisoner 10 take a sip from every bottle with a 1 in its most significant bit. etc.prisoner = 10 9 8 7 6 5 4 3 2 1
bottle 924 = 1 1 1 0 0 1 1 1 0 0
For instance, bottle no. 924 would be sipped by 10, 9, 8, 5, 4 and 3.
That way if bottle no. 924 was the poisoned one, only those prisoners would die.
After four weeks, line the prisoners up in their bit order and read each living prisoner as a 0 bit and each dead prisoner as a 1 bit. The number that you get is the bottle of wine that was poisoned.
1000 is less than 1024 (2^10). If there were 1024 or more bottles of wine it would take more than 10 prisoners to do the experiment.Now, let's look at the number of prisoners that will die in the worst case. That's equal to the maximum number of 1 bits in numbers from 0 - 999. Number 511 has 9 1 bits. The first number with 10 set bits is 2^10 - 1 = 1023. Since, that's outside our range, the maximum number of prisoners that will die in the experiment is 9.

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Flutter Analysis and Practice: RichText Best Practices

Switches and Routers in Networking

Flutter Getx Implementation

Bluehost Vs Weebly

Why GitHub Copilot Will Not Change Programming

Working with Foreign Functions

Kubernetes Dashboard setup for a multi-node cluster

Run your Pull Request Preview Environments on Kubernetes

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Longest Increasing Subsequence Coding Question

LeetCode 146. LRU Cache

Average of Levels in Binary Tree

Dynamic Programming