# Brain teaser Interview Questions

interview questions shared by candidates

## Brain teaser Interview Questions

Suppose you had eight identical balls. One of them is slightly heavier and you are given a balance scale . What's the fewest number of times you have to use the scale to find the heavier ball? 45 Answers3 times. (2^3 = 8) Two. Split into three groups of three, three, and two. weigh the two groups of three against each other. If equal, weigh the group of two to find the heavier. If one group of three is heavier pick two of the three and compare them to find the heaviest. Brian - this would be correct if you in fact were using a weighing scale, and not a balance scale. The ability to weigh one group against another with a balance scale allows Marty's answer to be a correct answer. Although - the question as worded provides a loophole. If it had been worded as "What's the fewest number of times you have to use the scale to CONSISTENTLY find the heavier ball", then Marty's answer would be the only correct answer. However, it is possible that you could get lucky and find the heavier ball in the first comparison. Therefore, the answer to the question as stated, is ONE. Show More Responses This question is from the book "How to move Mt Fuji".... Marty has already got the right answer. Actually Bill, by your interpretation of the question the answer is zero, because you could just pick a ball at random. If you get lucky, then you've found the heaviest ball without using the scale at all, thus the least possible amount of times using the scale would be zero. The answer is 2, as @Marty mentioned. cuz its the worst case scenario which u have to consider, otherwise as @woctaog mentioned it can be zero, u just got lucky picking the first ball.... None- weigh them in your hands. Assuming that the balls cannot be discerned by physical touch, the answer is 3. You first divide the balls in two groups of 4, weigh, and discard the lighter pile. You do the same with the 4 remaining, dividing into two groups of 2, weighing, and discarding the lighter pile. Then you weigh the two remaining balls, and the heavier one is evident. 2 3a+3b+2 = 8 if wt(3a)==wt(3b) then compare the remaining 2 to find the heaviest if wt(3a) !== wt(3b) then ignore group of 2 discard lighter group of 3 divide the remaining group of 3 into 2+1 weigh those 2 If == the remaing 1 is the heaviest if !== the heaviest will be on the scale With the systematic approach, the answer is 3. But, if you randomly choose 2 balls and weigh them, and by coincidence one of these two is the heavier ball, then the fewest number of times you'd have to use the scale is 1. Although the real question is: are the balls truly identical if one is heavier than the rest? just once. Say you are lucky and pick the heavy ball. One use of the scale will reveal your lucky choice so once, or the creative answer zero if you allow for weighing by hand Without judging by hand: Put 4 balls on one side, and 4 on the other. Take the heavier group and divide again, put 2 balls on one side, and 2 on the other. Take the 2 that were heavier, and put one on each side. You've now found the heaviest ball. This is using the scale 3 times, and will always find the right ball. Show More Responses None. They are identical. None is heavier. 2 weighings to find the slightly heavier ball. Step 1. compare 2 groups of three balls. Case 1. if they are both equal in weight, compare the last 2 balls - one will be heavier. case 2. If either group of 3 balls is heavier, take 2 balls from the heavier side. compare 1 ball against the 2nd from the heavy group result 1. if one ball is heavier than the other, you have found the slightly heavier ball. result 2. if both balls are equal weight, the 3rd ball is the slightly heavier ball. Easy Shmeezi Fewest - get lucky and pick the heaviest one. But wait! How would you know it is the heaviest one by just weighing one ball? Your logic is flawed. Two groups of four. Split heavier one, weigh. Split heavier one, weigh. 3 times. i think its 3. i would take it like this OOOO OOOO then OO OO then OO problem solved. i do this everyday. bye. praise be to allah. thats it. It's 2. Period. If you can't figure it out look it up online or in "How Would You Move Mount Fuji" (like somebody else said). This is one of the most basic brainteasers you could be asked in an interview. The answer is 2. 1) Divide the balls into 3 groups. 2 piles with 3 balls each, 1 pile with 2 balls. 2) Weigh the 2 piles of 3 balls. If both piles are the same weight, discard all 6 and weigh the last 2 to find the heavier one. 3) If 1 pile of 3 is heavier than the other, discard the lighter pile and the pile of 2 balls. Weigh 2 of the remaining 3 balls from the heavier pile. If both of the weighed balls are equal, the last ball is the heavier one. 2=if all the balls are identical and you pick up the first...weigh it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. 1=if all the balls are identical and you pick up the first...balance it and the second one is lighter or heavier then you've found the heavier ball in the least amount of attempts. Amy is 100% correct for the following reason: everyone (except Amy) is solving the theoretical problem. The practical side of the problem - notwithstanding jimwilliams57's brilliant observation that if one weighs more than the others IT IS NOT IDENTICAL (would have loved to see the interviewer's face on that one) - in order to 'weigh' them on a scale, one has to pick them up, therefore, you will immediately detect the heavier one without weighing: pick-up three and three ... no difference, no need to weight. Pick-up the remaining two to determine the heavier one. Steve First off, take yourself through the process visually and forget square roots, that doesnt apply here and here is why: The question is the Minimum, not the MAXIMUM. BTW, the max would be 7 ( 8-1); you are comparing 2 objects, so 1 ball is eliminated automatically in the first step. Anyway, you have a fulcrom of which you are placing 2 of 8 objects on each end. If by chance you pick the slightly heavier object as one of the two balls, you have in fact, found the slightly heavier one in the first round... btw dont be a smartass with your interviewer, he is looking for smarts not smarmy;) Show More Responses Respectfully, the folks who are answering "3" are mathematically modeling the nature of the balance incorrectly. Performing a measurement on a balance scale is not binary. It is trinary. Each measurement gives you one of three responses: The left is heavier, the right is heavier, or they are equal. So while you do need three binary bits to specify a number from one to eight, you need only two TRINARY-DIGITS Formally, you want the smallest value of n such that 3^n >= 8. The answer is 2. Note that you could add a ninth ball, and still, you'd only need to make two measurements. Of course, the smarty pants answer would be one. Just pick two balls at random and be lucky to have chosen the heavy one. But you're not guaranteed to be able to do it in just one measurement. English isn't my mother tongue... What is a balance scale? If looking up on Google, I find some devices with two bowls on a bar bearing in the center. Hence, the answer is once (if I'm luck enough to select the heavier ball in teh first measurement) If a balance scale allows to measure only one ball at a time, then it would take two measurements, unless you'd have more information on the weight, which is not listed here, hence doesn't exist in the context of the question^. 3 times. Not having looked at the other comments, hopefully, I am the 26th to get this right. Put the balls 4 and 4 on the scale, Take the heavier side and place those balls 2 and 2 on the scale. Take the heavier side and place them 1 and 1 giving the heaviest ball. OK, now I read the comments and see that the people, like the question are divided into to groups, systematic approach people that say 3 (like I did) and analytic people that say 2. It takes a systematic person (me) a minute to get the answer. I'm guessing it took the analytic 5 minutes just to interpret all the ramifications of the question, i.e. they aren't idenitical if..., do it by hand..., get lucky. minimum is 1 (if lucky - 25% chance by picking 2 balls at random) & max is 2 (using most efficientl process to absolutely determine without luck - 3/3/2 scenario) While Symantec was busy weighing my balls I took a job with NetApp.... They need to focus on hiring good, capable security engineers, not weighing their balls. The point of these interview questions is to both check your logical brain function and to hear how you think. Most of you are just posting jerk off answers trying to be funny, or you are really dumb. These answer get you nowhere with me in an interview. Think out loud, go down the wrong path back track try another logic path, find the answer. None of this "0 if you use your hands". That is fine if you are interviewing for a job in advertising where creativity is desired, nobody wants you writing code like an 8 year old. You have 12 balls, equally big, equally heavy - except for one, which is a little heavier. How would you identify the heavier ball if you could use a pair of balance scales only twice? The problem is based on Binary Search. Split the balls into groups of 4 each. Choose the heavier group. Continue till you get the heavier ball. This can be done in log(8) (base 2) operations, that is, 3. Since there is only one scale available to weigh. You first divide the balls in half. Weigh each group, take the heaviest group. This is using the scale twice so far. Now, divide the previous heaviest group into half, weigh both groups. Take the heaviest. Divide this last group and take the heaviest. This is the heaviest ball. We have used the scale 5 times. Show More Responses Would it be wrong to say for a sample size as small as 8, we might as well not waste time thinking about an optimal solution and just use the scale 7 times, as this will be more efficient than coming up with an ideal solution prior to using the scale? 3. I stumbled across this while looking for something else on Google but I had to answer. It is 2, split balls into 2,3 and 3. weigh the 2 groups of 3 against each other. If equal weigh the group of 2 and the heaviest is obvious. If they are not equal keep heavy group of 3 and weigh 2 of the balls. if equal heaviest ball is one you didn't weigh. If not equal the heavy ball is obvious. 2 times. 8 balls. 1st step: [3] [3] [2] 2nd step: [[1] [1] [1]] [[1] [1] [1]] [[1] [1]] No idea The fewest number of times to use the scale to find the heavier would be Eight to One times ? It will actually be 1 because the question asks what's the fewest amount of times which is one because you could just get lucky you can use any method you want it would still be one because that is the fewest amount of turns you can have It's one. The fewest number of tries on using a balance scale would be one. If you put one ball on each side and one is heavier, you have the found the heavier ball. Use an equilateral triangular lamina which is of uniform mass throughout. It is balanced on a pole or a similar structure. Steps: Place 2 balls at each corner (total 6 balls) i. if the odd ball is one of those, one side will either go up or go down. Now repeat the process with one ball at each corner including the 2 unbalanced ones. ii. if balance is perfect, repeat the process with the remaining two balls and one of the already weighed balls. test answer 2016-01-12 00:34:07 +0000 Show More Responses You would not be able to find a ball heavier than the others. All eight balls are identical; therefore, they must all be the same weight. Correct answer has already been posted. I just want to contribute some theoretical analysis. Given N balls, one of them is heavier. Finding out the ball requires log3(N) trit of information. (trit is the 3-base version of bit). Each weighing may give you one of the three outcomes: equal, left-heavier, right-heavier. So the amount of information given by each weighing is upper-bounded at 1 trit. Therefore, theoretical lower-bound for number of weighings in the worst case is log3(N), which is actually attainable. So 27 such balls need only 3 weighings and 243 balls need only 5 weighings, etc. |

### Explore Microsoft at Microsoft was asked...

Devise a way to make sure there is always mlik in my fridge. 31 AnswersSuper vague question. Looking back, I realized that they were looking for me to ask a LOT of questions to make the question clearer and to see my thinking process. put a female mammal in there spill some and it was always be there Show More Responses Depends on the position one is applying for - who do you want to be directly responsible for it and who will have oversight and authority to implement the plan? the owner of the fridge? Then establish a system to prompt the owner to check milk level and process for him/her to obtain the milk. the interviewee? Take direct responsibility to check and obtain or delegate the responsibility to an appropriate person, e.g. set up automatic delivery schedules.... Administer a drug to the interviewer that makes him mortally dependent on milk that is six days old. If he/she is going to ask ridiculous questions, ones answers should be equally outlandish. Just start vomiting.... Put in a container of milk and never drink any. Have a slot for a gallon or half gallon of milk that measures the weight of the container. One the milk runs low the refridgerator could light up a light, order milk online, text the owner, etc. The control scheme would have to take into account the possibility that the milk was removed for use or discard. An adjustable time delay with a default of 2 hours would work. Greater than 2 hours and the indicator/message is tripped/sent. the one about putting a female mammal in the fridge is delightful and completely out of the box (pun intended)...but end result is that thats ensuring a (live) animal is in the fridge and not neccessarily milk :-) how bout directly piping in milk from a dairy once a day / periodically based on expected consumption (the functional nature of the fridge is then changing, of course...) Get a bunch of UHT long-life milk. Can easily be stored outside the fridge without spoiling Get a bunch of UHT long-life milk. Can easily be stored outside the fridge without spoiling Er, go to the store before you run out? Live in the supermarket. Show More Responses Going back to the initial comment made by "Interview Candidate", solving this type of problem, where there are varying level of solutions, it comes down to the requirements for the solution. You could get fairly outlandish, as many of the responses show. How strict is the requirement for "always", for example. A solution that is 90% effective is VERY different in scope and cost to a solution that needs to be 99.999% effective. The solution can vary from a post-it reminder to get milk to an application that automatically places an order for milk to a grocery deliverer (as mentioned by "Former Msoft Candidate"). There's the marketing aspect of it as well. Who's the solution targeted to? For Bill Gate's personal use? Or for mass marketing (if so, what's the target market segment)? Even though the interview was for Microsoft, with past history for enigmatic interview questions, my first response would be to try to determine the intent of the question. Does the interviewer want outlandish responses to show that you are a creative thinker? Or do they want to figure out the steps that you would follow to solve a problem? Going back to the initial comment made by "Interview Candidate", solving this type of problem, where there are varying level of solutions, it comes down to the requirements for the solution. You could get fairly outlandish, as many of the responses show. How strict is the requirement for "always", for example. A solution that is 90% effective is VERY different in scope and cost to a solution that needs to be 99.999% effective. The solution can vary from a post-it reminder to get milk to an application that automatically places an order for milk to a grocery deliverer (as mentioned by "Former Msoft Candidate"). There's the marketing aspect of it as well. Who's the solution targeted to? For Bill Gate's personal use? Or for mass marketing (if so, what's the target market segment)? Even though the interview was for Microsoft, with past history for enigmatic interview questions, my first response would be to try to determine the intent of the question. Does the interviewer want outlandish responses to show that you are a creative thinker? Or do they want to figure out the steps that you would follow to solve a problem? As Interview Candidate said, this is clearly a question designed to explore your problem solving skills rather than to elicit a specific unitary answer. The "left field" nature of this sort of question can really throw those unfamiliar with the technique - I am reminded of the "good cop / bad cop" routine that I endured once in ignorance that it was a recognized interview technique (ironically, they offered me the job, but I declined because I didn't want to work with jerks like that). As for the milk question, I agree that the "correct" response is to explore the requirements in more detail. Make the refrigerator "Moo" when the milk slot is empty. It would get on your nerves so badly that you would run out and buy more. As Interview Candidate said, this is clearly a question designed to explore your problem solving skills rather than to elicit a specific unitary answer. The "left field" nature of this sort of question can really throw those unfamiliar with the technique - I am reminded of the "good cop / bad cop" routine that I endured once in ignorance that it was a recognized interview technique (ironically, they offered me the job, but I declined because I didn't want to work with jerks like that). As for the milk question, I agree that the "correct" response is to explore the requirements in more detail. Put powdered milk in the fridge By all means I will find out the extent and expense perimeters allowable for my solution, but I will have to assume that the question is open to my own interpretation and not bound by creative limits. Thus, a generic technocratic solution (considering that I am applying for a job with a technology company) to cater to all parameters is sought here. My proposed answer would go along the lines of: Build or customise a modern refrigerator that can be connected to the internet (deluxe fridges with internet connectivity are already available), is chock full of sensors and nanosensors, and can be programmed (via the Windows Mobile operating system of course!) to issue reminders to the household members via SMS, email, onscreen display at the fridge door, and text--to-speech verbal reminders, all issued before milk runs out. Presumably, to ensure higher accuracy, reliability and user flexibility in ensuring milk supply, this fridge provides a special container for milk to be poured into it for dispensing. The front of the fridge contains a standard dispenser mechanism for the milk. The milk container is antibacterial and nanoparticles on the plastic ensure minimal bacterial proliferation of the milk over time. Sensors detect the level of milk protein in the container, as well as the level of lactic acid buildup. This ensures that only milk is poured and kept in the container. Milk that is starting to go bad is detected, and warning messages are issued ahead of time to remind household members to clear and clean the container (as well as the antibacterial tubing and liquid flow path of the milk leading to the dispenser unit) and refill it with a fresh supply of milk. To provide flexibility and automation, the system allows the user to program the Windows Mobile interface to automatically place an order for milk delivery with a local internet-savvy supermarket or grocer. Other programming options include giving household members a choice of flavours when ordering from the e-grocer the next time around (to have a change of flavour or to cater to different domestic uses) or for the household members to send a specific message to the e-grocer concerning milk or any other food item that is monitored by the fridge. This is the basic schema for a typical household for one standard type of milk to be stored in the fridge. If household members desire more than one kind of milk to be kept in the fridge at any one time -- for example, milk of different flavours or animal origin -- the fridge can be customised with two sets of milk container/dispenser mechanisms. put milk in and weld it shut Get a job so you can buy fresh milk regularly. Put it in the fridge before the previous container is empty. Alternatively, get a VERY large fridge and install a cow, a warming-blanket for the cow, fresh air supply, feeding and waste disposal, and a milking machine. Get a job so you can ensure a supply of bull semen to impregnate the cow and replace the cow as needed. My experience tells me that this question is not about the question at all. Therefore,I would ask enough questions to determine the point of the question. As others have said and I concur, I'm pretty sure that problem solving skills are at least part of the point. Another aspect to this line of questioning might be that the interviewer/interviewing team may just want to see how I think, how fast I think, how creative I am, and how far do I delve into answering the question. Are they looking for complex abstract inventions or is a post it note on the fridge enough to cover the problem. If I'm talking to techno wizards or technical experts, they may want to hear a very intellectually abstract answer. If I'm sensing that the person/team just wants to get to the bottom line of keeping milk in the fridge, then I would keep it short and sweet. Bottom line for me would be to probe enough to get some kind of feel for or sense of what they are looking for and then give it my best shot. Show More Responses The heck with the milk. If someone can devise a way so my refrigerator is always full of beer, please post back! This is similar to the problem of always making sure that we get water in out bathrooms. For this we need to make sure that there is always some water in the tank on the roof top. We have an automated motor which pulls up water from ground in to the tank if the level of water in the tank drops below a threshold value. The motor gets turned off automatically when the water level reaches its max in the tank. Matter of redundancy. Measure variability of milk consummation and calculate mean and STDEV. Start milk volume at mean consumption volume + 6*STDEV and fill up to that level every day. Would require a pretty outlandish black swan milk event to exhaust milk volume (Toddler mega party) or include toddler mega party for calculation of mean and STDEV. Make the door clear (glass) stop drinking milk... This is easy - Take an electronic weigher, connect it to an RaspberryPI, program a Python script to auto order the milk (via WiFi) from a delivery service when it hits a specific weight... but wait, this is Microsoft! Got Milk? Put the Milk in the fridge and lock the fridge so that no one can open so "Milk will be always in the fridge :-)" as no one can take it out. |

