[PART : 1] Cracking the Coding Interview Puzzles
Puzzle 1 | (How to Measure 45
minutes using two identical wires?)
Solution :
Puzzle 2 | (The Heavy Pill: You have
20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of
weight 1.1 grams. Given a scale that provides an exact measurement, how would
you find the heavy bottle?
Soluton :
1) Arrange the 20 jars in a linear way numbering it from 1 to 20.
2) Now pick #no of
pills from each jar according to the order they are arranged. for ex pick 1 pill
from jar 1, 2 from jar 2, 3 from jar 3 and so on.
3) Suppose if all the
jars have equal weight of pills then the total weight is supposed to be:
Applying rule N (N
+ 1) / 2
20( 20 + 1) / 2 =
210 grams
4) Now weight the pills
that has been collected from these 20 jars, Let the total weight be X
grams.
5) Deduct 210 grams
from X grams. Let the result be Y.
6)The difference value
Y will indicate which bottle is heavier.
If it(difference) is 0.1 gram more, it is the
1st bottle which has the heavy pills. If it is 0.2 grams more, the 2nd bottle
has the heavy pills. If it is 0.3 grams more, the 3rd bottle has the heavy
pills. If it is 1 gram more, then the 10th bottle has the heavy pills.
If it is 1.1 gram more then the 11th bottle has the heavy pills. If
it is 2 gram more then then 20th bottle has the heavy pills.
Related question :
http://www.geeksforgeeks.org/puzzle-7-find-the-jar-with-contaminated-pills/
Puzzle 3 | (Basketball: You
have a basketball hoop and someone says that you can play one of two games.
Sol:
Game 1:
P(game1) = p
Game 2:
P(game2)=P(make 1 and 2) + P(make 1 and 3) +
P(make 2 and 3) + P(make 1, 2 and 3)
=p*p*(1-p) + p*(1-p)*p + (1-p)*p*p + p*p*p
=3p^2 - 2p^3
play Game 1 if:
P(game1) > P(game2)
=> p > 3p^2 - 2p^3
=> p(p-1)(2p-1) > 0 note that
0<=p<=1
=> 0 < p < 1/2
=> p < 1/2
play game 2 if :
p > 1/2
If p = 0 or p = 1/2 or p = 1, then it
doesn't matter which game to play.
Puzzle 4 | (Dominos: There is an 8x8
chessboard in which two diagonally opposite corners have been cut off. You
are given 31 dominos, and a single domino can cover exactly two squares. Can
you use the 31 dominos to cover the entire board? Prove your answer (by
providing an example or showing why it's impossible).)
Puzzle 5 | (Ants on a Triangle:
There are three ants on different vertices of a triangle. What is the
probability of collision (between any two or all of them) if they start walking
on the sides of the triangle? Assume that each ant randomly picks a direction,
with either direction being equally likely to be chosen, andthat they walk at
the same speed. Similarly, find the probability of collision with n ants on an
n-vertex polygon.)
Puzzle 6 | (Jugs of Water: You have
a five-quart jug, a three-quart jug, and an unlimited supply of water (but no
measuring cups). How would you come up with exactly four quarts of water? Note
that the jugs are oddly shaped, such that filling up exactly "half"
of the jug would be impossible.)
Puzzle 7 | (Blue-Eyed Island: A
bunch of people are living on an island, when a visitor comes with a strange
order: all blue-eyed people must leave the island as soon as possible. There
will be a flight out at 8:00 pm every evening. Each person can see everyone
else's eye color, but they do not know their own (nor is anyone allowed to tell
them). Additionally, they do not know how many people have blue eyes,
although they do know that at least one person does. How many days will it take
the blue-eyed people to leave?)
Puzzle 8 | (The Apocalypse: In the
new post-apocalyptic world, the world queen is desperately concerned about the
birth rate. Therefore, she decrees that all families should ensure that they
have one girl or else they face massive fines. If all families abide by this
policy-that is, they have continue to have children until they have one girl,
at which point they immediately stop-what will the gender ratio of the new
generation be? (Assume that the odds of someone having a boy or a girl on any
given pregnancy is equal.) Solve this out logically and then write a
computer simulation of it.)
Puzzle 9 | (The Egg Drop Problem: 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 two eggs. Find N, while minimizing
the number of drops for the worst case.)
Puzzle 10 | (100 Lockers: There are
100 closed lockers in a hallway. A man begins by opening all 100 lockers. Next,
he closes every second locker. Then, on his third pass, he toggles every third
locker (closes it if it is open or opens it if it is closed). This process
continues for 100 passes, such that on each pass i, the man toggles every
ith locker. After his 100th pass in the hallway, in which he toggles only
locker
Puzzle 11 | (Poison: You have 1000
bottles of soda, and exactly one is poisoned. You have 10 test strips
which can be used to detect poison. A single drop of poison will turn the
test strip positive permanently. You can put any number of drops on a test
strip at once and you can reuse a test strip as many times
Related question :
http://www.geeksforgeeks.org/puzzle-7-find-the-jar-with-contaminated-pills/
Sol:
|
|
Game 1:
|
|
P(game1) = p
|
|
Game 2:
|
|
P(game2)=P(make 1 and 2) + P(make 1 and 3) +
P(make 2 and 3) + P(make 1, 2 and 3)
|
|
=p*p*(1-p) + p*(1-p)*p + (1-p)*p*p + p*p*p
|
|
=3p^2 - 2p^3
|
|
play Game 1 if:
|
|
P(game1) > P(game2)
|
|
=> p > 3p^2 - 2p^3
|
|
=> p(p-1)(2p-1) > 0 note that
0<=p<=1
=> 0 < p < 1/2 |
|
=> p < 1/2
play game 2 if : p > 1/2 |
|
If p = 0 or p = 1/2 or p = 1, then it
doesn't matter which game to play.
|
Puzzle 9 | (The Egg Drop Problem: 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 two eggs. Find N, while minimizing the number of drops for the worst case.)
Comments
Post a Comment