# Analytical reasoning Interview Questions

interview questions shared by candidates

## Analytical reasoning Interview Questions

### 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. 28 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 |

Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Extend your answer for n trucks. 23 AnswersSo 50 trucks is solvable but annoying. The answer depends on payload size, also if the truck needs to return. If we assume no return and 1 truck can carry the payload. Make the number of trucks 64 for even powers of 2. The trucks all take off together and every 50 miles they all have half full tanks. Half of the trucks are sacrificed to refill the other half. Number of trucks goes from 64 -> 32 -> 16 -> 8 ->4 ->2 -> 1. So 6 splits * 50 miles = 300 + last truck has 100 miles. 400 for 64 trucks. 50 can be solved with annoying fractions. General answer is 50 * log(base2) of n + 100. :-) Yes, your assumptions are correct, and so is your solution. The answer is 450 miles. it is the sum for n=1 to 50 of [ 100 / (50-n) ] After 2 miles you would transfer all of the fuel from one truck, and could fill all 49 of the other trucks. (100mile range / 50 trucks = 2 miles before the first truck could be emptied of all fuel and is not needed to carry any fuel) at that point you only have 49 trucks, so 100/49 is the distance before you park the second truck. After parking 49 trucks you would have one full truck of fuel that would finish the last 100 miles. General solution for X trucks with Y range is Sum for n=1toX of [Y / (x-n)] Show More Responses My equation was off by one, need to sum for n=0to49, not 50. (since 100/(50-50) is infinite obviously it was in error.) The answer is quite simple. You can deliver the payload an infinite distance. Since you have 50 trucks at your disposal you can run one truck with the payload until its near empty then transfer the payload to a full truck. The near empty truck can re-fuel and then drive towards the destination re-fueling as needed. Once the truck with the payload is near empty it can transfer the load to a truck that has recently been refueled. The answer is quite simple. You can deliver the payload an infinite distance. Since you have 50 trucks at your disposal you can run one truck with the payload until its near empty then transfer the payload to a full truck. The near empty truck can re-fuel and then drive towards the destination re-fueling as needed. Once the truck with the payload is near empty it can transfer the load to a truck that has recently been refueled. Ua… Everyone needs to try again... Two trucks go 33 1/3 miles out and the second truck gives ½ of its remaining 2/3 of a tank to the other truck who parks and waits for the other truck to go back. It has enough fuel to return and comes back out with another truck who does the same thing but now we have two trucks 33 miles out and both with 2/3 of a tank or 66 2/3 miles of fuel remaining. With this method of inch worming and returning to refuel you can achieve a spacing of 33 1/3 miles between each truck and continue to refuel the entire chain. Only then once the entire refueling chain is stretched out to the range of 1666.66 miles you can have a truck be totally fueled 100% and then go either 50 more miles and still be theoretically able to return back to home base or 100 miles to sacrifice the truck for a delivery giving you a maximum range of (n + 1) * (1/3 of range) yielding a potential range of 1766 2/3 miles. You use a lot more fuel getting out to where you want to go but your range is increased well above the 400 miles range and the trucks aren’t lost. It is 1800 not 1766... I did the same 0 to 50 vs 1 to 50 miscalcuation. 100 + 51*100/3 = 1800 Ua… Everyone needs to try again... Two trucks go 33 1/3 miles out and the second truck gives ½ of its remaining 2/3 of a tank to the other truck who parks and waits for the other truck to go back. It has enough fuel to return and comes back out with another truck who does the same thing but now we have two trucks 33 miles out and both with 2/3 of a tank or 66 2/3 miles of fuel remaining. With this method of inch worming and returning to refuel you can achieve a spacing of 33 1/3 miles between each truck and continue to refuel the entire chain. Only then once the entire refueling chain is stretched out to the range of 1666.66 miles you can have a truck be totally fueled 100% and then go either 50 more miles and still be theoretically able to return back to home base or 100 miles to sacrifice the truck for a delivery giving you a maximum range of (n + 1) * (1/3 of range) yielding a potential range of 1766 2/3 miles. You use a lot more fuel getting out to where you want to go but your range is increased well above the 400 miles range and the trucks aren’t lost. Ua… Everyone needs to try again... Two trucks go 33 1/3 miles out and the second truck gives ½ of its remaining 2/3 of a tank to the other truck who parks and waits for the other truck to go back. It has enough fuel to return and comes back out with another truck who does the same thing but now we have two trucks 33 miles out and both with 2/3 of a tank or 66 2/3 miles of fuel remaining. With this method of inch worming and returning to refuel you can achieve a spacing of 33 1/3 miles between each truck and continue to refuel the entire chain. Only then once the entire refueling chain is stretched out to the range of 1666.66 miles you can have a truck be totally fueled 100% and then go either 50 more miles and still be theoretically able to return back to home base or 100 miles to sacrifice the truck for a delivery giving you a maximum range of (n + 1) * (1/3 of range) yielding a potential range of 1766 2/3 miles. You use a lot more fuel getting out to where you want to go but your range is increased well above the 400 miles range and the trucks aren’t lost. And if you want to be creative - 25 of those trucks can toe fully-fueled 25 trucks. Wanna try again? This is a straightforward programming problem. Clever solutions such as allowing the other trucks to refuel and allowing other trucks to tow extra trucks full of fuel rarely impress the interviewer. The simplest solution involves recursion, or induction. Imagine a function f(n) where f(n) is the distance n trucks can carry the load, the problem defines f(1)=100, and we're asked to solve for f(50), so our job is to solve for f(n) in terms of f(n-1), f(1) and n. It's safe to assume each truck, including the fully loaded truck will travel the same distance and that fuel is used uniformly over the distance. So with n trucks, the trucks should travel just far enough that n-1 trucks have room in their tanks for the nth truck's fuel, then transfer an solve for n-1. This equation is f(n) = f(1)/(n) + f(n-1) (All perl vs python vs ruby/etc wars aside) Plugging this into a simple scripting language such as perl is an easy way to solve this: sub f{ my $n = shift; return 100 if($n == 1); return f(1)/($n) + f($n-1); } print "50: " . f(50) . "\n";' On the command line, this gives a quick answer: > perl -e 'sub f{ my $n = shift; return 100 if($n==1); return f(1)/($n) + f($n-1);} print "50: " . f(50) . "\n";' 50: 449.920533832942 Approximately 449.92 miles with 50 trucks. The recursive subroutine above will suffice as a general solution in terms of n. Not a programmer but this is how I solved it. You obiously want to shed a truck as soon as the other trucks have room for the fuel from one truck. Since trucks have a range of 100 miles when all trucks have a tolal of 100 miles you can refill all truck s from one truck's remaing fuel. 100 miles divided by 50 trucks is 2 so two miles is the first refueling point at which time you will lose one truck. So I set up a Excel worksheet. Column A number of trucks beginning with 50 down to 1. Column B has formula 100/A1. Sum column B is 449.9205. Same as other s have come up with. Show More Responses This would depend on the fuel efficiency of the trucks. You could almost certainly get much farther by having the first truck tow all 50 others, once it runs out of fuel take it out of the train and continue on. One truck pulling others will still get better fuel efficiency than all trucks by themselves. ie you get 10mpg from a truck by itself, and 7 with it pulling the others, vs all using 10mpg at once. 50 trucks with a 100 mile range. The question does not state that all the trucks have to be in the same place to start. It's pretty easy. All the trucks are 100 miles apart. Therefore you can transfer the payload up to 5000 miles. I hate these problems. The interviewer is normally probing for a specific answer, and unwilling to understand that the question is fundamentally flawed, and whit they are looking for is being asked in obtuse way, often for the a wrong answer. Much of hte answer depends on what is or is not available in this crazy mad max world. Is there no more fuel in the world? Can the trucks refuel at the main depot? Is it okay to leave trucks parked on the side of the road? Sometimes the interviewers are asking about how you validate assumptions or deal with your own invalid assumptions of the world... normally not. Of course the normal answer would be 50 or 45 miles range. Shifting loads and siphoning fuel is a pita. The next answer would be get a CFN card and trusted drivers, then range is more limited by periodic maintenance i.e. oil changes. Failing that, as was done during the 1970s oil crunch, get some 50 gallon drums and tie them up to the back of the headache bar. Each gallon of diesel weighs about 8 lbs, and can get you about 4 miles down the road. The united states is about 3000 miles wide. That takes about 6000 lbs of fuel. To get back another 6000. It's not very efficient, but you won't get stuck on the side of the road. due to fuel reasons. But if you want a wanky CS answer. ( similar to JP's answer, but carrying it to stupidity). With trucks returning to an infinitely fueled depot: ( my favorite extra world pieces). By driving two trucks too 50 minus a smidgen miles. Park a truck with a driver in it, and it will have a smidgen of fuel in it. The other truck will keep making trips from 0 to 50 minus a little and transfer it's excess fuel to the parked truck. Eventually there is a fully fueled truck 50 (minus a little) miles from the depot. This chain can be extended one link at a time like some horrible towers of Hanoi problem. Finally you end up with a line of n-1 fully fueled trucks. This line alone stretches 2450 miles (minus 49 smidgens). The last truck in the line could round trip out to 2500. ( n * range/2) After you have a row of fully fueled rucks 2450 miles long, there might be something funky you could do with it to extend the range. Truck 1 would have 1/2 a tank at the next truck, 25 miles into the second leg it could park and the second truck would then have a full tank at 75 miles from base, but not be able to return. Scale this up across the entire line of trucks. ... one short throw away perl script later... looks like that'll get you about another ~100 miles. so almost 2600 miles with parked empty trucks. Maybe a nonlinear spacing would be beter, not sure.. don't care really. The fundamental answer is that most CS wanking stuff is often irrelevant in the real world. Money money money, cost cost cost. 50 trucks is somewhere in the piles of money range, quit wasting fuel. very simple to understand solution public class test { public static void main(String [] args) { int num=50; double result=0; for(double i=num;i>0;i--) { result=result+100/i; } System.out.println(result); } } Wow, Daren up top is definitely correct. I propose it's a little simpler than that. It is just the summation of n=1 to n=50 for 100/n Call the last truck the first truck, n=1. being full, it can go 100 miles. when there are 2 trucks left, 50 miles repeated down to the starting fleet of 50 trucks going 2 miles. pretty sure using x-n doesn't bring the world down on itself, but it's unnecessary and makes that 49 to 0 error much easier to fall for. @Daren Yes I reached the same equation as well. Sum for n=0 to 49 of [ 100 / (50-n) ] A quick spreadsheet run shows the result as 449.92 miles. It's a horrible and pointless thing to ask this question in an interview without the help of a calculator or spreadsheet. I guess my brain also oversimplified the problem. Since it was never stated that all 50 trucks needed to start from the same location I spaced them 100 miles apart towards the destination. If fuel is easier to transfer at each 100 mile point transfer fuel; else transfer payload for a maximum payload delivery distance of 500 miles, OR Number_of_Trucks * Range = Maximum_Payload_Delivery_Distance I'm a software engineer, but would have answered this completely differently. You have 50 trucks with a value of say $70,000 each, and 50 full fuel tanks. Sell 49 trucks, drive the 50th to the local fedex and and tell them where to deliver the payload . With the money remaining buy a villa in the South of France and retire. ques is how far u can deliver the payload that totally depends on the ranging limit of fleet of trucks that is 100 miles . it means they cannot move before 100 miles even if we transfer the fuel one after the another it has no sense here , let suppose one truck travels 100 miles (max) , we are not considering that it get emptied before reaching 100 miles after that next truck travels , so the total of distance that could be travelled is 100*50 miles = 5000 miles (this is the max distance the payload can be taken ) while the least could be 100 miles . Ok first determine the payload capacity of a truck. How many trucks required for payload. Assign one or mire truck to carry the fuel of other trucks which wont be delivering |

### Software Engineer at Google was asked...

You have a genealogy: 1) Describe a data structure to represent it. 2) Given any two people within the genealogy, describe an algorithm to determine if they share a common ancestor. You just need to return true/false, not all ancestors. 6 Answers1) Each person is represented by an object, with two pointers: "mom" and "dad" that point to their respective parent. 2) Choose one of the two people arbitrarily. Perform depth-first traversal and create a set of ancestors reachable from that person. Perform depth-first traversal on the 2nd person and for each node visited check if they are in the set; if yes, return true. Use a hash-set for best performance. calculate the height of person 1 in the tree, calculate the height of person 2. Move them up to be the same height. Then keep going until they intersect. @user: Its not a tree. A genealogy is a graph due to the fact that you have maternal and paternal trees intersecting. Therefore there is no root from which to calculate height. Show More Responses If you've optimizing for worst case, hash set is O(n) for search. You'd do better in worst case with a sorted structure. You'd do even better if you store a "visited" flag at each node. Alternately you can number each node and keep an array of visited flags. since depth first seach might find a longer link through dad before checking mom, you're better off with breadth first search. Anything reachable in one hop would be seen before anything reachable at best in 2 hops Yes. Good points. The second traversal should be breadth first. The first traversal it doesn't matter, as you need to visit all ancestors anyways. The use of a visited flag is a good optimization. Based upon the way the question was worded, it wasn't clear if you could design the data structure to optimize the algorithm or not. I belive both the first and second should be BFS traversals |