### Trader at Morgan Stanley was asked...

If two cars are traveling in a two lap race on a track of any length, one going 60 mph and the other going 30mph, how fast will the slower car have to go to finish at the same car to finish at the same time? 30 AnswersIt's impossible, the faster car will be done the race by the time the slower car finishes the first lap. the answer to this question lies on how long the race track, we can solve its mph if we know how long the track we be. Well, this is interesting because there are no track details and makes for multiple answers through ambiguity and assumptions. i.e. One could assume that it is a circular track and that the two lanes are very wide and that one car is on the outermost furthest from the centre and the other is on the track very near the centre. The circumference of each track therefore could be such that the faster car would have to travel twice the distance that the slower car has to and therefore the two cars would arrive at exactly the same time. The is why cares on a racetrack must start at offsets to each other or have their times corrected in some other way! In real-life, this is highly unlikely however it does demonstrate my point. Show More Responses I agree with the first answer (by the Interview Candidate). When the slow car completes the first lap, the fast will complete the second lap. It does not matter how fast the slow car goes on the second lap; it cannot win... 90 mph Wouldn't the slow car just need to go 60mph? It doesn't say that the fast car is going double the slow cars speed only that the slow car is going 30 mph and the fast is going 60mph. The question is a trick. It says how fast will the slower car have to go to finish "AT THE SAME CAR" to finish at the same time? It can go any speed!! It will always finish at the same car (2nd) at the same time. The car isn't changing!!! I'm assuming that the question, as typed, was entered incorrectly and that it should be worded, "How fast will the slower car have to go to finish at the same time as the faster car?" The answer is 30mph. Because that's how fast the slower car is going. Nowhere in the question does it state that the cars are at the same point on the track. The slower car is currently halfway between the faster car and the end of the race. The two pieces of missing info are: 1. How long is the distance of the track and 2. The distance that each of the cars has already traveled on the track. If you have that info then you can figure it out. The two pieces of missing info are: 1. How long is the distance of the track and 2. The distance that each of the cars has already traveled on the track. If you have that info then you can figure it out. I totally agree with wildfire. Did you just say, "If two cars are traveling in a two lap race on a track of any length, one going 60 mph and the other going 30mph, how fast will the slower car have to go to finish at the same car to finish at the same time?" WTF? Are you having a stroke? Try to raise both hands above your head. OK, now smile for me. And would you please try to say a complete sentence? The way the question is currently worded, it does not indicate any of the following: 1. Whether the two cars started at the same place, at the same time (we can infer "same place, same time" because it is a race), 2. Whether either car has traveled any distance at all (if yes, then how far; if the slower car has traveled one lap, then the faster car has finished, and if no, then the answer is 60 mph), 3. What is the shape of the track (to Alanjai's point, a regular track requires offset starting positions, whereas a figure-8 track with fixed lanes would not), and finally 4. Why the question is worded so poorly ("to finish at the same car to finish at the same time" ... I mean, come on, that's practically not even literate). Show More Responses Speed a = Car A speed = 60 mph b = Car B speed = 30 mph t = Time Elapsed (in hours) d = Race Distance (in miles) ((t * a) = distance traveled by Car A) - d = Distance Remaining Car A = dra ((t * b) = distance traveled by Car B) - d = Distance Remaining Car B = drb x= mph that Car B has to drive for the remainder of the race (drb/dra)= y y * a = x or ((t*b)-d))/((t*a)-d)) = y y * a = x Example: t = 1 hour d = 240 miles ((1 * 60) - 240 = 180 [distance remaining Car A] ((1 * 30) - 240 = 210 [distance remaining Car B] 210/180 = 1.666666667 1.666666667 * 60mph = 70 mph, the speed that Car B has to drive for the remainder of the race. oh, yeah... in case you couldn't guess, I'm a Digg user. oh, yeah... in case you couldn't guess, I'm a Digg user. I agree with wildfire. This question is not grammatical and is unsolvable as written. The point seems to be that you should read the entire question (review the entire problem) before jumping in to solve the question that is immediately apparent. So, attention to detail is important at this company. Assuming the question was mistyped into this discussion, and they want to know how fast the second car would have to go to finish at the same time as the first car, then the answer is: infinitely fast. The question is better expressed as: A car is driving a sixty-mile path at thirty miles per hour. At the half-way point, the driver wants to speed up so his average speed at the end of the path is sixty miles an hour. How fast does he have to go? At the half-way point (30 miles) he has taken one hour for his drive. To average 60 MPH, he would have had one hour for the entire road. Therefore he has no time left, and must travel infinitely fast (for zero time) to average 60 MPH. It doesn't matter what answer you give, it is how you come to your conclusion that counts here. There is missing information on purpose because they want to see how you solve problems, not if you can solve problems quickly. The cars, the track the speed doesn't matter, it is the questions you ask and the information gathering that counts. Since there are only 2 cars in the race, the race is over and the instant one of the cars passes the finish line. One car finishes first, the other finishes second by default. The answer is that it doesn't matter how fast either of them are going, or how long the track is. They will always finish at the same time (not to be confused with "finishing with the same lap time"). I agree with SteveC. Once the either car finishes, the race is over. The question was clearly misworded. If not, most of you would have failed. The best answers here are from toolbelt_1 and dadag. Morgan Stanley needs people with exceptionally strong quantitative abilities and communication skills. The interviewer gives you a vaguely worded question to see (1) how you would gather the rest of the information and (2) how you would use it. In the course of a real workday your manager, client or other stakeholder will rarely provide a perfectly well-defined request for information. In the heat of the moment, important questions are worded quickly and vaguely, yet your performance will be judged based on how well you respond. One of your most crucial job skills is determining true requirements through timely and effective follow-up communication, intuition and experience. Show More Responses Both cars will finish at the same time if the track length was 0. This is typical of Morgan Stanley. Search a bit more and read about the lack of communication and clarity within this company--and when the result is as it should be (wasted time and effort) they blame the lower level worker as Al did above. If you ask for more information, you get more of the same -- confusion. Al might ALSO work for Morgan Stanley and makes a flimsy excuse for wasted time in having to track down pertinent information for the task. He makes no mention of the increasing frustration, lost productivity and the poor underlings that take the blame for poor managers. There are a few upper level managers who communicate and instruct their reports very well. It is a breathe of fresh air. They will tell the report the objective, quick background and the task and then you go do it. That simple. Others have more time for backstabbing, gossip and slimy character demonstrations than instructing their reports. No wonder they will never catch up to Goldman Sachs. They just don't get it. it's quite easy guys, just think: 30 mph is the current speed x is the race lenght 60 mph is the target average speed so theanswer is 30*(miles raced/ total race) + speed to achieve*(iles missing/tot. race) = 60 speed = i know that yu can dothis.....;) I'm pretty sure this is how the question is supposed to be worded which makes Mike's response correct. If two cars are traveling in a two lap race on any length track, one going 60mph for the entire race and one going 30mph to begin the race, how fast must the slower car travel for the rest of the race once the faster car finishes its first lap to finish at the same time as the faster car? If this is the case then we can do the following. distance = rate X time let d = the length of the track. After the fast car completes one lap the slow car will have completed one half lap, or .5d So the fast car has d left to go and the slow car has 1.5d left to go. since distance = rate x time, and the fast car is going at 60mph, we have d = 60t where t is time. For the slow car, if we let x be the rate it will go (so what we're ultimately trying to solve for, we have 1.5d = xt. now substituting d = 60t in we have 1.5 x (60t) = xt Since the track has some distance, t cannot be zero so we can divide t out leaving 1.5 x 60 = x = 90mph. Hence the slow car would have to travel 90mph the second lap to finish at the same time as the fast car. Make it simple, it depend on the fast car, if fast car got no problem( like break down , flat tires...), it hard to pass. The slow car just got to wait, time and opportunity is the key. Car A - 30mph Car B - 60mph One Lap - X miles Car A will have to decide whether it wants to catch up before completing the first lap. Otherwise it's over. We have two missing variables. We can't solve it. The speed will be calculated based on car's A location. Car A has to accelerate at any point prior reaching X. For instance, at 1/2X miles Car A will have to travel 90mph to finish at the same as time as Car B. But at 3/4X it will have to go faster. So the closer it gets to reaching X, the faster it will have to drive. Let's say the track is 60 miles long. Car 1 has completed a lap of 60 miles after one hour, and car 2 has traveled 30 miles. For the second lap (which is one hour for Car 1 to finish), car 2 must travel 90 mph. This works with any distance; this one is the easiest to visualize. |

### Software Engineer at Raytheon was asked...

In front of you are three light switches. Only one does anything, and it turns on the light downstairs. From here you can't see the light, and it makes no sound. You must determine which switch operates the light, BUT you can only go check it once. How do you figure out which switch is for the light? 26 AnswersFlip any switch you want. Wait for about 5-10 minutes to let the bulb heat up. Flip that same switch off, and another one on. Go check the light. If it's off and hot, it was the first switch, if it's on it was the second and if it's cold and off, it was the last one. flip one switch look down stairs with out going down stairs and look if there is any light. Continue this until you see the light. Flip switches, keep checking, at the foor of the stairs, until you see light; that will be the switch! Show More Responses flip them all on. only one does anything so the other two really doesn't mean anything. Open the switch plate, using an electrical tester- test for the live wire. Only one will test positive. On a multiple unit switch the farthest left is often the first to be hooked up, Flip the switch on one end, wait a "long" time (e.g., 15 minutes); then flip the middle switch; them immediately go check the light for on/off status and temperature. If off: the switch you didn't change controls the light; If on and surrounding fixtures slightly warm, the middle switch controls the light; If on and surrounding fixtures fully warm of hot, the first switch controls the light. The first answer is right of course. Most of the other answers would make the interviewer realize you don't listen, don't understand the question, or don't care. Either way, not what you want in an interview. Don't jerk around. I frankly enjoy all the wry responses! Because this is just one of many ridiculously shallow and pointless interview questions that reveals much more about the intent and competence of the interviewer rather than the interviewee. Preparing for and sitting through an interview is tense enough - so it is totally deflating when a "gotcha" question like this is thrown at you. When I hear a question like this during an interview, I immediately know that the interviewer is 1) incredibly lazy and 2) clueless about how to actually gather worthwhile information in order to make an informed decision. Is that person someone you would want working with/supervising you??? Use solution one. Then use the light to get out - unless downstairs is the switch to fire the HR Department. I do like the use "an electrical tester" answer - unless you're interviewing for a safety job. Use solution one. Then use the light to get out - unless downstairs is the switch to fire the HR Department. I do like the use "an electrical tester" answer - unless you're interviewing for a safety job. Collins has the answer - Flip all 3 switches send your helper downstairs to let you know when the light turns on and off. Show More Responses LOL...good luck tripping and stumbling while looking for the warm light bulb in the dark! Turn all three switches on. The flip one switch off at a time and check to see if the light goes off after flipping that switch off. When the light goes off...that was the switch. oops! can only check it once. I dont get the job because I cant follow directions...If i'm in charge of the project, I can check it as many times as I like!!! Take the faceplate off and look inside to see which switch has wires hooked to it. That would be the winner. Tell the HR interviewer to go stick his/her finger in the light socket and scream when you flip the correct switch. It does not have sense because I am not an electrician. So I can flip any switch, after few minutes flip once again this switch and any other and go check to bulb. If it will be dark I can not check anything because I can not find the bulb I it will be light it does not mater which switch operate. I can go forward, :) I'll take the job. I can think of several solutions. I like these questions. And they are not pointless. How you answer such a question, or how you attempt to do it shows ho imaginative you are and whether you persist. A few possible solutions: 1. If it is dark outside, or the building does not have windows, operate the switches one at a time until you hear angry voices from downstairs - nobody likes to stay in the dark. 2. Otherwise, operate the switches one at a time and ask the people downstairs. 3. Do not operate any switch. Take your light-detecting sensor downstairs. The sensor transmits a wireless signal to the receiver in your pocket. Get back to the panel and start flipping the switches until you get the signal from the receiver. 4. Take your bow and three arrows with dull heads (you do not want to damage the switches). Go to a place from where you can see both downstairs and the panel. Start flipping the switches one by one by shooting arrows at them. 5. You need a big fly - one of those you can hear flying. Turn off all the lights in the building. The lights must be on only at the place where you stand and downstairs. Have someone release the fly downstairs - you can hear it buzz. Start flipping the switches one a time and wait. You know you got the right switch when you stop hearing the fly (or when it comes to you). Ask someone to go downstairs and yell up to you when it works. What are you people mentally challenged? You have no way of knowing which switch controls the light. The "correct" answers above assume the light is initially off. If the light started out as on and you performed this test you would get misleading results. I would either ask someone on the team who already knows which light switch it is or I would search the Internet for the solution to figuring it out on my own. I like the answer about requesting someone to go downstairs and check the light while you flip the switch, it shows 3 things about you: #1-You're not afraid to ask for help when needed. #2- It shows you can delegate. These responses coincide with TEAMWORK. Unless the interviewer has specifics, in which you ask. That could be the #3rd answer-BEING RESOURCEFUL by asking questions. It shows your interest in the job and you don't have to be an electrician to figure it out. Show More Responses subduejoy clearly has the answer, it's what I do for most of my problems. The "temperature" method is clever but that assumes the lights are incandescent and you're close enough to the bulbs that you can get there before they cool down to room temperature. An interviewer might look at that answer as clever but wrong because you make assumptions that weren't explicitly allowed (Microsoft would probably say this). My answer would either be. a) Ask for help (shows you not afraid to be a team player b) Do it the electrical engineering way and put a video camera in the room and wait 15 minutes before flipping each switch. It's really a stupid question though that says nothing about how good of an employee you'll be. 1. Flip one switch 2. wait 2 minutes 3. Flip switch off again 4. Flip another switch on 5. Immediately go downstairs and check if a light is on If the light is off, the switch you flipped in step 4 is not correct. 6. Touch the bulb If the bulb is cold, the switch you flipped in step 1 is incorrect. That means that the remaining switch is the correct choice. If the bulb is hot, the switch you flipped in step 1 is the correct choice. |

