tag:blogger.com,1999:blog-30000851264367112412017-06-21T19:22:21.653-07:00Classic PuzzlesSSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-3000085126436711241.post-38132674921995707392011-11-26T02:22:00.000-08:002011-11-26T02:24:12.622-08:00Free Online Programming Books<a href="http://indiadiscuss.com/cs-resources/list-of-free-online-books-and-tutorials-for-learning-scala-programming-language/">List of Free Online Books and Tutorials for Learning Scala Programming Language</a>SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com0tag:blogger.com,1999:blog-3000085126436711241.post-81871803211945240302011-11-13T05:19:00.000-08:002011-11-13T05:21:54.102-08:00Fox and Duck Interview PuzzleA number of different versions of the puzzle are available. For this post we are using the Fox and the Duck version. A duck, pursued by a fox, escapes to the center of a perfectly circular pond. The fox cannot swim, and the duck cannot take flight from the water. The fox is four times faster than the duck. Assuming the fox and duck pursue optimum strategies, is it possible for the duck to reach the edge of the pond and fly away without being eaten? If so, how?<br /><br />From : <a href="http://indiadiscuss.com/interview-questions/">IndiaDiscuss.com Interview Questions and Puzzles</a><br /><br /><span style="font-size:130%;">Solution:</span><br />This is not a simple mathematical puzzle to solve like normal common problems. Fox in this puzzle is too fast and clever for any normal and simple strategy.<br /><br />From the speed of the fox it is obvious that duck cannot simply swim to the opposite side of the fox to escape. Pi*R/4 < R.<br /><br />Let V be the speed of Duck and 4V speed of fox.<br /><br />Now we need to find out the position from where duck can swim to the shore in time less then Pi*R/4V. Pi = 3.14.<br /><br />To keep things simple we will take the distance from center for the duck to escape when the fox is on the exact opposite side of the pond to be R/4.<br />So duck can swim in 3R/4V which is less than Pi*R/4V.<br /><br />Now the next challenge is how we can make sure the clever fox will be on the opposite side. Here is the tricky part.<br /><br />Let the duck rotate around the pond in a circle of radius R/4. Now fox and duck will take exact same time to make a full circle. Now reduce the radius the duck is circling by a very small amount (Delta). Now the Fox will lag behind, he cannot stay at a position as well. Now in due time duck will get to a position we wanted, 3/4*R distance away from shore where fox is on the exact opposite side of the pond. From there duck can swim safely to shore and fly away.SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com7tag:blogger.com,1999:blog-3000085126436711241.post-43995414682607612832011-11-09T11:22:00.000-08:002011-11-13T09:38:33.520-08:00Interview Puzzles and Answers<a href="http://indiadiscuss.com/puzzles/river-crossing-puzzle/">River Crossing Puzzle</a><br /><br />Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, they only have one flashlight and it only has enough light left for seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the campers make it across in 17 minutes? <br /><br />Solution: Send 1 and 2 first, 1 comes back, send 5 and 10, 2 comes back, send 2 and 1 to the other side.<br /><br /><a href="http://indiadiscuss.com/puzzles/3-baskets-puzzle/">3 Baskets Puzzle</a><br /><br />There are three baskets labeled Orange , Apple, Oracle/Apple. And all of them have wrong labels.How to find the correct label by checking only one basket<br /><br />Solution:<br />Open the Orange/Apple basket. If we get Apple then basket labeled as Orange will be "Orange/Apple" basket.SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com6tag:blogger.com,1999:blog-3000085126436711241.post-74326373327493833482011-11-03T11:11:00.000-07:002011-11-24T09:54:30.384-08:0025 Horses PuzzleThis is a<a href="http://indiadiscuss.com/story.php?title=25-horses-puzzle"> classic puzzle</a> which can look simple.<br />Given 25 horses, find the best 3 horses with minimum number of races. Each race can have only 5 horses. You don't have a timer.<br />Now the challange is how we can do it in 7 races.<br /><br /><br /><span style="font-size:130%;">Solution</span><br /><br />We will have 5 races with all 25 horses<br />Let the results be<br />a1,a2,a3,a4,a5<br />b1,b2,b3,b4,b5<br />c1,c2,c3,c4,c5<br />d1,d2,d3,d4,d5<br />e1,e2,e3,e4,e5<br /><br />Where a1 faster than a2 , a2 faster than a3 etc and<br /><br /><br /><br />We need to consider only the following set of horses<br /><br />a1,a2,a3,<br />b1,b2,b3,<br />c1,c2,c3,<br />d1,d2,d3,<br />e1,e2,e3,<br /><br />Race 6<br />We race a1,b1,c1,d1 abd e1<br />Let speed(a1)>speed(b1)>speed(c1)>speed(d1)>speed(e1)<br /><br />We get a1 as the fastest horse<br />We can ignore d1,d2,d3,e1,e2 and e3<br /><br />a2,a3,<br />b1,b2,b3,<br />c1,c2,c3,<br /><br />Race 7<br /><br />Race a2,a3,b1,b2 and c1<br />The first and second will be second and third of the whole setSSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com8tag:blogger.com,1999:blog-3000085126436711241.post-83371815052270072062008-05-02T22:52:00.000-07:002008-05-02T23:00:29.586-07:00Door Toggling Puzzle Or 100 Doors PuzzleThis is a very common interview puzzle. The problem is very simple if you understand it. So the point to note is, do not arrive at the solution so "fast”, if you are asked this puzzle in an interview and if you are not planning to show any acquaintance with this puzzle.<br /><br />Problem goes like this :<br />There are N doors in a row numbered from 1 to N. Initially all are closed.<br />Then you make N passes by the N doors. In pass 1 you toggle the all the doors (1,2,3,4....)starting from the first door. In the second pass you toggle every second door(2,4,6,8,...). In the third pass you toggle all third doors(3,6,9...).Similarly you make N passes.<br /><br />Question is what is the state of door k after N passes.<br /><br />This is a simple but requires clear mathematical Logic.<br />Normally asked version has N=100.SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com77tag:blogger.com,1999:blog-3000085126436711241.post-44084119730351583402007-04-21T11:50:00.000-07:002010-11-20T22:36:57.171-08:00Sum of hats PuzzleThe problem is taken from here :<br />Description goes like this :<br />There are 3 people Abel,Bill and Clark.Three of them have numbers written on their hats.One can only see the numbers written on others hats and can not see the number written on his own hat. Sum of numbers on any two 2 hats is equal to the number on the third hat.Now the following event occurs<br />1. Abel was asked about the number on his hat.He replied "Don't Know"<br />2. Bill was asked about the number on his hat.He also replied "Don't Know"<br />3. Clark was asked about the number on his hat.He also replied "Don't Know"a<br />4. Abel was asked again ,to which he repplied "50"<br /><br />Now the question is how did he know it.And what are the numbers on other people's hats.<br /><span style="font-size:78%;"><a href="http://savenseek.com/page/Puzzle_3_People_and_Assigned_Numbers__tomswayer"><br /></a></span>SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com24tag:blogger.com,1999:blog-3000085126436711241.post-17974217786096497422006-12-27T00:06:00.000-08:002008-05-02T23:14:05.881-07:00Microsoft Interview Question : Polar Bear<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://bp2.blogger.com/_1fu7FaMjWwc/RZIqhROtPfI/AAAAAAAAABQ/xkwd7NXVGgo/s1600-h/bear.GIF"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="http://bp2.blogger.com/_1fu7FaMjWwc/RZIqhROtPfI/AAAAAAAAABQ/xkwd7NXVGgo/s200/bear.GIF" alt="" id="BLOGGER_PHOTO_ID_5013116086265921010" border="0" /></a><br /><br /><br />One of the most asked and well known <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_0">microsoft</span> interview question is that of the walking bear.The question is still asked because a lot of people have either not heard of it or most of them <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-corrected" id="SPELLING_ERROR_1">don't</span> know the correct solution yet.<br /><br />If a bear walks one mile south, turns left and walks one mile to the east and then turns left again and walks one mile north and arrives at its original position, what is the color of the bear.<br /><br />Well,from the very framing of the question it is evident that we r talking about the poles,and all polar bears are white.Y<span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_2">ou</span> can also very well argue that any bear or man walking the same path will reach the same starting position if he is at north<br />pole.The question can also be extended and <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-corrected" id="SPELLING_ERROR_3">that's</span> what we are interested in.<br /><br />The question is how many such points exists on the surface of the globe.<br />Well,whats your answer,is it one or infinitySSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com29tag:blogger.com,1999:blog-3000085126436711241.post-85495636689806806462006-12-20T21:25:00.000-08:002008-05-06T07:42:19.621-07:00Microsoft Puzzle : Coins on the Table<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://bp1.blogger.com/_1fu7FaMjWwc/RYobSBOtPdI/AAAAAAAAAA8/j5JKGRHGAp8/s1600-h/coin.GIF"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="http://bp1.blogger.com/_1fu7FaMjWwc/RYobSBOtPdI/AAAAAAAAAA8/j5JKGRHGAp8/s200/coin.GIF" alt="" id="BLOGGER_PHOTO_ID_5010847531784814034" border="0" /></a><br /><br />This is not one of the classic Microsoft puzzle. I recently heard from a friend. I am listing the problem below.<br /><br />There is a table on which a number of coins are placed. You also know that there are as many coins with Head up as many coins with Tail up. Now you have to divide the coins (number of coins is even) into two equal piles such that number of coins with Heads up and Tails up in either piles be the same. The catch is you are blind folded and you cannot determine the sides (for sure) if you are blindedSSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com28tag:blogger.com,1999:blog-3000085126436711241.post-25978438730314014192006-12-18T22:48:00.000-08:002008-05-06T07:42:19.622-07:00Solution to the Shopkeeper ProblemI don't think I need to post the solution as Christophe has already solved all of them in no time.<br /><br /><div style="text-align: center;"><span style="color: rgb(204, 102, 0); font-weight: bold;">Problem 1: One Side Only (Simple)</span><br /></div><br />This is simply the numbers 2^0,2^1,2^2 ….. that is 1,2,4,8,16 ……….<br />So for making 1000 kg we need <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-corrected" id="SPELLING_ERROR_0">up to</span><br />1, 2, 4, 8, 16, 32, 64, 128, 512.<br /><br /><br /><div style="text-align: center;"><span style="font-weight: bold; color: rgb(204, 102, 0);">Problem 2: Both Sides (Medium)</span><br /></div><br />For this answer is 3^0,3^1,3^2 …. That is 1,3,9,27,81,243,729<br /><br /><br /><div style="text-align: center;"><span style="color: rgb(204, 102, 0); font-weight: bold;">Problem 3: Incremental (Hard)</span><br /></div><br />This is exactly a problem solved by Gray code.<br /><br />Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953<br />A Gray code represents each number in the sequence of integers {0...2^N-1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time.<br /><br />Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011,<br /> 100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010,<br /> 110, 111, 101, 100}.<br /><br />For this answer we need as many blocks as per Solution to Problem 1.<br />For easy understanding let me describe the case where the packets range from 1 to 7 which can be easily extended to 1 - 125 range.<br />Now if we want to make packets of all weights from 1 to & we will do the following<br /><br /> 001 We measure 1kg,using 1kg block.<br /> 011 We measure 3kg by placing 2 kg block also<br /> 010 We remove 1kg block and measure 2 kg.<br /> 110 We add 4kg weight and measure 6kg weight …<br /> ………….<br /><br />Now we can see answer to our problem is Gray code of 7 bits. Now our range is 1 to 125 and not 1 to 127.This can be solved by using appropriate Gray code making the following numbers falling to the end of the sequence you are starting with<br />1111 110<br />1111 111SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com2tag:blogger.com,1999:blog-3000085126436711241.post-69625570560396798502006-12-15T04:26:00.000-08:002008-05-06T07:42:51.823-07:00Job Interview Puzzle: 3 Classic Weighing puzzles :Simple Medium and Hard<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://bp0.blogger.com/_1fu7FaMjWwc/RYKU3dbPKsI/AAAAAAAAAAw/p37c32vuph8/s1600-h/weights.GIF"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="http://bp0.blogger.com/_1fu7FaMjWwc/RYKU3dbPKsI/AAAAAAAAAAw/p37c32vuph8/s320/weights.GIF" alt="" id="BLOGGER_PHOTO_ID_5008729416101997250" border="0" /></a><br /><br />In this post I want to describe about a series of puzzles called weighing puzzles. These puzzle vary in hardness from simple to extremely mathematical involving either expertise in some fields or extreme ingenuity. Either you know it or you figure out it using extreme intelligence. So here is the chance for some people to burn your grey cells.<br /><br />I am putting forward three puzzles with varying range of hardness. Sometimes you may feel the hardest one is very easy for you have already come across the theory, but I still made it the hardest for the people who will be solving it with out knowing the theory behind it, giving them an option to figure out a small part in evolution of computational history.<br /><br />There is a shopkeeper who wants to weigh things who has a common balance. He must be in a position to weigh things of all possible integral weighing units from 1 to a given maximum sum. The question will be either about how many weights you will need or how will you weigh.<br /><br /><span style="font-size:130%;"> </span><div style="text-align: center;"><span style="font-size:130%;"><span style="font-weight: bold; color: rgb(255, 102, 0);">Problem 1: One Side Only (Simple Interview Question for Phone Screening usually)</span></span><br /></div><br />In this version of the problem shopkeeper can only place the weights in one side of the common balance. For example if shopkeeper has weights 1 and 3 then he can measure 1,3 and 4 only. Now the question is how many minimum weights and name the weights you will need to measure all weights from 1 to 1000. This is a fairly simple problem and very easy to prove also.<br /><br /><br /><div style="text-align: center;"><span style="color: rgb(255, 102, 0);font-size:130%;" ><span style="font-weight: bold;">Problem 2: Both Sides (Medium:5 to 10 mins onsite interview question)</span></span><br /></div><br />This is same as the first problem with the condition of placing weights on only side of the common balance being removed. You can place weights on both side and you need to measure all weights between 1 and 1000.For example if you have weights 1 and 3,now you can measure 1,3 and 4 like earlier case, and also you can measure 2,by placing 3 on one side and 1 on the side which contain the substance to be weighed. So question again is how many minimum weights and of what denominations you need to measure all weights from 1kg to 1000kg.<br /><br /><div style="text-align: center;"><span style="color: rgb(255, 102, 0); font-weight: bold;font-size:130%;" >Problem 3: Incremental (Hard)</span><br /></div>This is an altogether different one in the same scenario. You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing.<br />It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only.<br /><br />Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar.<br /><br /><br />Please post your solutions as comments.Solution will be posted soon in the blog.If any where its obfuscated or simple wrong pls feel free to correct.SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com24tag:blogger.com,1999:blog-3000085126436711241.post-88984276885025133782006-12-11T10:54:00.000-08:002008-05-06T07:42:51.824-07:00Solution to the 13 Balls ProblemSolution for 12 Ball Problem<br /><br />NOTE : N represents a normal ball<br /><br />Name the 12 balls as A1,A2,A3,A4,B1,B2,B3,B4 C1,C2,C3 and C4.We will weigh A's on one side and B's on the other side.<br />A1 A2 A3 A4 <---> B1 B2 B3 B4<br />If Both weighed same then the odd ball is among C's.<br />We have to find the odd ball among 4 balls using 2 weightings.For that we balance<br /><br />C1 C2 with C3 N.<br /><br />Now if C1 C2 equals C3 N then C4 is the odd one.<br /><br />Now suppose C1 C2 is heavier than C3 N then we compare<br />C1 C3 to N N<br />Now if C1 C3 equals to N N the C2 is the odd ball.<br />If C1 C3 is lighter than N N, then C3 is the odd ball.<br />If C1 C3 is heavier than N N then C1 is the odd ball.<br /><br /><br />Coming to the situation where the first weighing resulted in unequal balance.Lets assume A's are heavier than B's.<br />ie .<br /><br />A1 A2 A3 A4 > B1 B2 B3 B4<br /><br />Now we compare<br /><br />A1 A2 B1 B2 to N N N B4.<br /><br /><br />if A1 A2 B1 B2 > N N N B4<br /><br />The odd ball is among A1 A2 or B4 and we also know that A1 A2 > B4 N.To find out the odd ball among A1 A2 and B4 we do compare<br /><br />A1 B4 to N N .<br /><br />if A1 B4 > N N then<br /> A1 is the odd ball<br />if A1 B4 < b4 =" N" b2 =" N"> N B3 which we have already shown how to solve.<br /><br /><br />Solution for 13 ball problem is easy if we could solve 12 ball problem.For that lets assume we have an extra ball C5.Now if A's and B's dont weigh same we have all the steps already calculated.<br /><br />Now if A's and B's weigh same then the odd one is among C's.<br /><br />Now we compare<br /><br />C1 C2 to C3 N.<br /><br />If C1 C2 = C3 N then we can find out the odd ball from C4 and C5 by comparing it with any normal ball.<br />Else if C1 C2 > C3 N then we compare<br /><br />C1 C3 to N N.<br />If C1 C3 > N N then C1 is the odd ball<br />If C1 C3 = N N then C2 is the odd ball<br />If C1 C3 < N N then C3 is the odd ballSSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com19tag:blogger.com,1999:blog-3000085126436711241.post-73876777410062329812006-12-11T00:00:00.000-08:002008-05-06T07:42:51.824-07:0013 Balls problem : One of the Hardest Interview Questions<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://bp3.blogger.com/_1fu7FaMjWwc/RX0UYqDmRdI/AAAAAAAAAAk/8-mzmYuBX6Q/s1600-h/13balls.GIF"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="http://bp3.blogger.com/_1fu7FaMjWwc/RX0UYqDmRdI/AAAAAAAAAAk/8-mzmYuBX6Q/s320/13balls.GIF" alt="" id="BLOGGER_PHOTO_ID_5007180774544655826" border="0" /></a><br /><br />One of the most classic puzzles involving balls is figuring out the odd one out using common balance.There are many levels of puzzles based on the same concept for different levels of interviews - Simple ones for phone interviews to the most gruelling 1 hour <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_0">hard work</span> needing hard ones.<br /><br />Problem space<br />The general problem is you will be given n balls and one of them is either heavier or lighter and you are asked to find out the minimum number of <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_1">weighings</span> using a common balance required to find out the odd one out.<br /><br /><span style="color: rgb(204, 102, 0);">Example 1:8 Balls,Odd ball being heavier</span><br /><br />This is the simplest question among the lot and is often used during phone screenings.The question is to find out the minimum number of <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_2">weighings</span> required to spot the odd heavier ball among 8 identically looking balls using a common balance.Answer is 2 and the solution is given in the next paragraph.<br /><br />For simplicity let us name the balls as A1,A2,A3,B1,B2,B3,C1 and C2.We weigh with A's on one side and B's on the other side of the balance.If both sides are equal this means the heavier odd ball is among C1 and C2.We can figure out the heavier ball with one more weighing.If A's are heavier than B's then the heavier odd ball is among A's.Now we balance A1 and A2.If both are same then A3 is the odd ball or else the heavier one of A1 and A2 .Thus, we can find out the heavier ball using only 2 <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-error" id="SPELLING_ERROR_3">weighings</span>.<br /><br /><br /><br /><span style="color: rgb(204, 102, 0);">Example 2:8 Balls,Odd ball can be either heavier or lighter than the rest.</span><br /><br />This is a little trickier to solve.Let us name the 8 balls as A1,A2,A3,B1,B2,B3,C1 and C2.Now weigh with A1,A2,A3 on one side and B1,B2,B3 on the <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-corrected" id="SPELLING_ERROR_4">other side</span>.If both weigh equal then the odd ball is among C1 and C2.Now we know that A's and B's are all normal ones we can weigh C1 with A1 and check whether C1 weighs the same as the normal ball.In this way, we can figure out in one weigh which of C1 and C2 is odd.Now if A's weighed more than B's then we know for sure C's are normal ones.Now lets assume A's heavier than B's and we still <span onclick="BLOG_clickHandler(this)" class="blsp-spelling-corrected" id="SPELLING_ERROR_5">don't</span> know whether the odd is among A's or B's.<br /><br />We know<br />A1 A2 A3 < B1 B2 B3<br /><br />Now we compare<br />A1 B2 B3 to B1 C1 C2 .<br />Now if the A1 B2 B3 is heavier than B1 C1 C2 Then it means the odd ball is among A1 and B1.If A1 B2 B3 is lighter than B1 C1 C2 then the odd ball is among B2 and B3.If A1 B2 B3 equal to B1 C1 C2 then odd ball is among A2 and A3.So we have zeroed down to 2 balls.Now its very easy as we can compare any of the normal ball with one of the 2 balls.So answer is 3,ie in 3 weighings we can find out the odd ball.<span style="font-weight: bold;"><br /><br /></span><span style="font-size:130%;"><span style="color: rgb(204, 102, 0); font-weight: bold;">Problem</span></span><br /><br />You are given 13 balls.The odd ball may be either heavier or lighter.Find out the odd ball in 3 weightings.(There is an equally difficult smaller version of the puzzle involving 12 balls also but because both require the same solution technique i am leaving that problem) Hint: I have already given the hint for this question.This mammoth looking task only requires the techniques already discussed in the page.If you have not read all the steps mentioned above i request you to please go through the above solutions carefully.<br /><br /><br />Solution will be posted soon ....<br />Pls post your solution as comment ...<br />Waiting for a trickier smarter solution ....SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com108tag:blogger.com,1999:blog-3000085126436711241.post-72870489401307440562006-12-05T11:30:00.000-08:002008-05-06T07:42:51.824-07:00Google Interview Puzzle : 2 Egg Problem<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://bp0.blogger.com/_1fu7FaMjWwc/RXXKItdfAvI/AAAAAAAAAAU/IMB2cd0id9E/s1600-h/eggs.gif"><img style="margin: 0px auto 10px; display: block; text-align: center; cursor: pointer;" src="http://bp0.blogger.com/_1fu7FaMjWwc/RXXKItdfAvI/AAAAAAAAAAU/IMB2cd0id9E/s320/eggs.gif" alt="" id="BLOGGER_PHOTO_ID_5005128811883201266" border="0" /></a><br />My intention here is not to trouble Google interviewers. I was just collecting some classic puzzles and found this one and a small Google search showed me that this is a Google interview puzzle to my pleasant surprise. But many of the answers I found were either wrong or totally twisted. I am making no surety of the answer I give and I am open to your remarks or suggestion or corrections.<br /><br /><br /><div style="text-align: center;"><span style="font-size:130%;"><span style="color: rgb(204, 102, 0);">The Standard Problem in simple writing goes like this:</span></span><br /></div><br /> * You are given 2 eggs.<br /> * You have access to a 100-storey building.<br /> * Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.<br /> * You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.<br /> * Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process<br /><br /><br /><br />If you are one of the people who likes to solve a puzzle before seeing the answer you must quit the blog now and come back later for checking the answer.<br /><br /><br />Now that this is a Google interview question I am taking the normal "Interview-Style" of solving a problem. Simply saying thinking aloud through the solution from worst to the best correcting the flows optimizing the solution or taking the 5-minute hard thinking acting pause to a problem, which you know already and just want to make your interviewer think that you are a challenge lover.<br /><br /><br /><div style="text-align: center;"><span style="font-size:130%;"><span style="color: rgb(204, 102, 0);">Solution</span></span><br /></div><br />Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.<br /><br />Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.<br /><br /><br />Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.<br /><br /><br />(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)<br /><br />Now let x be the answer we want, the number of drops required.<br /><br />So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.<br /><br />Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.<br /><br />Lets take the case with 16 as the answer<br /><br />1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops<br />1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops<br />1 + 13 45 .....<br />1 + 12 58<br />1 + 11 70<br />1 + 10 81<br />1 + 9 91<br />1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task<br /><br /><br />Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.<br /><br />So we could write it as<br /><br />(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.<br /><br />Let 1+p=q which is the answer we are looking for<br /><br />q (q+1)/2 >=100<br /><br />Solving for 100 you get q=14.<br />So the answer is: 14<br />Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).<br /><br />Please feel free to correct or post any comment on the solution or the answer.<br /><br />Links I found useful<br /><div style="text-align: left;"><br /><br /><a href="http://ite.pubs.informs.org/Vol4No1/Sniedovich/" name="abstract">OR/MS Games: 4. The Joy of Egg-Dropping in Braunschweig and Hong Kong</a><br /><br /><a href="http://techinterview.org/Puzzles/fog0000000142.html">Puzzle from Techinterview.org</a><br /><br /><a href="http://blog.taragana.com/index.php/archive/google-and-the-puzzle-of-dropping-eggs/">http://blog.taragana.com/index.php/archive/google-and-the-puzzle-of-dropping-eggs/</a><br /><br /><br /></div>SSPhttp://www.blogger.com/profile/16962935028110792196noreply@blogger.com275