### Mobile Developer at Pocket Gems was asked...

At a movie theater, the manager announces that they will give a free ticket to the first person in line whose birthday is the same as someone who has already bought a ticket. You have the option of getting in line at any time. Assuming that you don't know anyone else's birthday, that birthdays are distributed randomly throughout the year, etc., what position in line gives you the greatest chance of being the first duplicate birthday? 2 Answersx/x-1 < 356/(365 - x) 20th |

### Mobile Developer at Pocket Gems was asked...

You are in a game of Russian Roulette with a revolver that has 3 bullets placed in three consecutive chambers. The cylinder of the gun will be spun once at the beginning of the game. Then, the gun will be passed between two players until it fires. Would you prefer to go first or second? 2 AnswersWould go First as Probability for winning is 4/6. Imagine a 6 chamber gun with chambers labeled A through F in a circular fashion. Chambers A, B, and C have the bullets (remember the bullets are placed consecutively). If the first shot is from chambers A, B, or C, Player 1 dies/loses. If chamber D is first, Player 1 will win. If chamber E fires first, Player 1 will die/lose once the gun is passed back to him at chamber A. So overall, Player 1 has a 4/6 chance of dying, and Player 2 has a 2/6 chance of dying. Therefore, I would prefer to go second. |

### Systems Engineer at BAE Systems USA was asked...