If you had to get rid of one of the United States which one would it be and why? 28 AnswersThe answer to this question basically described your decision making process and how you deal with problems... There is only one United States Well should I have said one of the states in the United States... Show More Responses this is an easy answer its sort of subtle. depends on your market segment. you want to get rid of the state with no customers :o) at that level its your quota that's important. That question is either worded wrong or needs some long consideration. The question was basically pick a state to get rid of and tell why.. No considerations given... The only one in existence. (Reread your question.) Well, we'd have to get rid of Maryland and Virginia both... only way to be rid of our real problem - Washington, DC. Because theres basically nothing of use there and it would be easy to annex to Canada I would follow this question with a question - is the goal of getting rid of a state to decrease down to 49 states? In that case I would combine two or more states together, allow them to keep separate, regional offices for politicians, and re-zone the new area to determine the proper number of senators, House representatives, etc. If the goal is to completely eliminate one state from the Union, I would let the states decide. There has to be a state who wants to leave the union. It's really not my decision to make. Because theres basically nothing of use there and it would be easy to annex to Canada "I would follow this question with a question - is the goal of getting rid of a state to decrease down to 49 states? In that case I would combine two or more states together, allow them to keep separate, regional offices for politicians, and re-zone the new area to determine the proper number of senators, House representatives, etc. If the goal is to completely eliminate one state from the Union, I would let the states decide. There has to be a state who wants to leave the union. It's really not my decision to make." You would just make the interview annoyed with that answer, as you're just dancing around. Its a simple question. Pick a state, and give your reason why. Don't over analyze the answer. It doesn't make you seem clever, it makes you appear full of yourself. So Hoog, how would YOU answer this question? Show More Responses Texas.. ever been there? Yes, we can do without. Texas? I think NOT. It has one of the most important shipping ports in the U.S., not to mention one of the busiest international airports in the U.S., and is also a "hub" between NYC and CA. Idaho? Have you every been to Idaho? Okay, delete Idaho only so long as the U.S. wants to get eliminate one of the better travel destinations in terms of outdoor activities (winter OR summer). It would be just as easy to eliminate Vermont or Maine, for that matter -- give one of THOSE states to Canada. How about doing the U.S. a favor and get rid of California and all of its financial problems, earthquakes, forest fires, and mudslides. It appears that the goal of this interview question is to reveal the existence of some deep-seated prejudices and anger issues in the interviewees. 1) Its a stupid question. 2) Probably would tell the interviewer hes wasting my time. Goodbye, going to talk to his/her manager. Kinda like "Are you a glass 1/2 full or 1/2 empty question" Its a stupid. Why give Canada a state? What makes people think that Canada wants a piece of the USA? If you're insistent on getting rid of a state, get rid of Alaska because that is clearly very far north and engulfed by Canada. As well, Canada is very good at dealing with the cold temperatures and with dealing with vast amounts of tundra/snow/ice. They excel at being able to travel across this snow and dealing with avalanches and cold-temperature rescue missions. I think Canada could efficiently deal with Alaska :0) Texas -- because we can make it and be better off without the other 49! (-: I would say New Jersey. Bye bye cows & industry. frame the question. Jack Bauer has to decide which state to eliminate the population of, or else 50 megaton nuclear weapons will go off in the middle of the 5 largest US Cities. Then the choice would be Wyoming, with the lowest population, with a "bonus" of Dick Cheney ;^) If his choice is which state to annex to a foreign country, then using the same logic either New Mexico to Mexico or Maine to Canada. Not Alaska or Hawaii you ask? No - both states are in very strategic geopolitical locations. disturbingly vague question. Is the goal of "elimination" to reduce the number of states to 49? Or is it to choose a state to break into more manageable parts and cause the number of states to increase? Or is it to pick a piece of real estate to obliterate? Or is it to cede a state to a neighboring country? If no guidance were available, I would assume the idea is to create a more manageable landscape. In that context, I would break California in two, making North California and South California. Why? Each of the two new states would be more homogeneous and a little easier to govern than the existing single state of California. new jersey. nuff said. Show More Responses Thats f-n ridiculous. I love how employers think interviewing is a big game when there are so many unemployed people out there trying to take it seriously. The question does require more framing. What criteria am I using to eliminate a state? If the interviewer really does just want you just give your personal opinion than the above poster is right, its just trying to ferret out your politics, religion or personal preferences and really is not appropriate. However, if what they looking for is for you to show that you know how to tackle a vague problem by asking the right questions and further refining the requirements, this could show how a potential candidate thinks. I personally would ask for more information on what they mean by 'eliminate' - what they mean by that has a huge impact on my decision process. As I said above, I would ask what the criteria would be - am I judging based on what is going to be best for this company, for the country, for myself? What is the time frame for this elimination? If eliminate means completely annihilate via atom bomb and I have to decide in the next 60 seconds, I am going to pick the least populated state. If the time frame is 6 months I can choose based on the value of the land, since I can move the people. If eliminate means kick out of the union and force them to become their own country, and I am doing what is best for me, I would pick the state I travel to least and have the fewest friends who live there. If my goal is to do what's best for the country, I would pick the state that has the least economic value. Just answering the question with something like 'Nebraska, because its boring' shows that you aren't considering the situation properly before making a decision. If the interviewer is thinking like Hoog and is annoyed by your trying to gather more information before making a decision, you don't want to work for that company anyway. I was thrown by this question and after a moment decided on New Jersey - haven't been there mostly because their reputation precedes them - though controvesy does keep things interesting. In retrospect I'd respond with Rhode Island. Not big enough for anyone to miss and not sure what they offer to the whole! Did you know that there is a United States of Mexico? or AKA United Mexico States..... There is one United States. If your asking to get rid of one of the states in the US I would have to say Washington DC. Just being honest. |

