A good long techo discussion and i come up with this . Some insights into a problem long known and discussed . A good interview question that can be brought up for discussion and i totally loved it!!

King and Wine problem :-

The standard King and wine pblm is a very often asked puzzle . Suppose a king had 1000 bottles of wine and some traitor poisoned 1 of the bottles but was caught immediately after that .

The poison takes 1 hour to take to effect and even a single drop can cause death . The King wants to find which bottle had the poison. He can used prisoners to so the same .

What will the king do to find the poisoned bottle in 1 hour?

First solution -

This solution will get you least no of prisoners involved

Convert  each bottle to binary no .

bottle 1 = 0000000001 (10 digit binary)

bottle 2 = 0000000010

.....

bottle 1000 = 1111101000

Let each digit on this represent a prisoner . P₁.......P₁₀

So depending upon which prisoners die we can identify the bottle .

Suppose P₃,P_5, P₆ ,P₇ ,P₈, P₉ die , then it means that bottle

0111110100 = 500  had the poison.

This approach guarantees less prisoners are involved but can involved many deaths as well.

Second solution :-

This will guarantee that less of prisoners die

Align 1000 bottles into a 2 dimentional array (32 X 32 array)

	P1	…………	P32
P33	B1	.............	B32
..	B33	...............	B64
P64	...................	B1000

P1 drinks from all bottles in the column P1 (B1, B33...)

P33 drinks from all bottles in column P33 (B1...B32)

Depending on which 2 prisoners die , We can find the bottle

(Extension to this -  instead of 2 direction use a 3 dimensional array (10 x 10 x10 ) and depend ingon which 3 prisoners die identify the bottle . Hence 30 prisoners)

The interesting gaming company problem

Hi,

I was going through some online courses last week and hit this assignment. The problem was a good brushup in terms of some mathematical series involved . So enjoy !!

You own a large gaming company and want to distribute an update to all of your players. The size of the update is 1GB and your server can send data at up to 1GB/s. Your engineers have found that assuming every player can download at 1MB/s leads to very accurate estimates of network performance. Furthermore, they've found you can assume that the server splits its capacity evenly across clients. You have 100,000 players.

One of your engineers recommends that you distribute the update by having all users download the full file from your company's server. You walk through this calculation with the engineer and determine it will take 100,000 seconds (~28 hours) for all of your players to download the update. The server can support 1,000 players downloading the update at once by splitting its 1GB/s across 1,000 1MB/s clients. It will take 100 rounds of 1,000 players for everyone (all 100,000) to receive the update. As it takes 1,000 seconds for a 1MB/s connection to download 1GB, each round will take 1,000 seconds. 100 rounds of 1,000 seconds is 100,000 seconds, or 28 hours.

Another engineer recommends a different, peer-to-peer, strategy. In this strategy, players who have downloaded the patch allow other players to download it from them. So in the first round, 1,000 players download the patch from the server. In the second round, 1,000 new players download the patch from the server, and 1,000 new players pair with the first round downloaders. In the third round, 1,000 new players download the patch from the server, and 3,000 new players download the patch from players who have already downloaded it.

Calculate how long it will take until the last player to receive the update using the second strategy. How much faster is it than the first strategy?

Solution- Do not confuse the big nos here . Consider 1000 players to be a single unit that had total download capacity of 1 Gbps. So we have 100 such unit

Let us define 1 round as

1 round = 1 stream to get 1 Gb data @ 1Mbps = 1000 sec tp n no of subs               

Now for each round how many such set receive the msg

Round 1  - 1 (from server to 1 set)

Round 2 - 2 (1 from server and 1 from set that got in round 1)

...

Round n - 2 ^n-1

In how many such round will 100 unit get the data or

for which n will we have

Σ 2 ^n-1   > = 100

We know that 1 + 2 +4 + 2 ^n-1 < 2 ⁿ

For which n

 2 ⁿ   >=100

n = 7  (approx)

So total time taken = 7 x (time for 1 round)

                                       =  7 x 1000

                                      =  7000 sec approx