Josephus Problem - Puzzle

A Barcode Puzzle

Google Puzzle- who keeps the fish?

Facts:*

1: There are 5 villas in 5 different colors
2: In each villa lives a person with a different nationality.
3: These 5 owners drink a certain beverage, smoke a certain brand of cigar
and keep a certain pet.
4: No owner has the same pet, smoke the same brand of cigar or drink the
same drink.


*Hints:*

1: The British lives in a red villa.
2: The Swede keeps dogs as pets
3: The Dane drinks tea
4: The green villa is on the left of the white villa (it also means they are
next door to each other)
5: The green villa owner drinks coffee
6: The person who smokes Pall Mall rears birds
7: The owner of the yellow villa smokes Dunhill
8: The man living in the villa right in the center drinks milk
9: The Norwegian lives in the first villa
10: The man who smokes Blend lives next to the one who keeps cats
11: The man who keeps horses lives next to the man who smokes Dunhill
12: The owner who smokes Blue Master drinks beer
13: The German smokes Prince
14: The Norwegian lives next to the blue villa
15: The man who smokes Blend has a neighbor who drinks water.

*The question is: who keeps the fish?

Minimum Number of Cuts Needed to Cut Rope in get the rope of desired length

the length of the rope is l units.
I can only cut any rope into two halves. for example if the length of the rope is 8 and we need a length of rope 6 we first cut into two halves and we get 4, 4 now we cut any of the half again and we get 4,2,2 now we can merge 4 and 2 and form a rope of length 6. in this example we need a minimum of 2 cuts to get the length of rope 6 from 8

assume that l is always a power of 2 and we need always a even length of rope from it how to find the number of minimum cuts needed to get the new rope?.

1st Solution

k -> rope of desired length.
l -> rope of given length
m = 2;
while(k%m==0 )
m *= 2;
ans :: (log2(l) - log2(m) + 1).
ex.
k = 6,l = 8
so initially m = 2;
after 1st iteration m = 4;
then break;
so min = log2(8) - log2(4) + 1 = 3 -2 + 1 = 2.


2nd Solution
for a number N
first set bit(From Left) is simply integer value of log(N)
last set bit can be calculated as
N = N-(N&(N-1)); and then Log(N)
int i = log(n);
n -= n&(n-1);
int j = log(n);
i-j will be the answer.

Refer here for more detail

A Triangle Puzzle

three points are randomly chosen on a circle.what the probability that
1.triangle formed is right angled triangle.
2.triangle formed is acute angled triangle.
3.triangle formed is obtuse angled triangle.

Let the three vertices be A, B, C. We denote the angle at
center by the arcs AB, BC, CA by x, y, z.

x + y + z = 360.

Hence, the sample space can be represented by the region
surrounded by lines

x > 0,
y > 0 , and
x + y < 360. For the acute angled triangle ABC max(x, y, z) < 180, i.e., x < 180, y < 180, and x + y > 180

It can be easily seen that the three constraints form a
region which has exactly 1/4-th area of the original
sample space.

Solution Given abc

Secratry Puzzle ( A Kind of Hat having Balls)

A hat contains n balls, each with a number on it. On each turn, a ball is drawn uniformly at random and without replacement, and shown to you. If you are able to identify the ball with the largest number when it is drawn, you win the game. Give an algo/technique that wins with probability at least 1/4.


The secretary problem is an optimal stopping problem that has been studied extensively in the fields of applied probability, statistics, and decision theory. It is also known as the marriage problem, the sultan's dowry problem, the fussy suitor problem, the googol game, and the best choice problem. The solution is sometimes called the 37% rule. The problem can be stated as follows:

1. There is a single secretarial position to fill.
2. There are n applicants for the position, and the value of n is known.
3. The applicants can be ranked from best to worst with no ties.
4. The applicants are interviewed sequentially in a random order, with each order being equally likely.
5. After each interview, the applicant is accepted or rejected.
6. The decision to accept or reject an applicant can be based only on the relative ranks of the applicants interviewed so far.
7. Rejected applicants cannot be recalled.
8. The objective is to select the best applicant. The payoff is 1 for the best applicant and zero otherwise.

Terminology: A candidate is an applicant who, when interviewed, is better than all the applicants interviewed previously. Skip is used to mean "interview and reject".

