Gold bar with 7 segments

You’ve got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Break the 7 piece gold bar to make a piece of 1 segment size and the other of 2 segments size.( the remaining 4 segments intact)

i.e 7= 1 + 2 + 4 (only two breaks needed)

1- 1st day

2- 2nd day

(1+2) - 3rd day

4 - 4th day

(4+1) - 5th day

(4+2) - 6th day

(4+2+1) - 7th day.

Pick a Random Byte

Question: You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal.

Answer: Since we can only store one byte at a time, we have to be able to work with the bytes as they come in. We can’t store everything, count the number of bytes and pick one. That would be too easy wouldn’t it?

Let’s think it through. We don’t know how many bytes there are, so at any point in time we should have a random byte picked from all the bytes we have seen so far. We shouldn’t worry about the total number of bytes at any time.

When we get the first byte, it is simple. There is only one so we store it. When we get the second one, it has 1/2 probability of being picked and the one we have stored has a 1/2 probability of being picked (we can use any programming language’s built-in random function). After picking one, we replace the current stored byte with the one we picked. Now it gets interesting. When we get the third one, it has 1/3 probability of being picked and the one we have stored has a 2/3 probability of being picked. We pick one of the two bytes based on this probability. We can keep doing this forever.

Just generalizing, when we get the nth byte, it has a 1/n probability of being picked and the byte we have stored has (n-1)/n probability of being picked.

Sometimes, this question is a little confusing. The question said you have only space to store one byte but there is an assumption that you have space to store variables to track the number of bytes and so on. Another assumption is that the stream of bytes is not infinite. If not, we won’t be able to calculate (n-1)/n.

If you have suggestions or comments, they are always welcome.

Three Switches

Question: You are standing outside a room next to three switches, all of which are off. Each switch operates a different light bulb in the room. The room door is closed, so you cannot see which switch operates which bulb. You are only allowed to go into the room once. Determine which switch operates which bulb.

Answer: Stumped? The issue lies in the fact that there are only two possible positions for each switch (on or off), but three bulbs to identify. Identifying one bulb is super easy, just set one switch on and then go into the room to check which one is on. But then, how do we detect the other two?

So let’s think deeper, what are the other properties of a light bulb operated by a switch? Light bulbs definitely produce light, but they also produce heat (a not so very important characteristic!). Any chance we can use this idea to help solve our problem? Since a light bulb would take sometime to lose its heat after being switched off, you could still determine if it had ever been on by touching it.

So now, we can easily determine which bulb is operated by which switch. First, we turn the first switch on and leave the other two off. After 5 minutes, we turn the first switch off, turn the second switch on and leave the third switch off. Then we go into the room and touch one of the bulbs which is turned off. After that, it would be easy to tell that the first switch matches the warm bulb, the second switch matches the bulb thats turned on and the third switch matches the colder bulb.

Flipping Coins on the table

There are twenty coins sitting on the table, ten are currently heads and tens are currently tails. You are sitting at the table with a blindfold and gloves on. You are able to feel where the coins are, but are unable to see or feel if they heads or tails. You must create two sets of coins. Each set must have the same number of heads and tails as the other group. You can only move or flip the coins, you are unable to determine their current state. How do you create two even groups of coins with the same number of heads and tails in each group?

Answer: Create two sets of ten coins. Flip The coins in one of the sets over, and leave the coins in the other set alone. The first set of ten coins will have the same number of heads and tails as the other set of ten coins.

Reaching the door of Heaven

A person dies, and he arrives at the gate to heaven. There are three doors in the heaven. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. How long will it take the person to reach heaven?

this is a probability question - i.e. it is solvable and has nothing to do with religion, being sneaky, or how au dente the pasta might be ;-)

Answer:

1/3 of the time, the door to heaven will be chosen, so 1/3 of the time it will take zero days. 1/3 of the time, the 1-day door is chosen; of those, the right door will be chosen the next day, so 1/9 trips take 1 day. Similarly, 1/9 will take two days (choosing the 2-day door, then the right door).