GIven 9 balls all of which weigh the same except for one, what is the minimum of weighings necessary to find the ball weighs more (or less). 28 AnswersAnswer = Maximum of three steps to find heavy ball. Put one tennis ball aside and put the other 8 on the scale - 4 on each side. If the scale is balanced you're done - the one you put aside is the heavy ball If not Remove the 4 balls on the light side of the scale. The heavy ball is one of the four still on the scale. Spit these four in two on each side of the scale. Remove the two on the light side of the scale. The heavy ball is one of the two remaining balls on the scale. Split the two remaining balls. Your done. Solution #2 - heavier ball found in two steps: Step 1: group 9 balls in sets of 3. Reserve 3 balls(a), put 3 on each side of scale(b) and (c). Observe that heavier ball is in one of three sets, (a), (b) or (c) - either the scale side that dropped or the reserved set, if the scale balanced. Step 2: Split the set with the heavier ball - reserve one and place one on each side of the scale. Observe that heavier ball is one of the 3 balls, - either the scale side that dropped or the reserved ball, if the scale balanced. Solved in two steps. While the solution above is correct, more or less, you first should clarify the question and spell out any assumptions. The assumption here is that you know or are aware beforehand that only one ball is of different weight. Sometimes your ability to clarify and state assumptions is more valuable than getting the right answer. Sometimes you can arrive at the right answer with the wrong logic which helps you solve this problem, but may mess you up in the future. You could do this with two weighings assuming its a two pan balance - (1) place three balls on each side - if they balance out then its the remaining three that has abnormal ball (2) out of that group, place one ball on each side - if balances it out, the abnormal ball is the remaining one. If the weighing in step (1) does not balance out, grab the group of three balls that is light or heavy and repeat step (2) described above. Show More Responses I began with the assumption you could do this with a minimum of three, but I now believe it's four. Perhaps I'm over thinking it though, so I'll explain my "solution". Step 1. Start with three balls on either side of the scale, with a third set waiting on the sidelines. If the scale is balanced, you can move onto the three waiting. 2. place one ball on either side, again with the last one waiting. Should the scales be balanced, it's the last one. 3. If they aren't, take the heavier side off, and place the waiting ball on, if they balance. It's the one you just removed. If they're off canter again, it's whichever side was inconsistent. The hitch with the fourth measurement comes due to the little trip up in the question "To find the ball that weighs more (or less)." If you don't know from the start if you're looking for a heavier or lighter ball, should the scales be off on the first measurement, you'll need to replace three of the balls with the reserves to determine which ones are the odd batch out. The comment about the assumptions is absolutely spot on. For example, I like the answer that says ONE step (weighing) but this assumes a balance scale is used not a device that weighs each ball. Based upon a weighing device that weighs each ball and remembering the question is the MINIMUM number of weighings then the answer is THREE - here is the logic. Each weighing weighs one ball. The minimum number of weighings to identify a difference is two, i.e the first two balls are different in weight. The third weighing will confirm which of the previous two is part of the set of eight balls with the other being the odd one out. Simple....8 of the balls are hollow.....1 is not. Maybe I'm slow but....if I put set A and set B on the scale while reserving set C, and if set A is heavier than set B, how do I know if set C is equal to set A or B without weighing it? Notice the question says "more (or less)". In other words, why wouldn't I have to weigh set C? (This is assuming each set is of 3 balls.) Suncoastgal has a point, and most of the answers above are simplifying this problem a bit. You are not told if the odd ball is heaver or lighter, which complicates things. The most efficient method is that described by 'questions like this...' as method 2. Split balls into 3 groups and weigh two. The worst outcome is if the groups do not weigh the same, so assume that happens. All you know now is that the odd ball is NOT in the reserved group of 3, so set those aside. You don't know which of the two weighed groups contains the odd ball, so now you have 6. Repeat the first step with groups of 2 balls. Again the worst outcome is that the scales don't balance, so you've eliminated 2 more balls and only know that the odd ball is one of 4. As near as I can tell, you still need 2 more steps now to guarantee finding the odd ball: Choose any two balls from the 4 and compare. If they are the same, the odd ball is in the reserved 2, if they differ the odd ball is one of the two you weighed. Now take one of the two balls that might be odd, and weigh against one of the balls you have been setting aside as 'normal'. By the way, although you now know which ball is odd, you may still not know if it's heavier or lighter. If the last weighing balances, you only know that the other ball is odd, and you would have to weigh it against one of the 'normal' balls to see how it is off. You can do this problem in only 2 weighings if you are told whether the odd ball is heavy or light before you begin. Suncoastgal has a point, and most of the answers above are simplifying this problem a bit. You are not told if the odd ball is heaver or lighter, which complicates things. The most efficient method is that described by 'questions like this...' as method 2. Split balls into 3 groups and weigh two. The worst outcome is if the groups do not weigh the same, so assume that happens. All you know now is that the odd ball is NOT in the reserved group of 3, so set those aside. You don't know which of the two weighed groups contains the odd ball, so now you have 6. Repeat the first step with groups of 2 balls. Again the worst outcome is that the scales don't balance, so you've eliminated 2 more balls and only know that the odd ball is one of 4. As near as I can tell, you still need 2 more steps now to guarantee finding the odd ball: Choose any two balls from the 4 and compare. If they are the same, the odd ball is in the reserved 2, if they differ the odd ball is one of the two you weighed. Now take one of the two balls that might be odd, and weigh against one of the balls you have been setting aside as 'normal'. By the way, although you now know which ball is odd, you may still not know if it's heavier or lighter. If the last weighing balances, you only know that the other ball is odd, and you would have to weigh it against one of the 'normal' balls to see how it is off. You can do this problem in only 2 weighings if you are told whether the odd ball is heavy or light before you begin. If the question to identify the odd ball (heavy or light) out of 9 balls is read literally, then the answer is 1 weighing (under the most luckiest of circumstances): weigh 2 sets of 4 balls against each other using a double-pan balance and if you're lucky it will weigh evenly, allowing identification of the not-weighed 9th ball as the odd ball. (The question doesn't say you need to identify whether it was heavy or light.) If the question is what is the least number of weighings it takes to identify the odd ball under the least lucky circumstances then the answer is 4, as best I can come up with. 1. Weigh 2 sets of 3 balls against each other, setting aside the 3rd set of 3 balls. The least lucky result ("LLR") is an imbalance. However, this does identify the 3rd unweighed set as all standard balls. 2. Here's where creative problem solving/out-of-box thinking comes into play. Take a red and black marker and mark one of the heavy balls red and one of the light balls black. Switch the marked balls. LLR --> still an imbalance, though imbalance must remain in the same direction since there is only 1 odd ball (yet to be identified). 3. Repeat step 2 (mark one of the unmarked heavy balls red and one of the unmarked light balls black, switch them and reweigh). LLR --> still an imbalance. 4. Take one of the 3 unweighed balls, previously set aside from the 1st weighing, and substitute it for the last remaining unmarked heavy ball. If this last weighing results in an imbalance then the odd ball is the last remaining light ball (and is light, obviously). If the weighing results in a balance, then the removed unmarked heavy ball was the (heavy) odd ball. These type of interview questions are so lame. They don't sniff out the lazy people, the coders who write crap no one can decipher, and can't or won't write maintainable code. Yes you want people who can problem solve and break down problems into manageable chunks, but how often do software projects fail? Answer = 70-90% and that's mostly due to poor management, not giving clients what they want, feature creep, poor quality, etc. So how is answering this question going to tell me that this new hire has integrity and can throw out his ego and write code for a real life product that people want to use? No wonder so much software is trash. (And yes I've been programming for 25 years and see the same errors happening over and over, it's pathetic and completely fixable.) I read the question as "determine if the odd ball weighs more or less", not "determine which ball is the odd one out". After re-reading the question, it seems like the word "IF" (i.e. "...to find [IF] the ball weighs more (or less)") or the word "THAT" (i.e. "...to find the ball [THAT] weighs more (or less)") is ommitted (purposefully?). I went about answering the my first interpretation and came up with 2 weighings as the MINIMUM required. I assumed we have a scale that can accurately measure the weight in grams (or whatever unit of measurement needed to accurately measure the ball). Step 1. Weigh 8 balls. Divide the total weight by eight. Step 2. Weigh the remaining ball. If you compare the result from each step you'll know if the ball is heavier or lighter than the others. Only 1 step required. Throw all of the balls in a sufficiently deep enough pool of water. The ball that sinks the fastest/slowest is the ball that doesn't weigh the same. If all of the balls float, then it is the ball that is lowest/highest in the water that doesn't weigh the same. Show More Responses The answer should 1 as it asked "the minimum". When you weight 4 balls on each side of the scale and find it equally weight then the 9th ball is definitely the odd ball. You can always got lucky on the first attempt! I understand the Question to be what the minimum of weightings needed is to find out if the different ball weighs more or less than the other 8. The answer is three. 1. You way 1 ball and get its weight 2. Weigh a second and get its weight 3. If they do not weigh the same way a third to see if the different ball is the heavier or lighter one. Or If they weigh the same weigh all the balls and divide by 9 if it is less than one of the balls you weighed the different ball is lighter. If it is more than one of the balls you weighed the different ball is heavier. I agree with Anonymous in that these questions don't tell much about character. However, I can't beleive nobody here is analytical enough to come up with the correct answer. First off, the question is not stated correctly. The scale should be a simple balance, and the objective is to find the "odd" ball AND determine if it is heavy or light. The answer is three. First separate into three groups of three, G1, G2, and G3. In the first two weighings you can determine which group has the "odd" ball AND if the odd ball is heavy or light. Weighing 1 - weigh G1 against G2: Two outcomes 1) G1 == G2 --> Odd ball is in G3, in Weighnig 2, use either G1 or G2 against G3 to determine if Oddball is H or L 2) G1 != G2 -> Odd ball is NOT in G3 but you now know if G1 is heavier or lighter than G2, in Weghing 2, use either G1 or G2 against G3, for instance use G2 and G3, if same, then G1 has oddball and you know if its H or L, if G2 != G3, then G2 has odd ball and you know if it is H or L Now that you know which G it is in And the disposition of the Oddball (Heavy or Light), weigh any two of the Group containing the oddball, and based on your knowledge of wether the oddball is H or L, you know which one it is and its disposition. Any offers?? The question is perfect to define how the person takes directions - how many assumptions the person does before start the job - how many questions the person asks (if asks) to make clarifications before start the job. Also, I see there another result - all answers come finally to two groups of getting result : 1) to get faster the first result but more steps for guaranteed result - from 1 to 4 steps or 1 to 4 weightings for combination 4+4+1 2) to get faster guaranteed result - from 2 to 3 steps for starting combination 3+3+3, I would say that BMF scheme contains one additional step (comparison of weight lighter/heavier - definition what of them is consider to be "odd" ), which in solution structure should be equal to the additional step, so it comes to from 2 to 4 steps but still in 2 to 3 weightings. After all, I would say that you may get from this question: How the person understand the task How many assumptions the person does before start the job How many questions the person asks before start the job How many solutions and ideas the persons generates. How the person make a choice to present one solution from multiple (say fastest first result vs fastest guaranteed result). Etc. The candidate should clarify if they truly mean the minimum to find the odd-weighted once, or everytime. I agree that it only takes one weighing (and some luck) to find it. Actually, the person could randomly guess (not weigh any) and get the right ball. So you need to understand the balance of risk vs. cost. By the way, simple logic problems do trip up people that you don't want working for you (depending on the job). So I like the question. It is interesting to speculate if the question wording is being cute or tricky by saying "more (or less)". Is it just being general and saying find the odd ball, or is it being tricky and saying find the odd ball AND tell me if it is lighter or heavier. I think it is being over thought here and just means find the odd. In that case the answers saying 2 weighings is the best you can guarantee. None of this lucky crap. BMF had it if you had to determine if it was in fact heavier or lighter instead of being told. So if the question had the added clause that if you really tried it and didn't get it in the number of tries you answered (or fewer), then you would be killed, would you still say "just one if you get lucky"? Keep it simple. If it's 3-state balance you need log2(9) / log2(3) attempts since you can encode 9 states using 2 3-bit states. I don't understand why everyone is confused. The question clearly asks to not only find the odd ball out but to also determine if the odd ball is lighter or heavier. The only assumption is that it is a standard two pan balance. My solution is 4 weighings: 1. Divide 9 balls in three groups of 3. Let's name them A,B,C 2. Weigh any two groups of 3. Let's say A and C. (1st weigh) 3. If A and C are equal then the B group is the culprit. 4. Now lets label the B group as B1, B2, and B3 5. Take either two balls from either A or C and measure against two from B let's say B2 and B3. (2nd weighing). If both are equal then B1 is the odd ball. Now weigh B1+ one good ball against the same two good balls used in the previous weighing and compare to see if the ball is heavier or lighter. (3 weighings) If they are not equal then determine if the B group is currently heavier or lighter. Go to step 6. 6. Switch either B2 or B3 with B1. Let's say we replaced B2 with B1. If the weighing is now equal then B2 is the odd ball out. If the weighing is still unequal then B3 must be the ball. Thus we have used a total of only 3 weighings. Since we made note of the weighing in step 5 we know if the odd ball is heavier or lighter. 7. Now if the 1st weighing (between group A and C) was unequal then we need to determine which is the bad group. Thus we need to weigh one of them against group B (which we know is correct) and then proceed with the steps 2-6. So in this case it is one extra weighing which brings a worst case total of 4 weighings. I hope everything made sense. I don't think its possible to get it in 3 AND also find whether the odd ball is lighter or heavier. One thing is for sure: I would have never solved it during the interview since this took way more than 5 min to figure out. I believe the answer is 2. Step 1: Before weighing anything, you separate the balls into groups of three. Step 2: Put one group of three on one side of the scale, and the other group of three on the other side of the scale, leaving still one other group of three somewhere on the side. ---visualization ooo /\ ooo <--------1st weighing ooo <------side group Step 3: If the scale is balanced that means that the heavier ball is in the side group. At this point, you would weigh any two of the remaining three balls. Again, if the scale is balanced, then you know that the only ball left is the heaviest one. If the scale tips to any particular side, on the other hand, then you know that the heavier ball is on that side. Up to this point the number of weighings is 2. Step 4: if on your first weighing with three balls on each side, the scale tips, then your next weighing will be of any two of the three balls which were on the tipping side of the scale. Again.. if the scale is balanced, then the remaining ball must be the heaviest. And if the scale tips to a side, then you know that side has the heaviest ball. Up to this point the number of weighings is also 2. Therefore the minimum number of weighings is 2. You obviously can get away with 1 weighing, but only if you are lucky; weighing 4 against 4 and hoping that the other ball (not weighed) is the heavier one. Otherwise, starting out weighing 4 against 4 will lead to 3 weighings, therefore that solution is not the optimal one. Even starting out with a 2 against 2 scheme, you can have up to 3 weighings until you are absolutely sure of which ball is the heaviest. So, optimally, you will be weighing 3 balls against 3, and the least amount of times you would have to weigh the balls to know for sure which one is heaviest is 2. In lieu of the fact that we don't know whether the ball is heavier or lighter then the rest, you would have to do 3 weighings. 1: ooo/\ooo ooo Do the first weighing as pictured above to isolate the set of balls that you know for a fact weigh the same. Then, in the second weighing, use that set to isolate the set that contains the odd ball. The second weighing should also tell you whether the odd ball is heavier or lighter because of how the scale reacts when you replace the control set with the unknown set. If the scale stays tipped down to the side opposite the control set, then it's heavier. If it stays tipped up, then it's lighter. If the scale was balanced before the second weighing, then you know that the remaining set is the set that has the odd ball, and replacing it with a set that you know all weigh the same should still tell you whether the ball is heavier or lighter by watching how the scale behaves. Then you can proceed to the 3rd weighing to isolate the heavier/lighter ball. So my mistake everyone -- the correct answer is 3 weighings when you don't know if the ball is heavier or lighter. Show More Responses I had this interview question this morning. Those of you who say it has no bearing on determining character are wrong. An arrogant person will present their answer, right or wrong, and say that they are done and it is perfect. It takes humility to consider that your first answer may be wrong, and the interviewer will want to see your process for checking that your answer is correct. Remember, it is the path you take to get to the answer that is more important than getting the answer right. Given 3 step, divide the balls into 3 groups A, B, C, Not knowing which has the heavier or the lighter ball, #1 Step: scale A vs B, If it balanced then we already know that C has the different weight.(but we still dont know if the ball is heavier or lighter. If it did not balance we will know that the OTHER ball is maybe in group A or B. (Note: e.g. A raises and B dropped) #2 Step: scale A vs C, If it balanced then we will know that the OTHER ball is in group B. If it did not balance e.g A raises and C dropped. we now conclude that C and B has the same weight and the OTHER ball is lighter #3 Step: Using the group A ball. scale the 2 balls, if they balance they we will know that the 3rd ball is the one that is different. if it did not balanced then the side where the ball raises is the OTHER ball because from step 2 we already notice that the ball is Lighter. Problem solved! Divide the 9 balls into groups of 3 3 - 3 -3 take first 2 groups on the scale. If they balance out: Take the last group of 3 Divide the last group into 1 - 2 Take the 2 (above) one each of the scale. If they balance out, then the '1' is the heavier one else u get the heavier one. Number of scale measurements required = 2 Balance 4 vs 4, - if balance the excess 1 is the lightest or the heaviest. Don't mind which is the heaviest nor the lightest since the question is OR - you can just have one answer. the minimum would be two. First ball and second ball either one would weight more... since they are asking the "minimum'... if they asked for the maximum then it will take 8 times. |

