Puzzle
Problem-1: You have 10 bags full of gold coin each coin weighing 10 grams. But there is one bag that contains false coin weighing one gram less than original coin.There is a digital weighing M/C that tells the weight of things. find out the defective bag in one weighing.
Take 1 coin from First bag 2 from second and so on. weight the accumulated coins w'. The defective bag will be Summation (10)*10 - w'.
Problem-2: There are 25 horses which runs at different speed, and you have to find out the top three horses, in one race you can race not more than 5 horses, find the no. of races required minimum.
It will take seven (7) race to decide winner.
First 5 races: divide 25 horses into 5 groups and that gives you 5 winners.
Sixth race: Now race 5 winner that will tell you which two are the bottom most group. Reject them
Seventh race: Now consider first 3 groups the horse that came 3rd his group can only bid for 3rd place so we take him for next level. The horse that came 2nd. his group can bid for 2nd, 3rd spots we take 2 from this group. The horse that came first his group can bid for 1,2,3rd place, but we have already got overall our winner from this group so we only need 2nd and 3rd of this group. so that leave us with 5 horses; Race them you get your top 3
Problem-3: You have 8 balls. One of them is defective and weighs less than others. You have a balance to measure balls against each other. In 2 weighing how do you find the defective one?
First take 6 balls, 3 in each side. If the balance is balanced, then weigh the other two balls, placing each ball on each side. You will get the defective ball, i.e., the one which is weighing less. If balance is not balanced in the 1st case, when 6 balls are taken, then take the group of three balls which weigh less. Keep one ball from the three aside, Put the two balls on 2 sides. If the 2 balls are of equal weight, the ball kept aside will be the defective one, otherwise the ball weighing less will be the defective one.
Problem-4: You have a 100-story building and a couple of marbles. You must identify the lowest floor for which a marble will break if you drop it from this floor. How fast can you find this floor if you are given an infinite supply of marbles? What if you have only two marbles?
Asymmetric Binary search, It can be done in 14 trail. Here is the right reasoning. Suppose that the optimum number of steps (in the worst case) is 'n'. We do not know what 'n' is.
Now suppose the first egg breaks in the first attempt. Then we only have 'n-1' attempts left (to do with the second egg). Therefore the first egg must be dropped from the 'n'-th floor.
Now suppose the first egg breaks in the second attempt. The first attempt was done from the 'n'-th floor. After the second attempt, we only have 'n-2' attempts left (to do with the second egg). Therefore the second attempt must be from 'n+n-1=2*n-1'-th floor.
Continuing this way, the third attempt (if the first egg survives the first two falls) must be from the [n+(n-1)+(n-2)]-th floor. For the optimum 'n', we want the last two floor to be 97 and 100, or as close as possible (so as not to waste drops). I.e., the 'n' we seek is the smallest 'n' such that
n+(n-1)+(n-2)+(n-(n-2)) >=97
n*(n+1)/2 >=98
The smallest such n is 14, which is the answer we seek.
So the first egg is dropped from the following floor (starting the counting from 1).
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
Problem-5: You are given 12 coins. One of them is heavier or lighter than the rest. Identify this coin in just three weighing.
Group coins in A,B,C each has 4 balls {a1,a2,a3,a4 } {b1,b2,b3,b4} {c1,c2,c3,c4}.
Weigh#1: A and B -
Case 1 : equal
Weigh#2: {a1,a2,a3} and {c1,c2,c3}
Case 1 : equal
c4 is defective
Case 2 : (c1,c2,c3) is heavier (defective coin is heavier)
Weigh#3: {c1,c2}
Case 1 : equal
c3 is defective
Case 2 : not equal
heavier one is defective
Case 2 : A is heavy, B is light, C is of right weights.
Divide in 3 groups X = a1,a2,b3 Y= b1,a3,c1 Z= a4,b2,b4
Weigh#2 - X with Y
Case 1 : equal
Weigh#3 - b2 with b4
Case 1 : equal
a4 is defective and heavier
Case 2 : not equal
whichever is lighter is defective
Case 2 : X is heavier
Weigh#3 - a1 with a2
Case 1 : equal
b1 is defective and lighter
Case 2 : not equal
whichever is heavier is defective
Case 3 : Y is heavier
Weigh#3 - a1 with a3
Case 1 : equal
b3 is defective and lighter
Case 2 : not equal
Case 3 : B is heavy, A is light, C is of right weights.
Divide in 3 groups X = a1,a2,b3 Y= b1,a3,c1 Z= a4,b2,b4
Repeat same logic as Case : 1
No comments:
Post a Comment