Ant's travel in a grid

 http://tech-queries.blogspot.in/2010/03/ants-travel-in-grid.html

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.