Generate integer from 1 to 7 with equal probability

Generate integer from 1 to 7 with equal probability?

Given a function foo() that returns integers from 1 to 5 with equal probability, write a function that returns integers from 1 to 7 with equal probability using foo() only. Minimize the number of calls to foo() method. 

Sol:

We can generate from 1 to 21 with equal probability using the following expression.

 5*foo() + foo() -5 

Let us see how above expression can be used.
1. For each value of first foo(), there can be 5 possible combinations for values of second foo(). So, there are total 25 combinations possible.
2. The range of values returned by the above equation is 1 to 25, each integer occurring exactly once.
3. If the value of the equation comes out to be less than 22, return modulo division by 7 followed by adding 1. Else, again call the method recursively. The probability of returning each integer thus becomes 1/7.

// Returns 1 to 7 with equal probability 

public static int getRandom()   

{  

    int i;  

    i = 5*foo() + foo() - 5;  

    if (i < 22)  

        return i%7 + 1;  

    return getRandom();  

}  

Lockers puzzle

Puzzle: There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (e.g., he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open? 

Ans:

For which rounds is a door toggled (open or closed)?

A door n is toggled once for each factor of n, including itself and 1. That is, door 15 is toggled on round 1, 3, 5, and 15.

When would a door be left open?
A door is left open if the number of factors (x) is odd. You can think about this by
pairing factors o as an open and a close. If there’s one remaining, the door will be open. 

When would x be odd?
x is odd if n is a perfect square. Here’s why: pair n’s factors by their complements. For example, if n is 36, the factors are (1, 36), (2, 18), (3, 12), (4, 9), (6, 6). Note that (6, 6) only contributes 1 factor, thus giving n an odd number of factors.

How many perfect squares are there?
There are 10 perfect squares. You could count them (1, 4, 9, 16, 25, 36, 49, 64, 81, 100), or you could simply realize that you can take the numbers 1 through 10 and square them (1*1, 2*2, 3*3, ..., 10*10).

Therefore, there are 10 lockers open. 

Egg drop puzzle

Puzzle: There is a building of 100 floors. If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case. 

Ans: Observation: Regardless of how we drop Egg1, Egg2 must do a linear search. i.e., if Egg1 breaks between floor 10 and 15, we have to check every floor in between with the Egg2

The Approach:
A First Try: Suppose we drop an egg from the 10th floor, then the 20th, ...

• »  If the first egg breaks on the first drop (Floor 10), then we have at most 10 drops total.
  
• »  If the first egg breaks on the last drop (Floor 100), then we have at most 19 drops total ( floors 10, 20, ...,90, 100, then 91 through 99).
  
• »  That’s pretty good, but all we’ve considered is the absolute worst case. We should do some “load balancing” to make those two cases more even.
  Goal: Create a system for dropping Egg1 so that the most drops required is consistent, whether Egg1 breaks on the rst drop or the last drop.
  

1. A perfectly load balanced system would be one in which Drops of Egg1 + Drops of Egg2 is always the same, regardless of where Egg1 broke.
   
2. For that to be the case, since each drop of Egg1 takes one more step, Egg2 is allowed one fewer step.
   
3. We must, therefore, reduce the number of steps potentially required by Egg2 by one drop each time. For example, if Egg1 is dropped on Floor 20 and then Floor 30, Egg2 is potentially required to take 9 steps. When we drop Egg1 again, we must reduce potential Egg2 steps to only 8. That is, we must drop Egg1 at floor 39.
   
4. We know, therefore, Egg1 must start at Floor X, then go up by X-1 floors, then X-2, ..., until it gets to 100.
   
5. Solve for X+(X-1)+(X-2)+...+1 = 100. X(X+1)/2 = 100 -> X = 14
   

We go to Floor 14, then 27, then 39, ... This takes 14 steps maximum. 

Magical Hat

Puzzle: A bunch of men are on an island. A genie comes down and gathers everyone to-gather and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. 

Ans:

so let’s simplify it by looking at specific cases. 

Case c = 1: Exactly one man is wearing a hat.

Assuming all the men are intelligent, the man with the hat should look around and realize that no one else is wearing a hat. Since the genie said that at least one person is wearing a hat, he must conclude that he is wearing a hat. Therefore, he would be able to remove it that night.

Case c = 2: Exactly two men are wearing hats.
The two men with hats see one hat, and are unsure whether c = 1 or c = 2. They know, from the previous case, that if c = 1, the hats would be removed on Night #1. Therefore, if the other man still has a hat, he must deduce that c = 2, which means that he has a hat. Both men would then remove the hats on Night #2

Case General: If c = 3, then each man is unsure whether c = 2 or 3. If it were 2, the hats would be removed on Night #2. If they are not, they must deduce that c = 3, and therefore they have a hat. We can follow this logic for c = 4, 5, ... 

There are c hats so it will take c nights to remove all of them.