### Software Engineer at Facebook was asked...

You have two lightbulbs and a 100-storey building. You want to find the floor at which the bulbs will break when dropped. Find the floor using the least number of drops. 37 AnswersStart moving up in increments of 10 floors and dropping the bulb until it breaks (ie: drop from floor 10, if it doesn't break, drop from floor 20, etc.). Once the bulb breaks, move down to the floor above the last floor it broke on and start moving up floors in increments of one until the second bulb breaks. This results in a worst case scenario of 19 drops. Surely a binary search method would be more efficient i.e. starting at 50 and either going up or down 25 floors based on if it breaks or not. If you do a binary search, what happens if it breaks at floors 50 and 25? Show More Responses Do you know what a binary search is? You drop it from floor 12 next. If it breaks, you know it breaks between floors 12 and 1, inclusive. If it doesn't, you know it breaks between floors 13 and 25, inclusive. The main principle of binary search is that with each step you reduce your search space in half. Now your search space consists of only 12 floors. Wow, I want to get asked such a question in an interview! >>you drop it from floor 12 next... if you broke it on 50 and 25... you are out of luck and out of bulbs... 19 drops is not the best worst case scenario... imagine trying floor 16, if it breaks, you try 1 - 15 and thats 16 tries. if it doesn't break, then try floor 31 and if it breaks, then try 17 - 30 (so 16 tries, including the try on floor 16). And on and on (45, 58, 70, 81, 91, 100). If you reach 91, you'll have tried 7 floors so far and if it doesn't break, then there's 9 more tries to get to 100 (thus 16 in the worst case) Even a drop from the ceiling of 1st floor, a simple light bulb will break. thats what i think It's a light bulb. It will break when dropped from the 2nd floor. Drop it there then go to the first floor, hold it over your head and drop it. first do a binary search (agressive first step - fast) with 1 bulb. when first breaks, you know X(last but one fall - success) and Y(last fall - failure). now do a linear search starting from X(conservative but accurate second step - slow). complexity = in between logN and N. Use Binary search starting with the middle 50 The complexity of binary search is logN . So it will be log(100) < 7. Based on my experience, I think it will be floor 1 itself . Drop from 1st floor. If it didn't break, drop the same bulb from 2nd. If it still didn't break, drop the same bulb from 3rd... repeat as necessary. Only one light bulb required :) Yes, but doing each floor, that will give you the most drops -- question relates to optimizing for "least" number of drops -- I didn't think about being able to re-use the bulbs...that obviously is helpful. Maybe a fibonaci sequence once you determine a "break" floor and a "non-break" floor. I'd probably fail completely at coding it...knowledge of optimization and prediction theory would certainly be useful. Let f(m,k) be number of tries for m lamps and k floors. Obviously f(1,k)=k. let f(2,k) be s. k<=(s-1)+(s-2)...(1) =s(s-1)/2. Therefore f(2,100)=15. Show More Responses Actually, 16 is not the optimal, nor is 15; you can do it in 14. Here is one solution (there are at least 5 other equivalents): * Drop first bulb at 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks. * Go to the highest floor where the first bulb didn't break. * Repeatedly go up one floor and drop the second bulb. When it breaks, you have your answer. Why is 14 optimal? Since you are decrementing each time, you want (n) such that sum(1..n) barely reaches 100. The answer is n=14. Generally, if the number of floors is (f), the lowest number of drops is ceil((sqrt(8*f+1)-1)/2). This is the best worst-case scenario. An interesting related question is what gives the lowest expected number of drops. And no, I could not have gotten this in an interview. In theory, use one bulb to determine an interval, and use the second bulb for a linear search within the interval. The solution that decreases the interval by one for each trial is quite clever. In practice, however, take the nature of the problem into account: Start on the first floor and move up by one floor. That's the answer I would be looking for. Start with bulb 1 and drop it from floor 2. Doesnt break? then floor 4 Doesnt break? keep dropping the same bulb moving even number of floors all the way upto floor 100. If on some even floor the bulb breaks drop the second bulb from the odd floor below the even floor, to detect if its the even or the odd floor that breaks the bulb Best case detection: 2 tries (first bulb breaks on 2nd floor, second bulb breaks on 1st floor) Worst case: 51 tries (the fist bulb breaks at 100 and second bulb breaks or does not break at 99th floor.. ) Go to the 100th floor and drop the first bulb. It WILL break. Done, 1 drop. It doesnt say whats the lowest floor it will break at, just at what floor will it break with least drops. Thus floor 100. Alright guys...you have two light bulbs. ...the second one has to be used for linear search, let the worst case number of items to be searched be x, then your interval will also have to be x, which will result a worst case of 100/x drops for the first light bulb. So now you are just trying to minimize n=100/x+x, find n'=0 when x=19...the candidate's answer is correct. I meant...x=10. and n=19. 0 drops, 1 bulb......stop thinking like computer nerds. Use physics or an engineering mindset. They didn't prohibit the use of any tools. Grab a scale, figure out force req'd to fracture bulb. Calculate acceleration due to gravity adjusting for air resistance/barometric pressure at location (trivial for anyone who took a 1yr physics course). Figure out how many meters up you need to be based on the req'd acceleration. Done.... @Rich: I am sure they were hoping for you to give them a computing answer since they don't do physics, and rather do computer science. mer's answer is correct: 14. Let F(s, n) be the optimal worst-case number drops for s stories and n bulbs. Suppose we drop at floor f, constituting one drop. If it breaks, we must make up to F(f-1, n-1) drops. If it doesn't break, we must make up to F(s-f, n) drops. Thus, for a given floor f, we have up to 1 + max { F(f-1, n-1), F(s-f, n) } drops. Optimizing over f: F(s, n) = 1 + min{ max { F(f-1, n-1), F(s-f, n) } for f in 1..s} Using the appropriate base cases, we have F(100, 2) = 14, as mer has given. Another way to think about it is in terms of decision trees. We want to construct a binary decision tree with leaf nodes for floors 1..100, and at most one "left" turn per path from root to leaf. To minimize the height of the tree, we want to reduce the variance in the length of each root-to-leaf path. This suggest we try dropping the first bulb at floors of the form: a, a-1, a-2, .. a-b, where the sum a + (a-1) + .. + (a-b) is equal to or barely over 100, so that determining almost any floor (possibly excluding the top few) takes a drops. Using this approach, we get the sequence of drops that mer has suggested. Well done @mer I have seen this question posed many ways, and that is the best answer I have ever seen. Sure hope I get asked this one now Show More Responses 14 In my experience light bulbs break when dropped from any height above 3 feet nice explanation from http://www.programmerinterview.com/index.php/puzzles/2-eggs-100-floors-puzzle/ Depends on how accurate u want to be. If i want exact answer, drop one from fifty, if it breaks start from first floor woth the remaining bulb. If it does not break, then start from fifty first florr. u will iterate fifty times as worst case. If u want a approximate answer, u can do binary way with give or take twenty five floors. Step over based on accuracy needed. You are all ignoring valuable information in this question. We are talking lightbulb, not bowling ball, and building, not step ladder. The bulb will almost certainly break by being dropped from the second floor (assuming US numbering conventions). The chance of it surviving a 3rd floor drop are miniscule, but not zero. The chance of a 4th floor drop, even less. Therefore, drop it from the 3rd floor first. If it breaks, go to the second floor and try. If that breaks you know the answer is 2. If it by some miracle doesn't break from the 3rd floor drop, the answer is 4, but take the elevator up one floor and drop it just to see. Rinse and repeat to 5, but since it will have already broken, go out and grab a beer, and tell your friends how much fun you just had. n*(n+1)/2 = 100. n approx = 14. In worst case u can figure it out in 14 drops. 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks. I believe the number sequence should be: 14, 27, 39, 50, 60, 69, ** 77, 84, 90, 95, 99 **. The 9 floor gap between floor 69 and 78 would result in 8+8 = 16 drops worst case. Easy. Answer is zero. You don't need a test to find out that a lightbulb is going to break, even when you drop it from the first floor, because it's made of glass. BigO(100/X + X-1), Where X is the number of floors. 100/X calculates the dropping times to break the first one and X-1 is the additional maximum overhead to break the second one starting from the previous dropping floor to the floor the previous bulb was broken. If you solve the derivative of the above equation equal to zero, the optimal solution becomes 9.9 ~= 10 . Worst case = 100/10 + 10 -1 = 19 If its a glass bulb it will break from a 2ft height...i wont even care climbing any floors to check. Show More Responses Once you break the first light bulb, you are FORCED to start at the highest safe floor + 1 (i.e. highest floor that you safely dropped bulb #1 from) and drop bulb #2 one floor at a time, moving upward. Therefore, the algorithm for the first light bulb is critical (cuz once it breaks you are counting by 1's upward). Binary search starts at the 50th floor ==> max # drops = 50 Choosing fixed increments rather than binary search, e.g. start at 10, increment by 10, yields better results ==> 25 The ideal solution is 14 drops ==> Start at 14, increment by 14 each step until it breaks (leaving for the reader why 14 is optimal). It doesn't matter what floor you are on to make a bulb break. Doesn't it matter how high off the floor the bulb is dropped. If I am on the 5th floor and the bulb is sitting on the floor of the 5th floor, how high off of that 5th floor do I need to drop it before it breaks. This is a misleading question. The question doesn't say that you will drop the bulb out the window. Drop both from eye level. Both will break, and I answered the question without even climbing one stair. Efficiency isn't always about math..Common sense Answer: 14 drops Mathematically: 14 is the first number n, where the sum of numbers from 1 to n is greater than 100 Trial and error: The worst case happens when the bulbs break at floor 13. If you start from the 14th floor and the bulb breaks, then you start at the bottom floor and work your way up. If it doesn’t break and you try it again from the 28th floor and it breaks, then you go back down to the 15th and work your way up 1 floor at a time. |

### Associate at Novantas was asked...

You have 15 horses that run various speeds. You own a race track on which you can race the horses, and this track holds a maximum of 5 horses per race. If you have no stopwatch or other means of telling exactly how fast the horses are, how many races would you need to run between the horses to be ABSOLUTELY SURE which horses are first, second, and third fastest? 23 AnswersOnce this question is answered successfully, a follow-up question is posed: if you now had 16 horses, how many races will you need to run to achieve the same 1st, 2nd, 3rd ranking? Is both answers 4? 6 runs for 15 horses and 7 runs for 16. You run 5 horses first, then in every next run you keep the top 3 winners from the previous run. Of course, since these are horses, you should always give them time to rest between the runs. You still cannot be ABSOLUTELY SURE though - a fast horse may have had a bad day. Show More Responses I contend 5. Run all horses in the first 3 races (call these heats). This will limit your pool to nine candidates for the top three spots (as you can remove the slowest two from each heat). Run the second place heat finishers and two of the original first place heat finishers (just for kicks) in the fourth race. With the information from the second place heat finishers, we can determine the final 5 horses as follows: * Slowest 2nd place heat finisher from fourth race and his 3rd place heat finisher counterpart are out (as we know that that his 1st placer, the other 2nd placers and their 1st placers - 5 horses - are faster). 2 down, 2 to go. * Middle 2nd place heat finisher from fourth race and his 3rd place heat finisher are out (as we know that his 1st placer, and the fastest 2nd placer and his 1st placer - 3 horses - are faster). 2 down. So, final race is between all first place heat finishers, fastest 2nd heat horse and his 3rd place counterpart. The order this race is won determines the fastest three horses. A bit wordy but hopefully, you'll get the idea. How about you can't be absolutely sure about the fastest horses. Otherwise you'd be rich from bettin' the ponies and not interviewing for this job. Very good A Lars. I came up with minimum of 5 races, 6 max. Walked thru your example, and came up with 4 minimum, 5 max. Well done. I don't think Lars is necessarily correct in all cases because you may choose the 5 fastest horses in the first race of the first heat, so horses 4 and 5, which are eliminated are faster than horses 1 and 2 in the second race of the first heat. hjc, That's why in the last race you have the 3rd place of the fastest 2nd placer heat, to see if he's faster than the other 1st placers. I've also got 5 races but in different way than Lars. 1st race 5 horses. 2nd, 3rd and 4th race is the first two places of the previous race and 3 new horses. so after 4 races we can determine the fastests 2 horses of 14 horses. the fifth race is between the 3rd placers of the previous races and the last horse. btw, in Lars method you can even find the 3 fastest horses out of 16 also in 5 races. in the last race you don't need the 1 placer of the 2nd fastest because you obviously know he's faster than his 2nd and 3rd placers. so that gives you an opening for the 16th horse. OFFICIAL ANSWER: 5 races Assume that you have numbered the horses 1,2,...,15. Since each race can accommodate at most 5 horses, the first three races will be 1,2,3,4,5 then 6,7,8,9,10 and then 11,12,13,14,15. Now assume that the order the horses finish in those races is numerical (for simplicity) - i.e. in the first race 1 wins, 2 comes in second, ..., 5 comes in last. We now know that horses 1, 6, and 11 are the winners of their respective heats. So in the fourth race, we race just these three horses against one another to see who is the outright fastest. Assume (according to our previous simplification) that 1 wins, 6 comes in second, and 11 comes in third. We now are CERTAIN that 1 is the fastest horse. However, we don't yet know which horses are 2nd and 3rd fastest. But what we do know is that the only possible horses that can be the second fastest are horse 2 (immediate runner-up to horse 1 in the first race) and horse 6 (immediate runner-up to horse 1 in the fourth race.) And the only possible horses that can be third fastest then are 2 or 6 (depending which is second fastest), the immediate runners-up to these horses (horses 3 and 7), and horse 11, winner of the third race. Consequently, in the 5th and final race, we pit horses 2, 6, 3, 7, and 11 against one another. The horses finishing first and second in this race are the second and third fastest horses overall. NOTE ABOUT FOLLOW-UP QUESTION: When 16 horses are involved, we still need only 5 races to determine outright the first, second, and third fastest horses. We simply add horse #16 to the fourth race - recall that only the three heat winners raced in this race, and we therefore have room for horse 16. The rest of the race methodologies are the same. For instance, if 16 comes in last in that race, then trivially it is not 1st, 2nd, or 3rd fastest. If it comes in any place but last, then we exclude the last place horse from the final race (which would be horse 1, 6, or 11) and instead include horse 16. Hope this helps, and I am glad to see so many people taking an interest in this problem. Soon I will post another (albeit easier) interview question from the same round of interviews at Novantas. You aren't taking into consideration that one heat could be entirely faster than the next. Yes 1 might be the fastest in its heat but maybe all 11 - 15 are faster than 1, so I don't see how you can be certain that 1 is the fastest horse after the fourth race. whats wrong with fastest horse from each race in a fourth race with 16th horse? View the answer on my blog at http://bit.ly/b8riKs Show More Responses I also say 5, but have yet another method. ;) I start like Lars, i.e., run all horses in the first 3 races and get down to nine horses. Then I'll run the three horses that finished first and two of the horses that came in second. That way I'll know already what the fastest horse is. I'll take out the last two horses from that race because I already know that there are 3 horses that are faster. So all I need to do in the final race is take the 3 winners from the fourth race and race them against the two horses I haven't included in the fourth race. 8 races: You need 3 races with each 5 horses - you take the 3 fastest of each race You have 9 horses left. You need 2 races with 4 and 5 horses resp. You take the 3 fastes of each race You have 6 horses left. You need 2 races with each 3 horses. You take the 2 fastest of each race. You have 4 horses left. You need one final race with 4 horses. You will identify the 3 fastest. However, admittedly, they will be exhausted at the end ; ) So practically it is maybe not the best approach - but in theory it should be ok. I wanted to type this answer as if I were thinking out loud in an interview (and before I looked at the posted answers). Anyone can work it out and give the answer here, but maybe it took them 3 hours. Here goes: 3 races gets you the 3 fastest, but clearly you don’t know their relative rank and if a 2 or 3 in one group is faster than a 1 from another. So race 4 gets you fastest 3 of that 5 group and race 5 gets you fastest 3 of that race group, then you would have 6, and race 6 gets you 3 which you add to the 1 and have a final race 7. (at this point I realize that is too simple for an interview question/answer and say) That was not so hard to figure out, so there is probably a more efficient answer, so let me rethink it. So after first 3 races, set aside the #1 horse of each. Then you have 6 second and third place horses. So if the original 3 groups were A, B, C and finishing places were A1, A2, A3, etc, then you know some of the orders and can use that to eliminate some horses without racing them. So in a 4th race you race A1, B1 and C1, and they finish in that order (for example), then you Know B1 and A1 are faster than C2 and C3 so you can toss C2, C3 out. You also know A1 is absolutely the fastest so you set him aside on the gold medal stand. Now you have B1,2,3, an C1,A2,A3 still 6 horses, which would cause 2 more races. (so at this point I ask to go to the white board to write some things down, as I am starting to do on my paper here at home). So I write down a matrix with A1,2,3, B1,2,3, and C1. On the white board, I start writing some possible outcomes and talking out loud, but it is taking longer than I would like (the key in the interview is to stay calm). I came up with one method that could do it in 5 races by racing A1, B1, C1 and two random #2 spots (in race four), then I showed that I could eliminate enough to bring in A3 and B3 in race 5 and then determine a final order. But then I saw a better solution by looking at it again. I realized after race 4 that I can eliminate B3, because if B2 is faster then C1, then B2 will be at best in third place, so there is no more spots and we never have to race B3. So now we have only 5 possible horse that can be second or third: A2,A3,B1,B2, C1. We run race 5 and the first and second place get second and third overall. The one point is, the first easy answer is usually wrong when trying to find the most efficient solution to a logic question. The other point is, keep talking it thru, use the white board or paper in the interview to “show your work” as you think out loud. Also, if you’re ever get one of these questions in an interview and you know the answer, either tell them, or fake it by thinking down some wrong paths. If you whip out the answer too fast they be suspect you knew and lied. That decision must be made by your moral compass ;-) FYI, after looking, this answer is same as InterviewCandidate. I think Lars went down the same more complicated path as I did when just "thinking out loud", but it was not as simple. Winning Horse - why would you post an answer that is so much worse then correct answers already on the board? Odd. Also, the assumption is the horses never get tired and run at the exact same speed every time. You just can time them or "judge" which is faster without a head to head race. I did not know the followup before reading answers, but I agree with Interview Candidate - add it as 4th horse the the 4th race to see if he knocks of one of the top 3 (and therefore the #2 and #3 behind them.) In my example, if #16 knocks off B1 (therefore B2B3C1C2C3), the you just test him against A2, A3 in race 5. If it knocks off C1, then it takes the place of C1. If it knocks off A1, then it gets "gold" and C1,C2,C3 are eliminated and the A's and B's must race. B3 is logically eliminated like I said in my example. Agree Five Races, but don't agree with the methodology. Here's how I did it Number the Horses 1-15 Run three races. Race One Includes Horses 1-5. Race Two Includes Horses 6-10. Race Three Includes Horses 11-15. For Simplicity Race One Result Order - Horse 1,2,3,4,5 Race Two Result Order - Horse 6,7,8,9,10 Race Three Result Order - Horse 11,12,13,14,15 What do we know at this point? Horses 1,6, and 11 COULD be the three fastest horses. However, horses 2,3,7,8, 12, or 13 could also still be in the top three if you take into consideration, for example, every horse in Race One was faster than every horse in Race Two. So how do we solve for this? Run a Fourth Race with Horses 1,6, and 11. Let's say, again for simplicity, the outcome of this race, in order is Horse 1,6, and 11. Now what do we know? Horses 7,8,12, or 13 CANNOT be in the top three anymore. We already know Horse 1 is the fastest, but candidates for the top three remain Horses 1,2,3,6, and 11 because it still hasn't been proven Horses 2 or 3 are slower than horses 6 or 11. Race 5 (Final Race) - Horses 1,2,3,6,11 Top three finishers are you top three horses. Comments Welcome Best case scenario = 4 races: 1st: 1 2 3 4 5 eliminates 2 horses 2nd: 3 6 7 8 9 eliminates 4 horses 3rd: 3 10 11 12 13 eliminates 4 horses 4th: 1 2 3 14 15 Race 1, 2 & 3 eliminate 10 horses from the pool of top 3. Race 4 determines final rank. Worst case scenario = 5 races. 1st: 1 2 3 4 5 eliminates 2 horses 2nd: 6 7 3 8 9 eliminates 3 horses 3rd: 10 11 2 7 12 eliminates 3 horses 4th: 1 6 13 14 10 eliminate 2 horses 5th: 1 6 13 15 16 Final rank 16th horse is bonus 4 races... you don't need to know the fastest until the last race. You merely need to eliminate those that are not in the top 3 until the final round. Round 1: 3 races of 5 each. Take the top 3 in each (9 remain) Round 2: 2 races of 4 and 5. Take the top 3 in each (6 remain) Round 3: 2 races of 5 and 1. Take the top 3 in each (4 remain) Round 4: 1 race of 4. Line em up and see who comes in 1, 2, 3. I see some interesting answers here - up to and including folks mistaking a 'round' for a 'race', thereby racking up a total of 8 races!. This may help to demystify the problem. You have to run 3 races to start to get the 1-2-3 ratings for the three sets of 5 horses, let’s call them A1 to A3, B1 to B3 and C1 to C3 respectively. If you race A1, A2, B1, B2 and C1 you will identify the fastest horse, and the results will dictate the next step, as follows: IF ... The results are: A1, B1 – regardless of order C1 A2, B2 – regardless of order THEN ... You are done. For example, let’s say the result is A1, B1, C1, A2 and B2. You will have established that A1 is fastest, given that it beat B1 and C1, B1 is next fastest, given that it is faster than A2 (i.e. all other A horses) and C1, and C1 is third fastest, given that it is faster than A2 and B2, and you already know that it is the fastest C horse. So anyone who thought that you needed a minimum of 5 races was wrong. IF ... The results are: The #1 of A1 and B1 C1 The #2 of A1 and B1 A2, B2 – regardless of order THEN ... You need to race the slower of A1 and B1 against C2 to see which horse is third fastest. IF ... The results are: C1 The #1 of A1, A2, B1, B2 The #2 of A1, A2, B1, B2 The #3 of A1, A2, B1, B2 The #4 of A1, A2, B1, B2 THEN ... You need to race the #1 and #2 of A1, A2, B1 and B2 against C2, C3 to see which horse is second fastest and which horse is third fastest. There is not a scenario where you need a sixth race. If you add another horse to the mix – let’s call it X – then you will need 5 races, as follows: It is still most efficient to run 3 races to start to get the 1-2-3 ratings for the three sets of 5 horses - e.g. A1 to A3, B1 to B3 and C1 to C3 respectively – and it is still most efficient to race A1, A2, B1, B2 and C1 to get your next level of information. But then things will change a bit: IF ... The results are: A1, B1 – regardless of order C1 A2, B2 – regardless of order THEN ... You will need 1 more race with A1, B1, C1 and X, to see if things change.. IF ... The results are: The #1 of A1 and B1 C1 The #2 of A1 and B1 A2, B2 – regardless of order THEN ... You need to race A1, B1, C1, C2 and X to get your true 1, 2, 3 rating. IF ... The results are: C1 The #1 of A1, A2, B1, B2 The #2 of A1, A2, B1, B2 The #3 of A1, A2, B1, B2 The #4 of A1, A2, B1, B2 THEN ... You need to race the #1 and #2 of A1, A2, B1 and B2 against C2, C3 and X to get your true 1, 2, 3 rating. ravi@ravi.com One race. Line horses 1-5 at the starting line, line 6-10 1/3 of the way down the track, and 11-15 2/3rds of the way down. first, second and third place winners are those who break the tape at each starting line. For sixteen, just line up four horses in 1/4 increments. same one race. The answer to 15 horses or 16 horses is: 4 races total. Just figure it out. |

### Sales Specialist at Lowe's was asked...

Have you ever told a subordinat to do something and found out latter it was wrong? How did you correct it? 23 AnswersHelped them correct it and appoligized for mistake I corrected the situation myself with the subodinate helping me. Take accountablity for the bad information, move on by correcting the mistake Show More Responses Help them correct it to ensure that they know what to do the next time. correct my mistake and apolgize i will not say directly that it was wrong but i will ask him/her whether we can do this in different way n ask his opinion, by taking his reply in consideration i will correct the wrong thing with his help Went to the person told them that after thinking about the situation that I think we should handle it a different way. Informed them of the new (correct) way of doing it and ask them what they think. Nothing beats honesty. Part of the foundation of any leadership philosophy should be: "Always speak the truth. People will forgive an honest mistake, they won’t forgive you if you lie." You must be honest. This is your integrity on the line. There is nothing more frustrating or de-motivating than a manager who cannot admit mistakes. When you have admitted the error be sure to offer assistance in repair or damage control. Confess to the associate that you gave him/her incorrect information and that the work needs to be done over again. Apologize for the error and that this error just validates the fact that no one is perfect, we all make mistakes. Hopefully the associate will not be too upset, but the job still needs to be done over. Offer some assistance...you still need to manage your building. Correct way: Correct problem first, admit your mistake, move on. This takes a big person. Wrong way (also known as the American Corporate way): Ignore wrongdoing, blame subordinate. Put complaint in subordinate's personnel file. Have subordinate cut in next round of layoffs. This is how weasels work. My last employer didn't provide a job description and I basically twiddled my thumbs until I created a job for myself to make the time pass; a corporate uppity complained about my project and my boss defended my work knowing full well I created the position description. So I had no explanation as to how my job should be done. My boss ended up providing instructions on how to fulfill my "made up job" from that point forward. That's when I started looking for other employment. I've made that mistake. I apologized for the mistake and fixed it. Simple as that. Show More Responses You absolutely admit the error and take whatever corrective action is needed. As other posters said, honesty is the best policy. Don't fake it and don't make stuff up. If the situation REQUIRES a guess, then guess and still admit if you made the wrong decision. But don't try to cover your tracks. You lose credibility and frankly, you don't deserve it at that point. "Every day... I have worked with some pretty dense people and it takes the patience of a devout buddhist monk to see the way some of my previous employees bastar-dized the work that i asked them to do and react with nothing more than a polite reminder of the correct way to not jack sh it up all the time. " Actually,I find the Question a little confusing. (not to mention the spelling). Did the subordanite do the job wrong or were they giving the wrong info? You should probably do a spell check next time before posting something...it does make the question harder to read... Will take accountability of the same & think of next move Take accountablity for the bad information, move on by correcting the mistake Admit my mistake and rectify the problem I would go to that employee as soon as realized the mistake and let them know i was wrong and make sure they are clear on the correction. I would thank them for their time and move on with my day. Just admit that you made a mistake. Review the task at hand with the employee and solicit his/her opinion on how to do it more efficiently and mistake free. And always thank them. B |

### Linux Kernel Engineering at Google was asked...

You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer. 29 AnswersI don't know, but Google it, you'll find the answer. Once you know it, it's obvious. 12 Probably 8. First answer: at least 5 (you have to look at every horse). Second answer: 11. You can race five horses, replace 4th and 5th place horse by two horses from pool of horses that haven't raced, and continue doing this until all horses have raced. Since there are 25 horses, you need 1 race for the first five horses and 10 to go through the remaining 20. Third answer: 8. Round 1 (5 heats) : Race horses in heats of five. Eliminate all 4th and 5th place horses. (15 horses left) Round 2 (1 heat): Race winning horses from every heat. Eliminate 2nd and third place horses that lost to horses in round 2 that came third or worse. (7 horses left). Round 3 (1 heat): Pick any five horses. Race them. Eliminate bottom two and replace with remaining two horses. (5 horses left) Round 4 (1 heat): Eliminate bottom two. Note: after round 2 it may be possible to use some interesting decision tree mechanism to determine the three fastest horses using fewer horses per heat but you still need two heats to do that. This problem assumes horses don't get tired, no ties are possible and a horse's speed is deterministic race after race after race. Good assumptions for brain teasers, but not for real life. Show More Responses Actually, should be 7. Forgot that after round 2 you can eliminate one more horse leaving you with 6 horses, one of which (the winner of the second round), is the fastest horse of them all. One more race with the five horses not No.1 and you pick the top two. 6. First round consists of 5 races of 5 horses. Pull aside the winner of each race in the first round for the final heat and eliminate the bottom 2. 8. Run 5 races of 5 horses. (5) Put all the 3rd place horses in a race, winner is 3rd fastest. (6) Put all the 2nd place horses in a race, winner is 2nd fastest. (7) Put all the first place horses in a race, winner is fastest. (8) The third place horse was beaten by one of the 2nd place horses. So third stays in third. Same for the second place horse. chzwiz, r u sure u r not high? B, what happened in round 2? why 8 horses suddenly get eliminated by 1 race? again, do u know what you are smoking? oh, forget J,..... just speachless 7. chzwiz, your answer is incorrect. One of the first or second place horses could be 2nd fastest and/or 3rd fastest. I drew a grid to visualize the problem. First, run five races to establish 5 groups of internally ranked horses, and you can of course immediately eliminate 4 & 5 of each race. 1 2 3 x x 1 2 3 x x 1 2 3 x x 1 2 3 x x Then race 1st place horses, eliminate 4 & 5, and those they beat earlier. You can also eliminate the horses #3 beat, and the 3rd place horse from #2's first race. 1 ? ? X X 2 ? X X X 3 X X X X X X X X X X X X X X You know #1 is fastest. Race the remaining horses (2, 3 and ?'s), and the top two are 2nd and 3rd. After reading the above answers, this is the same as B's revised answer, but I found it easier to explain/visualize with the grid. @brad ... but isnt dat v dont have timer to know d ranking ... or my assumption is wrong?? I thought v know only 1 result of every race .. i.e. top 1 Spawn, it's true that you don't know timings, but you do know RANKINGS. I don't see errors in logic with each answer above. They may claim to discover the answer with fewer races, but they have too many assumptions or errors to be correct. To do this optimally and without any potential error, you must eliminate as many correctly placed horses as possible and eliminate the maximum number of non-win/place/show horses each round. Round 1: (Races 1-5) You must start with 5 heats @ 5 horses apiece. The non-Win/Place/Show horses of each round have been eliminated, leaving 15 horses. Round 2: (Race 6) You then race the top finishing horses against one another, leaving you with your overall fastest horse. We now have the Win horse, leaving only Place and Show as unknowns. This also eliminates the bottom two horses, leaving 2 horses from this race. There are also only two more unknown horses. Race 7) You may race the Place horses against one another. Only two survive this race, since we know that each of these horses can place 2nd at best. This leaves 2 horses from this race. (Race 8) You may also race the show horses of each round. Since they each have been beaten by two other horses in Round 1, only the 1st place horse of this round survives as the potentially 3rd best horse. This will leave 1 horse in this race to battle for the 2 remaining spots. Round 2 leaves 2 Horses (Race 6) + 2 Horses (Race 7) + 1 Horse (Race 8) = 5 Horses, for 2 unknown spots. Round 3: (Race 9) We can now have the final 5 horses race for the remaining two spots leaving us with the undisputed 2nd and 3rd places. Here is a more complex scenario below in which the top 2 horses come from the same original race and the later races are full of lame horses. Many of the solutions above do not address those problems. Each # is a horse, named by it's inherent ranking. X signifies 'eliminated horse' Race1 R2 R3 R4 R5 1-->R6 3-->R6 11-->R6 16-->R6 21-->R6 2-->R7 7-->R7 12-->R7 17-->R7 22-->R7 4-->R8 8-->R8 13-->R8 18-->R8 23-->R8 5X 9X 14X 19X 24X 6X 10X 15X 20X 25X Round 2: Race 6 (Winners) Race 7 (Places) Race 8 1 -->1st Place 2-->Race 9 4-->Race 9 3 -->Race 9 7-->Race 9 8X 11-->Race 9 12X 13X 16X 17X 18X 21X 22X 23X Round 3: Race 9 2P 3S 4X 7X 11X First Place = 1 Horse -- Race 6 Winner Second Place = 2 Horse -- Race 9 Winner Third Place = 3 Horse -- Race 9 2nd place To fix the formatting issues that appeared as spaces are eliminated above-- Race1________R2___________R3___________R4___________R5____ _1-->R6_______3-->R6_______11-->R6_______16-->R6_______21-->R6 _2-->R7_______7-->R7_______12-->R7_______17-->R7_______22-->R7 _4-->R8_______8-->R8_______13-->R8_______18-->R8_______23-->R8 _5X__________9X___________14X__________19X___________24X _6X__________10X__________15X__________20X___________25X Round 2: Race 6 (Winners)__________Race 7 (Places)__________ Race 8 1 -->1st Place_____________2-->Race 9______________4-->Race 9 3 -->Race 9_______________7-->Race 9 _____________ 8X 11-->Race 9______________12X____________________13X 16X_____________________17X____________________18X 21X_____________________22X____________________23X Round 3: Race 9 2P 3S 4X 7X 11X Less ascetically pleasing than the original, but it will suffice. Show More Responses This problem can be reduced to (viewed as) multiway mergesort: 1) split the horses into groups of five as if we had five files to sort 2) do a multiway mergesort but instead of sorting all horses, stop as soon as you get the top 3 We need one race per group to sort them (5 races total). And 3 more races to get the top 3. We will need 8 races. The interviewer might have been looking whether an applicant was able to spot this relation to algorithms or not. But if this was a brain teaser instead, maybe the answer is less than 8. The answer is definitely 7, here is a fantastic explanation: http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/ Randomly race the horses 5 times and keep a winner's bracket. The 6th race will determine the fastest horse. This is trivial. The 2nd and 3rd fastest could be in the winner's bracket or they could be the 2nd or even 3rd fastest in one of the losing brackets. Then we have to race 2nd and 3rd place from the winners bracket as well as from each original bracket, which had 5. This means we have 12 horses to try. Randomly keep 2 horses out and race 5v5. Keep the top two horses from both. We have 6 horses now. Race 3v3 and keep the top two, leaving 4 horses. Then race these. I count 11? Brute force divide and conquer solution = 18 races. Just be aware of the brute force solution in case there's restriction where we can't use the memory to save the first 3 places. Those who want a system that averages that fastest solving time, the answer will be 7 races.. Those gamblers who want an algorithm that gives the fastest possible solving time (all though sometimes it WILL take longer) the answer is 6. Race 1-5: First 5 races of five.. We randomly seed with no overlaps.. we use this to eliminate the bottom two from each race. I am going to use a two digit number labeling system where the first digit is which race in heat one they competed in and the second digit is which place they obtained in that heat.. These are the horses we have left: 11 12 13 21 22 23 31 32 33 41 42 43 51 52 53 Race 6: We have the winners from each heat compete, and for ease of explanation lets say that they ranked 11, 21, 31, 41, 51.. Now we know that 41, 51 and all the horses slower than them (their heats) are out.. also, we know that any horse slower than 31 is out (ie. 32 & 33), and we know that any horse that is at least two horses slower than 21 is out (ie 23). This leaves 11, 12, 13, 21, 22, 31.. 6 horses. Possible rankings: 11 12 13 21 22 23 31 32 33 Race 7 Rank 1 is already known.. and we just need to know how to organize 12, 13, 21, 22, and 31.. And look at that!! that's 5 horses! We race those 5 and the top two receive the overall rank of 2nd and 3rd. 5 races in round one, 1 race in round 2, 1 race in round 3.. it took us 7 races.. Option two: 6 Races Now, an alternate answer.. when we read "What is the minimum number of races to find the top 3 horses" we can interpret that maybe they don't care about this method working every time.. instead they want to hit up the Vegas Casinos and test their luck, and maybe save some track time.. If i was a gambling man.. i would race the first group of those that i thought looked the strongest.. I would eliminate 2 in that race (we are now down to 23 horses).. and then race the 3rd fastest multiple times and hope that he gets first in the remaining races, thus eliminating 4 horses each time. This is going to be painful for the horse that placed 3rd in heat one. Race 1: Eliminate 2, 23 horses remaining Race 2.. Eliminate 4, 19 horses remaining Race 3.. 15 horses Race 4.. Eliminate 4, 11 horses Race 5.. Eliminate 4, 7 horses Race 6.. Eliminate 4, 3 horses.. The original top 3 from Race 1. So using method 2, we completed this race in 6 races instead of 7! I messed up the possible ranks after race 6.. That should have read.. 11 12 13 11 12 21 11 21 22 11 21 31 Please forgive me. Brad's explanation is the perfect one. All other explanations are junk and impossible to read and follow. Round1: (5 groups) remaining horse 15 Round: (1 groups). Topper from each heat Round: (1 gounds). Forget about the 4th and 5th Heat horses (becoz their toppers are at last place) go to the 3rd position 6 races as the 25 horses are divided into 5 groups each grouping 5 horses in each group , then the winner from each group would be 5 then there should be last n final race to find the first , second and third placed horse . in this way we can find our top 3 horses :) It should be 11. In each race you can only eliminate 4th and 5th place simply because there's a chance that the top 3 in that single heat are the 3 fastest of all the horses. So each race you can select 5 random horses each race or keep the top three in the following race, the outcome is the same. Show More Responses I get 8 races to guarantee you get the top three. 5 races of 5 to get the fastest horse from each group. 1 race to determine the fastest overall. The second fastest horse can be in the group (x) that produced the fastest, 1 race with the remaining 4 fastest from the other groups and the second fastest from group x. That race will produce the second fastest overall guaranteed. 1 more race with the 3 or 4 from the original winners and the replacement from the group that produced the second place horse. That makes 8 races. I dont get it.. It shoudl be five races right? U will know how long each horse takes to cover same distance. Pick the three that took shortest. Y need more rounds? If u down vote my answer, u have the obligation to explain why 😜 Answer is 6. You will have 5 races and 5 winners. Next race with 5 winners is the 6th race and you get top 3. You're welcome. It would be 7, mainly because since there only 5 racers each round, then it would be tournament style. As you can tell, tournament style never determines the rankings in the short term. (Imagine if a new tennis player played against Roger Federer and he loses. He's not bad, he's just really unlucky haha) So in order to determine the answer, you would have to use massive logic and reasoning. First step is obvious: you get 5 sets of horses to race through 5 races. So the number is already at 5. We get the top horse in each one and note them. However, one problem is that you have to consider if fastest horses could lie all in the first, second, third, fourth, or fifth group. But we can't determine that yet, so let's race one more time with the winners of each race. Second step: Race with each winner from their groups. That makes 6 total races so far. Ok, now we can get somewhere with this. So now, its a question of which horses we can eliminate to determine the next race. Who can we eliminate though? Well, we can get rid of: - All the horses in the group with the last race that were 4th and 5th place. This makes sense since if the winner of their groups only made 4th and 5th place in the tournament style race, then they are definitely not the fastest horses. 15 horses remaining. - Well, we can also get rid of the last two horses of each group since we are only looking for the top 3. 9 horses remaining. - We also can get rid of the first place winner since we already know he is definitely the best. 8 horses remaining. - Since we already determined who the fastest horse is, now we have to determine who the second and third fastest horse can be. In that case, the second place horse from the last round can get rid of the third horse of that group, since he definitely has no shot of being the first or second fastest horse of this new race. Also, in the third group, we can get rid of the second and third horse in the group due to the same reasoning above. 5 horses remaining. Oh wow! We now have 5 horses left! This means we can just have a clean race and find the second and third fastest horse. So overall, the answer is 7 races! 7 In my opinion, you need 26 RACES to make sure that you get the top 3 without a timer. You need to know that without a timer if we plan only 5 races with 5 horses on each one, the last horse on the first group could end the race in 1 minute while the first horse on the second group (the winner) could end it in 2 minutes, which mean that the last horse of the first group is much faster than the first horse of the second group..and this is why we need to make a total of 26 RACES to determine the top 3 as follow: 5 RACES with 5 horses each .> We get the 5 winners from each race .> We race the 5 winners > We get the top 4 > We race the top 4 with one of the remaining 20 horses > we get the top 4 > we race the top 4 with one of the remaining 19 horses > we get the top 4 > we race the top 4 with one of the remaining 18 horses...etc until the last race then we select the top 3 winners from the last race. 5 RACES + 1 RACE + 20 RACES = 26 RACES |