Clearly, since the objective in the problem is to select the single best applicant, only candidates will be considered for acceptance. One reason why the secretary problem has received so much attention is that the optimal policy for the problem (the stopping rule) has a surprising feature. Specifically, for large n the optimal policy is to interview and reject the first n/e applicants (where e is the base of the natural logarithm) and then to accept the next who is better than these interviewed candidates. As n gets larger, the probability of selecting the best applicant from the pool goes to 1/e, which is around 37%. Whether one is searching through 100 or 100,000,000 applicants, the optimal policy will select the single best one about 37% of the time.

Solution http://en.wikipedia.org/wiki/Secretary_problem

Fogcreek programmers Variation of Hat Puzzle

100 fogcreek programmers are lined up in a row by an assassin. the assassin puts red and blue hats on them. they can’t see their own hats, but they can see the hats of the people in front of them. the assassin starts in the back and says “what color is your hat?” the fogcreek programmer can only answer “red” or “blue.” the programmer is killed if he gives the wrong answer; then the assassin moves on to the next programmer. the programmers in front get to hear the answers of the programmers behind them, but not whether they live or die. they can consult and agree on a strategy before being lined up, but after being lined up and having the hats put on, they can’t communicate in any way other than those already specified. what strategy should they choose to maximize the number of programmers who are guaranteed to be saved?

Solution

this is a very difficult problem to solve during an interview (especially if you’ve already taxed the candidate’s brain). look for obvious solutions first, and the reasoning behind them and then try to lead them to the ultimate solution.

a logical answer could be all the programmers would just say “red” and that way about half of them would survive on average, assuming the hats were distributed randomly.

this is a good start and should naturally lead to having every other programmer say the color of the hat in front of them. the first programmer would say the color of the hat in front of him, then the next programmer would just say that color that was just said. so we can guarantee that half survive - the even numbered programmers (since the person behind them told them the answer). and potentially if the hats were distributed randomly some of the programmers would get lucky and the hat in front of them would be the same color as their own. so this strategy should save more than half, and on average 75% of them would live.

at this point, if the solution is not clear, the candidate may give answers like, “they could agree that if they said their hat color in a soft voice, it means the hat in front of them is the same color, and if they say it in a loud voice, it means the hat in front is a different color”. this is definitely good and on the correct track. another option is they could say “reeeeeeeeeeed” for x number of seconds, where x represented the distribution of hats where a hat was a bit in a binary number, (red = 1, blue = 0). another interesting answer. there are many others like these that “bend” the rules and come to a solution.

but the real solution acknowledges that the programmers can only say “red” or “blue” and cannot alter their voice in such a convincing way as to signal any information other than the word they said. a good way to get this point across, is simply to change the problem slightly by saying “the assassin gets to hear their plan before she puts the hats on, and so will try to thwart the plan however she can.”

so if they decide to all say “red”, she’ll put blue hats on all of them. if they decide to all say the color of the hat in front of them, she’ll alternate the hats on every head, guaranteeing half will die. even with the assassin hearing their plan, there is still a way to save almost everyone.

we know that the first person is never going to have any information about the color of their hat, so they cannot be guaranteed to survive. but, i’ll give you a hint to the solution: i can save every other person for sure.

solution: they agree that if the number of red hats that the back person can see is even, that programmer will say “red”. if they add up to an odd number, they will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.

sample:

100 99 98 97 96 95 94 ... facing ->
R B B R B R B ... -> 45 R and 48 B

this shows #100 wearing a red hat, 99 a blue, 98 a blue, 97 a red, 96 a blue, 95 a red, 94 a blue and 45 red hats - 48 blue hats on the people in front of them.

100 counts up the red hats: 47 total. so 100 says “blue”. the assassin kills 100. 99 counts up the red hats in front: 47. 100 said blue, so 100 saw an odd number. 99 sees an odd number, so 99 says “blue” and lives. 98 had counted 47 red hats, and 99 didn’t say “red” so thats still the total. 98 says “blue”. 97 counts up and finds 46 red hats. 99 and 98 didn’t say “red”, so his count is missing a red hat (its on his head, he realizes). he says “red”. 96 heard the “red” and now knows that there are an even number of “red” hats in front of 95. 96 sees 46, so he knows he has a “blue” hat. etc…

even if the assassin knows the plan, she can’t thwart it. she hears the plan, but she still has to put the hats on their heads. the plan doesn’t rely on any ordering of the hats, so the worst the assassin can do is to make sure #100 gets killed and thats the worst damage she can do.