Why does a curveball pitch in baseball curve? 3 AnswersI would suggest doing a search to get a good technical answer to this. It will have to do with changes in pressure most likely. The secret behind the curveball is the spinning action created when the pitcher releases the ball. Friction and air are the key It's the spinning of the ball. Picture the ball segmented through its axis with a plane parallel to the ground. The top half is spinning forward (forward relative to its translating motion). The forward rotation increases the drag of the ball due to the no-slip boundary condition of the air flow at the immediate surface of the ball. The bottom half is the opposite. The ball is rotating away from the translated motion and the drag is less. The resultant vector of the drag force on the ball is pointed more toward the ground. |

What would you do if you were faced with a problem that you could not solve. 2 AnswersAny problem can be solved with th right resources. Get help and keep working it until it is fixed. The answer posted is an excellent answer but if it were me I would counter with another question. The quite obvious answer could be the worst possible solution. Why would you want me to solve a problem inefficiently through trial and error that could possibly result in greater complexities and produce additional problems? There is always a time when a problem may not have an immediate and effective solution. They as management should be asking themselves this same question: What do yout do in the case that a single resource cannot adequately address a problem? |

### Associate at L.E.K. Consulting was asked...

How many people are in Logan Airport at 9am on a Monday morning? 2 AnswersNeed to remember that some flights can use Boston as a connection. Don't forget passengers have family/friends that send them off. The best approach is to divide out into different categories of people: passengers, workers, friends/fam etc. and then estimate each. To estimate passengers, estimate number of run ways available (based on # of terminals) and what portion has planes, how big the size of the plane is etc... Do not forget the number of runways in order to estimate the number of passengers |