After that, the cases split again, and again, and again. I can’t seem to make a nice infinite sum this way, so let’s try again.

Suppose the average days spent is X. 1/3 of the cases are done in zero days as before. 1/3 of the cases are 1 day plus X. 1/3 are 2 + X. So:

X = 1/3 * 0 + 1/3 * (1 + X) + 1/3 * (2 + X)

  = 0 + 1/3 + X/3 + 2/3 + X/3

  = 1 + 2X/3

Therefore,

  X/3 = 1

    X = 3

On average, it takes three days to get to heaven. Two if the noodles are limp.

Took me one blind alley, and about five minutes.

Can you properly the hotel charges?

Three people check into a hotel. They pay $30 to the manager, and go to their room. The manager finds out that the room rate is $25 and gives $5 to the bellboy to return. On the way to the room the bellboy reasons that $5 would be difficult to share among three people so he pockets $2 and gives $1 to each person. Now each person paid $10 and got back $1. So they paid $9 each, totaling $27. The bellboy has $2, totaling $29. Where is the remaining dollar ? 

 

Solution: True its just a slip of tongue. 3 rooms money paid = $27 = Manager $25 + bellboy $2. Plus $1 to each of them.

Passengers and Random Seats

100 passengers are boarding an airplane with 100 seats.
Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order.
However, the first passenger lost his ticket so he just took a random seat.
For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat.
What's the probability that the last passenger would sit on his own seat ?

Solution:
Let us say that everyone is sitting except for the 100th passenger. Consider where can he sit - he can sit in either seat numbered 100 or 1. There cannot be any other seat vacant for him.
We can prove this using contradiction. Lets say that a seat numbered n=55 is vacant for 100th passenger. Since passenger 55 came earlier he should be sitting in his seat if its vacant. So seat 55 cant be vacant. This logic can be applied to all seats except for seat 1 and 100.
So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equally likely.
So answer = 1/2.

Fint out the matching socks

Michael have ten pairs of black socks, eight pairs of white socks and seven pairs of green socks. Everything is mixed in a draw. As there is no light he were not able to identify the color of the socks. How many of the socks did he want to take to match one pair ?

Solution:

The answer is 4 since in worst case all 3 socks taken first will be different color then the 4th one would be repetition. However if we consider a left sock to be different from right one, then at least 10 + 8 + 7 + 1 = 26 socks are needed.

How many races required?

You have 25 horses and 5 tracks and you need to find out top 3 horses. What is the minimum number of races required to do this ?


Solution:


For 1st question:
Group 25 horses in 5 groups:

A : A1, A2, A3, A4, A5 [Decreasing order of speeds]

B : B1, B2, B3, B4, B5

C : C1, C2, C3, C4, C5

D : D1, D2, D3, D4, D5

E : E1, E2, E3, E4, E5

Five races will have to take place for ranking in groups themselves.

One race for A1, B1, C1, D1, E1 for ranking of the groups.

Now A1>B1>C1>D1>E1

So A1 is the topper. We now need to find 2 more horses for 2nd and 3rd position.

Here is the key observation.

Selection by Elimination  [We need to find 2 more horses, if any horse is slower than 2 horses except A1 then it can not be included in the solution]

1. D1 and E1 can not be included in the solution as both of them are slower than B1 and C1

and hence their whole group is eliminated as they were best from their groups.

2. A4, A5 can not be included in the solution as they are slower than A2 and A3.
3. B3, B4, B5 can not be included in the solution as they are slower than B1 and B2.

4. C2, C3, C4, C5 can not be included in the solution as they are slower than C1 which is slower than B1 itself.

So we are now having only 5 possible horses for 2 positions which can be found out in just one race. [A2, A3, B1, B2, C1] Top 2 of this group will be ranked 2nd and 3rd after A1.