If you had 2 6-sided dice, what's the probability you get a 7? 2 Answershere are the different ways you can get 7 1-6 6-1 2-5 5-2 3-4 4-3 prob(7) = [Prob(1)*prob(6) + prob(6)*prob(1).......................+prob(4)*Prob(3)] = 1/6 You should ask if the dice are fair. |

### Architect at NVIDIA was asked...

Four people, (A, B, C, and D) need to get across a river, and there is only one boat. The boat can only hold two people at a time and will only go as fast as the slowest person in the boat. If it takes A one minute to cross, B two minutes, C five minutes, and D seven minutes, what is the shortest time for all 4 people to cross the river? 3 Answers14 minutes is the fastest time. A and B go first (2 min), then A comes back (3 min), next C and D goes (10 min), then B comes back (12 min), finally A and B go across again (14 min). The trick is hiding C's time within D. The other guy has got it wrong . When C and D go how come B comes back ? 1. D and A go . A comes back - = 7+1 = = 8 min 2. A and C go . A comes back = 5+1 = 6 min 3 A and B go . = 2 min Total time 16 min Well, Whar the above person means is, A+B go ---> 2 mins A comes back --> 1 min C+D go --> 7 mins B comes back --> 2 mins A+B go --> 2 mins. Total --> 14 mins B comes back because he has crossed the river and is on the other side and can come back. |