# Engineering Interview Questions

Engineering interview questions shared by candidates

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

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 QA Engineer at Apple was asked...

There are three boxes, one contains only apples, one contains only oranges, and one contains both apples and oranges. The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels. Opening just one box, and without looking in the box, you take out one piece of fruit. By looking at the fruit, how can you immediately label all of the boxes correctly? 38 AnswersAll the three boxes are names incorrectly. SO the bax lebeled Apples+Oranges contains only Oranges or Only Apples. Pick one fruit from it. If it is Orange then lebel the box as Orange. So the box lebeled Oranges contains Apples and the remaining contains both. Label the boxes fruit. The key bit is "All the three boxes are names incorrectly" so the label on the box which fruit comes from will need to be changes to one of the other 2 labels. It can only be 1 of them (and it will be obvious when you have the fruit) then the remaining box (that hasnt featured yet)...Just swap that label with fruit box that was originally on the box which you took the fruit out of Thats hard for anybody to understand somebody elses explanation... eaiest way is to just do an example Show More Responses Swaz answer is almost correct however it does not work in all scenarios. lets assume: box 1 is labelled Oranges (O) box 2 is labelled Apples (A) box 3 is labelled Apples and Oranges (A+O) and that ALL THREE BOXES ARE LABELLED INCORRECTLY" Pick a fruit from box 1, 1) if you pick an Orange: - box 1's real label can only be O or A+O - box 1's current label is O - since ALL LABELS ARE INCORRECT then box 1's real label can not be O - box 1's new label should then be A+O by elimination - since ALL LABELS ARE INCORRECT - box 2's label is changed to O - box 3's label is changed to A - SOLVED 2) if you pick an Apple: - box 1's real label can only be A or A+O - box 1's current label is O - since ALL LABELS ARE INCORRECT then box 1's real label can not be O - this still leaves us with the choice between label A and label A+O - which would both be correct - FAILURE Solution: The trick is to actually pick a fruit from the A+O labeled box Pick a fruit from box 3: 1) if you pick an Orange: - box 3's real label can only be O or A - box 3's current label is A+O - since ALL LABELS ARE INCORRECT then box 3's real label can not be A+O - box 3's new label should then be O by elimination - since ALL LABELS ARE INCORRECT - box 1's label is changed to A - box 2's label is changed to A+O - SOLVED 2) if you pick an Apple: - box 3's real label can only be O or A - box 3's current label is A+O - since ALL LABELS ARE INCORRECT then box 3's real label can not be A+O - box 3's new label should then be A by elimination (not O) - since ALL LABELS ARE INCORRECT - box 1's label is changed to A+O - box 2's label is changed to O - SOLVED it only says you can't look, doesn't mean you can't feel around or smell the fruit you picked, easy deduction after you figure the first box out Sagmi is right, but did not give the full reasoning. "the bax lebeled Apples+Oranges contains only Oranges or Only Apples. Pick one fruit from it. If it is Orange then lebel the box as Orange." so far so good Now, the box labelled Apples cannot be the box containing only Oranges, you've just found that box, so it must contain Apples and Oranges. And in that case the other box, labelled Oranges, must contain only Apples. It's easier to draw it out. There are only 2 possible combinations when all labels are tagged incorrectly. All you need to do is pick one fruit from the one marked "Apples + Oranges". If it's Apple, then change "Apple + Orange" to "Apple" The "Apple" one change to "Orange" The "Orange one change to "Apple + Orange" If it's Orange, then change "Apple + Orange" to "Orange" The "Apple" one change to "Apple + Orange" The "Orange" one change to ""Apple" Since all 3 boxes are labled incorectly Start with the box Labled A&O. If Its apples than the box labled apples then the apple one is oranges and the oranges is O&A. Label each box "Apples and/or Oranges" and the all will be correct. This is very simple to resolve. I was asked the same question at FileMaker. Each box is incorrectly labeled. So you go to the box that is labeled "Oranges and Apples" and take one out. It doesn't matter what comes out because all that you know is that it is not AO. If you remove an Apple then move the Apple label to it. Since the Apples are already identified it is easy to resolve the rest. All you know for certain is that the other two boxes remaining are mislabeled. So the AO label goes on the box with the remaining label and that label goes on the Apple box as you have already assigned that. The end result is you only need to remove one piece of fruit to figure out the proper locations of all. Go down the road to HP. Maybe they are hiring. Some of these pseudo-problem solving questions like this are bunk. I was once asked why sewer covers are round and not square. I gave the correct answer without even hesitation and the interviewer seemed put off that I knew the answer. I didn't get the job but, in hindsight, no great loss. I prefer the questions (like the basketballs one from google) where you won't be able to give an accurate numerical answer but by explaining HOW you would go about solving the problem is all you need to do and MAYBE shows your aptitude for problem solving. Smell the box you opened. Step 1: Order the boxes by weight. Either apples weigh more than oranges, or oranges weigh more than apples. The mixed box will always be in the middle. Step 2: Open the first box, take out the fruit and look at it. Step 3: If the fruit is an apple, deduce that the middle is apple and oranges and that the third box is oranges. If the fruit is an orange, then deduce that the last is the box with the apples. Show More Responses Donna is the only one with any common sense. The problem with corporate America, is that it's run by a bunch of Bozos who over complicate things and have a narrow to zero vision on how to solve even the simplest problems. I can imagine that most of you would get a committee, have long meetings where you talk about 'think out of the box', and 'at the end of the day' nonsense. This is an interesting logic question, but I would not want to buy fruit from a company who knew they had a problem and then sampled one out of three boxes to resolve the issue. There are other correct answers posted. I'll just make a comment: "The boxes have been incorrectly labeled such that no label identifies the actual contents of the box it labels." Nothing in the above statement says the labels are limited to oranges/pears, only that they do not identify the contents. They could say 'nuts', 'bolts', etc. Technically, all answers should be prefaced with: assume that the labels say 'oranges', 'pears', and 'orange/pears'. Ok, the problem does not make sense and is unsolvable if the labels say 'x', 'y', 'z', but someone with (likely with a math proof back ground) may appreciate attention to detail. Q: Why do posters denigrate the interview questions? The questions, however stupid they may be, are a opportunity to show you can build an answer. Even if you pursue an invalid train of thought in the interview, it's a thought. It's what they want to see and what will help you get a job offer. Note: I also would not assume that the questions asked are a reflection on the company, department, or team as a whole. It may just be the interviewer that has chosen poorly. So to say "I don't want to work for company X because they asked me a stupid interview question" is pretty closed minded. To even think I don't want to work with that interviewer just based on questions asked seems extreme. rightly pointed out by Sagmi ... this question was put forward to me at Huawei Technologies and that was the answer I gave So the question was asked at an interview for Apple: Label ALL the boxes apple and charge a ridiculous price for them! Just label all of them "Fruit." Put another way, it is not possible to tell since we don't know how the boxes are mis-labled. What if the Apple box was labeled Oranges and both the other boxes were labeled Apples and no box was labled Apples and Oranges? You might have assumed there are three different labels when their might have only been two different labels. Always pict a piece of fruit from the box labelled Apple&Orange. As we know that this label is wrong, there are two possibilities: If it is apple, then wo know that this box should be labelled Apple, so we switch Apple label with the label Apple&Orange. Then Apple label is correct. We also know that the Orange label is incorrect, so we then switch Orange label and Apple&Orange label. if it is orange, then we know that this box should be labelled Orange, so we switch Orange label with label Apple&Orange. Then Orange label is correct. The same as above, we know that the Apple label is incorrect, so we switch Apple label and Apple&Orange label. If all boxes are labeled incorrectly and u pick a orange out of a box that's labeled apple/oranges change the name to oranges then change the box labeled oranges to apples and the the box labeled apples to apple and oranges... If you pick a apple out of a box labeled apples and oranges change the name to apples and then change the box labeled apples to oranges and the last to apples and oranges... If u pick a apple out of a box labeled oranges change it to apples and oranges then the box labeled oranges to apples and the box labeled apples to oranges...if you pic a orange out of a box labeled apples change it to apples and oranges and the box labeled oranges to apples and the last to apples and oranges... See the pattern? I think there is a big box and it contain two small boxes and all the labels are incorrect so big one contain two boxes that makes it carrys both orange and apples and in that thwo boxes having orange and apple respectively so if we open any box we can label it correctly Show More Responses To see the java source code of puzzle, visit: https://github.com/SanjayMadnani/com.opteamix.microthon code is taking the input by console only. You can fork or clone the repository and proceed further. You can also rise bug if you find any. Run BasketPuzzleGameTest.java class as a Junit test case to start game. if it known already that boxes labeled incorrectly, I would give it back to those who did label them and ask to fix this confusion. it is impossible to tell by opening only one box, so you have to open one more box. As mentioned already, if you start with the A+O bucket, you can solve the puzzle by pulling only one fruit, Bucket: A+O Found: A Bucket A+O > A | A+O, but since A+O label is incorrect, then it must be A Bucket O > since A is taken, the new label must be O | A+O, but since O is incorrect, it must be A+O Bucket A > since A and A+O are taken, it must be O Bucket: A+O Found: O Bucket A+O > O | A+O, but since A+O label is incorrect, then it must be O Bucket A > since O is taken, the new label must be A | A+O, but since A is incorrect it must be A+O Bucket O > since O and A+O are taken, it must be A If you are lucky, you might solve it with just one fruit even if you start with other buckets, Bucket: A Found: A Bucket: A > A | A+O, but since the A label is incorrect, it must be A+O Bucket: O > A | O, but since the O label is incorrect, it must be A Bucket: A+O > since A+O and A are taken, it must be O Bucket: O Found: O Bucket: O > O | A+O, but since the O label is incorrect, it must be A+O Bucket: A > A | O, but since the A label is incorrect, it must be O Bucket: A+O > since A+O and O are taken, it must be A If you start with the A bucket and pull an O or if you start with the O bucket and pull and A, then you are SOL and you need to pull out more fruits to figure it out. 1. Open one box and check its contents. 2. Remove the current label and apply the correct one (by removing it from one of the other boxes) 3. Since all boxes have been labeled incorrectly, switch labels between the other 2 boxes. And Voila you have all the boxes labelled correctly :) In requirement already specify that all three box labels are not correct. A+O A O Step1: First Pick an item A+O Box. If you get an Apple then it is a Apple Box. swap the label . A A+O O AS we already know in the box that label with Orange, does not contain Orange because of wrong label. So It must contain A+O. Just Swap the label A O A+O OK, all 3 boxes are incorrectly labeled. Open the one that says apples and oranges. Whatever is in there is what it is (since it cannot be apples AND oranges). Now, if there was an orange in there, apples must be in the orange box (since they cannot be in the apples box), and apples and oranges in the apples box (due to process of elimination). Get it? I guess questions like these will appear easy if you put them on paper, it is the possible combinations that become relevant, one way to approach is.. One of the key factor is all boxes are labelled incorrectly, this gives rise to only (2) combinations right To label for 1st box incorrectly you will have (2) options, once you label it then you have only choice to label the other two boxes incorrectly so 2 x 1 = 2 combinations possible i.e. Incorrect lablling options { Boxes_with_Oranges, Boxes_with_Apples, Boxes_with_Apples&Oranges } = { A, AO, O} or {AO, O, A} 2. To know for sure the contents of the boxes, you need to pick the box with either Apples or Oranges and avoid box with Apples and Oranges. So from the (2) combinations you could pick a fruit from Box_labeled AO (this will contain either Oranges or Apples) So, if you get a Orange, it means that combination is{AO, O, A} , so that means Box_with_Label_O has Apples, Box_with_Label_A has Apples and Oranges Box_with_label_AO has Oranges or else if you get a Apple that combination is {A, AO, O}. Box_with_Label_AO has Apples, Box_with_Label_O has Apples and Oranges Box_with_label_A has Oranges Then you can correctly label all the 3 boxes. First answer in this post is correct, as its said all boxes doesnt reflect correct items in it, If an apple is picked from a box , then it can be from either A/O box or A box, if the box is names A/O the, the label of the box has to be changed to A, then other two box labels to be accordingly. It is interesting that in 6 years people keep overthinking this. The answer is in the question and the criteria are that the boxes are immediately labeled and they are labeled correctly. ANSWER: FRUIT FYI you don't even need to open one box. Show More Responses Your choice going to be (( 2 apple 1 orange)) or (( 2orange 1apple )) . It can be recognize only one box (x) . U have to chose again until u get another formula then u will named easly . Step 1: Open a box labeled ‘Apples and Oranges’. We know that this box does not contain ‘Mixture’ for sure. If this fruit is an apple, then label this box as ‘Apple’. Step 2: (Very important) If we look at the box labeled as ‘Oranges’, we know that since the label is incorrect, this box either has only apples in it or has Mixture. Since we already know which box contains only apples, we know that the box labeled as ‘Oranges’ contains ‘Mixture’. So label it as ‘Mixture’. Step 3: (Very easy) The 3rd box will be labeled as ‘Oranges’. When you put your hands on the box to pick the fruits by touching every fruits you can feel whether all are apple or oranges or both and just pick one to see.So it is not necessary to pick one fruit and see whether it is orange or apple also it is not said in question that you can touch and feel all the fruits inside the boxes without taking it out .and then you can fix the label correctly on the boxes. Absurd, no logic km I will took a pen and stab the apple. and then ? apple-pen. |

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

Given the list of points of the skyline of a city in order (from East to West) Find the maximal rectangle contained in this skyline. I was asked to write the code. I managed to find the algorithm but was not sufficient. 21 Answersjust google for skyline. @Interview Candidate Have you found any particularly clear explanations? I'm working on a solution - I'll post it later tonight - but it'd be nice to confirm my understanding. Thanks. Clear? Well, to be more exact: Given N points on 2-plane: (x1, y1), (x2,y2), ... , (xN, yN) s.t. x1=0, xN= 0 and for all 10,yM > 0. Find the maximum value of the area of a rectangle inside the region bounded by these points and the x-axis. You can assume that the rectangle's edges are going to be parallel to the x,y axes. Show More Responses Here's an O(n^3) dynamic programming solution. It's pretty ugly, but it seems to work. More elegant/efficient solutions would be greatly appreciated. -------------------------------------------- import java.util.ArrayList; public class Skyline { private int maxX; private int maxY; public String[] findLargestRectangle(String[] points){ // First translate the points into a boolean matrix. // The cell [i][j] in the matrix should be true if // it appears under the skyline and false otherwise. boolean[][] cells = this.pointsToMatrix(points); System.out.println("Matrix is: "); this.printBooleanMatrix(cells,maxX,maxY); // Now we calculate rectangle size. Define // s[i][j] to be the size of the rectangle // with (i,j) at its upper left corner. int[][] s = new int[maxX+1][maxY+1]; int maxSizeX = 0; int maxSizeY = 0; int maxSize = 0; for (int i = 0; i maxSize){ maxSize = max; maxSizeX = i; maxSizeY = j; } } } System.out.println("Size matrix is: "); this.printIntegerMatrix(s,maxX,maxY); System.out.println("Maximum rectangle has size " + maxSize + "."); System.out.println("Its upper left corner is (" + maxSizeX + "," + maxSizeY + ")."); return null; } // Points to be given as "1 0", "2 5", etc. private boolean[][] pointsToMatrix(String[] points){ ArrayList list = new ArrayList(); // The maximum x-value will be that of the last point. maxX = Integer.parseInt(points[points.length-1].split(" ")[0]); maxY = 0; for (int i = 0; i maxY) maxY = y; list.add(new Point(x,y)); // Assume there are no duplicates } System.out.println("Points are: " + list); System.out.println(" maxX = " + maxX + ", maxY = " + maxY); boolean[][] m = new boolean[maxX+1][maxY+1]; int prevX = 0; int prevY = -1; for (int k = 0; k 0){ m[x][j] = true; j--; } } else { // Look left. If the cell to the left is false, then this cell // is true (start of rectangle top). The value of the cells below // is also true. // // If the cell to the left is true and the previous point had the same value // of x, then this cell represents the start of another rectangle. Set its value // to true and the values of the cells below to true. if ((! m[x-1][y]) || (prevX == x)){ m[x][y] = true; while (j > 0){ m[x][j] = true; j--; } // If the previous value of y is the same as this value of y and the // difference between x values is greater than 1, fill in the cells // in between. if (prevY == y && (x - prevX > 1)){ int i = x-1; while (i > prevX){ j = y; while (j > 0){ m[i][j] = true; j--; } i--; } } } // If the cell to the left is true and the previous point had a different // value of x, then this cell is false (end of rectangle top). Set it and // the cells below it to false. This cell may be inside another rectangle, // in which case its value will be reset to true. else { m[x][y] = false; while (j > 0){ m[x][j] = false; j--; } } } prevX = x; prevY = y; //System.out.println("After " + p + ", matrix is: "); //this.printBooleanMatrix(m,maxX,maxY); } return m; } (cont'd) private void printIntegerMatrix(int[][] b, int maxX, int maxY){ for (int j = maxY; j >=0; j--){ for (int i = 0; i =0; j--){ for (int i = 0; i <= maxX; i++){ System.out.print(String.format("%8b",b[i][j])); } System.out.println(); } } class Point implements Comparable{ int x; int y; Point(int x, int y){ this.x = x; this.y = y; } public int compareTo(Object o){ Point p = (Point) o; return (this.x != p.x ? this.x - p.x : this.y - p.y); } public boolean equals(Object o){ if (! (o instanceof Point)) return false; Point p = (Point) o; return (this.x == p.x && this.y == p.y); } public int hashCode(){ return x*37 + y*19 + x*11 + y*7; } public String toString(){ return "(" + x + "," + y + ")"; } } /** * @param args */ public static void main(String[] args) { String[] points = {"0 2","1 2","1 1","2 1","2 3","3 3","3 0"}; Skyline s = new Skyline(); s.findLargestRectangle(points); System.out.println(); String[] points1 = {"0 1","1 1","1 4","2 4","2 3","3 3","3 6","4 6","5 3","7 3","7 7","8 7"}; s = new Skyline(); s.findLargestRectangle(points1); } } Output: Points are: [(0,2), (1,2), (1,1), (2,1), (2,3), (3,3), (3,0)] maxX = 3, maxY = 3 Matrix is: false false true false true false true false true true true false false false false false Size matrix is: 0 0 3 0 2 0 2 0 3 2 1 0 0 0 0 0 Maximum rectangle has size 3. Its upper left corner is (0,1). Points are: [(0,1), (1,1), (1,4), (2,4), (2,3), (3,3), (3,6), (4,6), (5,3), (7,3), (7,7), (8,7)] maxX = 8, maxY = 7 Matrix is: false false false false false false false true false false false false true false false false true false false false false true false false false true false false true false true false false false true false false true true true false true true true false false true true true false true true true false true true true true false true true true false false false false false false false false false false Size matrix is: 0 0 0 0 0 0 0 7 0 0 0 0 6 0 0 0 6 0 0 0 0 5 0 0 0 5 0 0 4 0 4 0 0 0 4 0 0 9 6 3 0 9 6 3 0 0 6 4 2 0 6 4 2 0 4 3 2 1 0 3 2 1 0 0 0 0 0 0 0 0 0 0 Maximum rectangle has size 9. Its upper left corner is (1,3). Found bug: public *int* findLargestRectangle(String[] points){ ... *return maxSize*; } (obviously) I don't mean to discourage you but there is no way that you can get away with an answer that works in O(N^3) for this question and even if the interviewer was happy with this performance, it would be impossible for you to write this kind of code given a reasonable time limit for the interview (which is around 45 minutes, and that's the entire interview which includes introduction and possibly some other easy questions) You can solve this in O(N). I don't have time to write a solution right now, I strongly recommend looking at Topcoder's skyline problems and contestants' solutions for an insight. best of luck to you For others' reference: http://www.topcoder.com/stat?c=problem_statement&pm=7473&rd=10661 http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm337 https://www.spoj.pl/problems/HISTOGRA/ http://www.informatik.uni-ulm.de/acm/Locals/2003/html/judge.html Here's a much nicer O(n^2) solution. As Anonymous said, there's an O(n) solution, too. /* * In this input array a, the ith building * has height a[i], which means its lower left * corner is at (i,0) and its upper right corner * is at (i+1,a[i]). All buildings have width 1. * The total width of the skyline is n. */ public long getMax(long[] a){ int n = a.length; int[] leftWidths = new int[n]; int[] rightWidths = new int[n]; // For each building, check how many units width to the left of the // top block of this building we can move before we are no longer // in a building. for (int i = 0; i = 0) && a[x] >= a[i]) { x--; count++; } leftWidths[i] = count; } // For each building, check how many units width to the right of the // top block of this building we can move before we are no longer // in a building. for (int i = 0; i = a[i]) { x++; count++; } rightWidths[i] = count; } // Now find the maximum rectangle. The value of the ith building's // rectangle is its horizontal width times its height, or // (1 + leftWidths[i] + rightWidths[i]) * a[i]. long maxArea = 1; for (int i = 0; i maxArea) { maxArea = nextArea; } } return maxArea; } O(n) solution: /* * Basic idea: use a stack to store the buildings. Look at * the buildings in left-to-right order (west to east). If a * building is taller than the building on the top of the stack * (the tallest building to its left), push it onto * the stack. If a building is equal in height to the building on the * top, skip it. If a building is shorter than the building on the top, * it is not part of the maximum rectangle that is topped by the tallest * building to its left. Pop that tallest building, calculate its area and * compare it to the current main area, then repeat the comparison * procedure with the new tallest building. * * Along the way, track the number of buildings to the left and right of a * given building that would participate in that building's maximum * rectangle. The number to the left is equal to the number of buildings * that are popped off the stack before this building is pushed - that is * the number of buildings to the left of this building that are taller. * We do not need to worry about the buildings that are equal in height * since they are discarded (they are accounted for in the topBuilding's * rightWidth count). * * The number of buildings to the right of this building that participate * in this building's maximum rectangle is equal to the number of buildings * that are discarded because they are equal to this building's height * plus the number of buildings that are pushed onto the stack because they * are taller than this building while this building is on the top of the * stack. * * In this input array a, the ith building has height a[i], which means * its lower left corner is at (i,0) and its upper right corner is at * (i+1,a[i]). All buildings have width 1. The total width of the skyline * is n. */ public long getMax_useStack(long[] a){ Stack stack = new Stack(); int n = a.length; long maxArea = 1; // Process the buildings in left-to-right order. for (int i= 0; i < n; i++){ Building nextBuilding = new Building(a[i]); // Keep track of the number of buildings that we pop before we // push nextBuilding. That number will be equal to the number // of buildings to the immediate left of nextBuilding that are // taller in size. int popCount = 0; // If the stack is empty, push the next building onto the stack. // There are no buildings to its left, so we do not need to // update nextBuilding.leftWidth. if (stack.empty()) { stack.push(nextBuilding); continue; } (cont'd) // Otherwise, compare the new building's height to the building on // the top of the stack until the new building is either // discarded (if it is equal in size) or pushed (if it is taller). while (! stack.empty()){ Building topBuilding = stack.peek(); long heightDiff= nextBuilding.height - topBuilding.height; // If the new building is equal in height, skip it. Increment // the rightWidths count of topBuilding as its largest // rectangle goes through the new building. if (heightDiff == 0) { topBuilding.rightWidth++; break; } // If the new building is greater in height, push it onto the // stack. The number of buildings to the immediate left of it // that are taller is equal to the number of buildings that // were popped before this point, its popCount. Set its // leftWidth equal to its popCount. Increment the rightWidths // count of the top building as its largest rectangle goes // through the new building. if (heightDiff > 0) { nextBuilding.leftWidth = popCount; topBuilding.rightWidth++; stack.push(nextBuilding); break; } // If the new building is less in height, update the maximum area // with regards to the element at the top of the stack. long topArea = topBuilding.getArea(); if (topArea > maxArea){ maxArea = topArea; } // Then discard the top element and repeat the comparison // procedure with the current next building. stack.pop(); popCount++; } } // If all buildings have been processed and the stack is not yet empty, // finish the remaining subproblems by updating the maximum area // with regards to the building at the top of the stack. while (! stack.empty()){ Building topBuilding = stack.pop(); long topArea = topBuilding.getArea(); if (topArea > maxArea){ maxArea = topArea; } } return maxArea; } class Building { long height; int leftWidth; int rightWidth; Building(long y){ this.height = y; leftWidth = 0; rightWidth = 0; } long getArea(){ return height * (1 + leftWidth + rightWidth); } } ellemeno, Nice solution/explanation. However, maxArea should be initialized to 0. @logimech Right. :) Thanks. Show More Responses ellemeno: The program has bug. We need to store the building's x cordinate. And when the nextbuilding is shorter than the top one, we need to update each popped building's rightwidth as topbuilding.x - nextbuilding.x Isnt this the convex hull problem? The O(n) algorithm does not work. I have another solution for it, however. Suppose we have the array of heights a of length n. We are looking for the smallest building index (let's say x and divide the problem in 2: the left part ( between 0 and i - 1) and the right part (between i + 1 and n - 1). Then we compute the area that can be build using the building indexed with i: a[i] * (n - 1 - 0 + 1) = n * a[i]. We compare this area with the ones obtained from the left and from the right part and return the result. Therefore, the complexity will be: N * time to find the index of the smallest building in a range - which is RMQ problem that can be solved in O(logn) and O(n) preporcessing time (and O(N) space). Therefore, the complexity is O( N log N). It works for 3 6 5 6 2 4: the solution is 3 * 5 = 15. The problem is known as the biggest rectangle below a histogram. An old question with my answer. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace SkylineTest { class Program { static void Main(string[] args) { Point[] pointList = new Point[10]{new Point(0, 1) ,new Point(1,1) ,new Point(1,2) ,new Point(2,1) ,new Point(2,2) ,new Point(2,0) ,new Point(4,0) ,new Point(4,6) ,new Point(5,6) ,new Point(5,0)}; Skyline sl = new Skyline(pointList); Point maxPoint = sl.CalculateMaxRanctangle(); Console.WriteLine("MaxPoint:" + maxPoint.X + " " + maxPoint.Y); Console.WriteLine("MaxArea:" + sl.MaxArea); Console.ReadLine(); } } public struct Point { private int _x; private int _y; public int X { get { return _x; } } public int Y { get { return _y; } } public Point(int x, int y) { _x = x; _y = y; } } public class Skyline { private Point[] _pointList; private int _maxArea=0; private Point MaxRactanglePoint; public int MaxArea { get { return _maxArea; } } public Skyline(Point[] pointList) { _pointList = pointList; } public Point CalculateMaxRanctangle() { Point maxPoint = new Point(0, 0); for (int index = 0; index 2) { for (int i = index - 2; i >= 0; i -= 2) { if (_pointList[i].Y >= _pointList[index].Y) areaForPoint += (_pointList[i+2].X - _pointList[i].X) * _pointList[index].Y; else break; } } if(index= _pointList[index].Y) areaForPoint += (_pointList[i].X - _pointList[i-2].X) * _pointList[index].Y; else break; } if (areaForPoint > _maxArea) { _maxArea = areaForPoint; maxPoint = _pointList[index]; } index += 2; } } return maxPoint; } } } i dont know if i understand the assignement correctly, but shouldnt ne sufficient to iterate all coorfinates and find min x, min y, max x, max and then calculate the area given by this rectangle? Hi Guys, there is O(N) solution using STACK. http://www.geeksforgeeks.org/largest-rectangle-under-histogram/ Psuedocode //Iterate through points one time where a point further east is greater than a point farther west, a point higher up is greater than a point lower down. //if x greatestX, greatestX = x //if y greatestY, greatestY = y //Equate (greatestX - smallestX) by (greatestY - smallestY) For some reason that left out like half of my psuedocode |

### Software Engineer at Cerner was asked...

The only unexpected question was to design a employee database because it wasnt in the previous thread :) but it was easy 18 Answersplease reply... Are they expect coding or UML diagrams for chess game ? No .. No uml or coding .. Just the high level design sorry, i don't understand.could you please explain it,programming design means UML.am i right.? what is high level design here.. Thank you in advance. Show More Responses They will just ask you that what classes will u use .. So just list the classes and if u wil make any abstract class or interface .. That's all they expect no uml or class diagram is needed Thanks, Hi, Could you provide some test cases for the following question? I am not very familiar with writing test cases. I would greatly appericate your help. Unit test a function which uses the following parameters : reversestring(originalString, stringToBeReversed, stringReverseTo,max) (Come up with as many test cases as possible) All you need to do is pass some actual values in the arguments, you can write as many combination of values as you want, for ex: in the function reversestring(originalString, stringToBeReversed, stringReverseTo,max) you can write test case as reversestring('abcde', 'abc', 'opr', 2) try to put some negative test cases too, ex: reversestring(1234566,33,4,2) reversestring('','','', ) Hi, Can you please provide some answers to this question: How do you find a bug and what steps did you take to correct it? Can we just say we will create a bug report, debug the code etc... or are they looking for any specific answer? Please do reply Thanks in advance Design an unbalanced BST using the word "CERNER" , duplicates allowed. - Can you please give me the right way of constructing this? Thank you. C \ E \ R / N / \ E R I was unable to find preorder traversal for the above one :(, however the following one gives proper solution for all pre, in, post order traversals. What do you suggest? C \ E \ R / \ N R / E Thank you very much. You are right I think the last solution you gave works fine for the traversals. Hi, Can you please provide some answers to this question: How do you find a bug and what steps did you take to correct it? Can we just say we will create a bug report, debug the code etc... or are they looking for any specific answer? Please do reply Thanks in advance Show More Responses Hi I have Question on Salary.I know it is not appropriate to ask this.But,If Possible anybody please answer. How much they offered to 1+ years experience.?(between 70k-75K or 75k-80K). Thanks in advance. are you experienced or did you apply for entry level positions ? https://dev.mysql.com/doc/employee/en/sakila-structure.html Can you explain unit test case for Stringreverse To which positions do we need to apply for software developer? |

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

Given a list of n objects, write a function that outputs the minimum set of numbers that sum to at least K. FOLLOW UP: can you beat O(n ln n)? 15 AnswersQuestion has some ambiguity. If "minimum set of numbers" means the minimum sum of numbers = K. This can be solved with a type of a greedy algorithm. The maximum(..) function shall take into account that when K is negative maximum should return the distance of the number to 0.(abs() of the element). As this boils down to getting maximum element of an array in order, it can easily be implemented via binary heap. The complexity becomes O(n.logn) and not sure if it can be beated. Partition the array by the target value. if any element is larger than target value, return it. else target value -= largest element and do the partition again. 1) Sort the array in increasing order 2) Start scanning backward from largest to smallest elements in array until we have enough elements that sum to given target sum. ArrayList FindMinSet(int sum, int numbers[]) { int numbers[] = Sort(numbers); // Sort in increasing order of numbers -- O(nlogn) ArrayList minSet = new ArrayList(); for(int i=numbers.length-1; i>=0; i--) { sum = sum - numbers[i]; minSet.add( new Integer(numbers[i]) ); if(sum <=0) { return minSet; } } } Show More Responses @Anonymous: that didn't beat O(n lg n) Construct a max heap out of this list. Keep taking out the max and decrease K accordingly till K becomes less than or equal to zero. Making a heap out of the array is O(n). on average, it could be better than O(logn). I believe the closest answer to the correct one is birdy's. You're supposed to partition around a random element x, and get the sum S of all elements larger than x. if S is larger than K, you recurse on the subarray of the elements that are larger than x. if S is smaller than K, you recurse for S-K on the subarray of elements that are smaller than x. The worst case running time of this algorithm can be O(n^2), but it will be O(n) on the average. The probabilistic proof of that statement is not very easy, but the intuitive idea is that most of the time, the partition will be more balanced than a (1,10) ratio, and this enough to make the subarray sizes bounded by a geometric sequence of ratio less than one, which will guarantee you a linear time algorithm. It is also possible to get a worst case linear time algorithm by adapting the algorithm given here: http://en.wikipedia.org/wiki/Selection_algorithm to the weighted case, but this is really overkill and,in practice, the resulting algorithm will be slower than the randomized algorithm I described. Traverse the array, use minHeap to store the values that > 0 and sum >= K if(newNode.value > 0) { if (heap.sum = K && newNode > heap.root.value) heap.root = newNode; //replace root with newNode; while(heap.sum - heap.root.value >= K) heap.remove(root); } Time = nlogm < nlogn - where m is number is Nodes in heap ~ number of numbers needed to sum to K Sorting + scanning is trivial and O(nlogn) If the input data is integer is also trivial, just use radix sort. O(n), so let's assume the input is float numbers If there is an element a[i] s.t. a[i] > t, where t is the target value, then it's also trivial, so let's assume a[i] =0 for all i If the sum of a[i] is still smaller than or equal to t, then the answer is N/A or the whole set, and this can be checked in O(n), so let's assume the sum of a[i] is larger than t. With the above assumption, let's try to do it in a way similar to qsort: select a[0] as pivot, partition the array using a[0], smaller element appears to the left, and larger to the right. do a sum of all the values to the right of the pivot, say it's s', if s's, answer is found; if still s's, we can focus on the subarray defined as the right of the pivot. Repeat the procedure until the answer is found. I believe there is a math proof similar to the analysis of why median selection can be done in O(nlogn) in average cases, to show this algorithm to run in O(n) in average cases. Any ideas? Please ignore the previous post, cuz I made too many silly mistakes. Sorting + scanning is trivial and O(nlogn) If the input data is integer is also trivial, just use radix sort. O(n), so let's assume the input is float numbers If there is an element a[i] s.t. a[i] > t, where t is the target value, then it's also trivial, so let's assume a[i] =0 for all i If the sum of a[i] is still smaller than or equal to t, then the answer is N/A or the whole set, and this can be checked in O(n), so let's assume the sum of a[i] is larger than t. With the above assumption, let's try to do it in a way similar to qsort: select a[0] as pivot, partition the array using a[0], smaller elements move to the left, and larger to the right. do a sum of all the values to the right of the pivot, say it's s', if s's, answer is found; if still s'+pivots, we can focus on the subarray defined as the right of the pivot. Repeat the procedure on the slimmed-down subarray until the answer is found. I believe there is a math proof similar to the analysis of why median selection can be done in O(n) in average cases, to show this algorithm to run in O(n) in average cases. Any ideas? I'm writing the actual code for this. #include #include #include using namespace std; void recPrintTightestSum(double* a, int from, int to, double s) { if (from >= to) { if (from == to) cout s) recPrintTightestSum(a, right+1, to, s); else if (sumRight == s) for (int i = right+1; i = s) cout = s) { cout 0) { sumA += a[i]; offset[i] = 1; }else offset[i] = 0; } if (sumA > s; while (true) { cin >> input[inputL]; if (998 <= input[inputL]) break; inputL++; } printTightestSum(input, inputL, s); return 0; } /* 99 4 3 5 7 21 43 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 999 -2 1 -3 4 -1 2 1 -5 4 999 1 -41 -51 -5 -2 999 -1 0 999 10 0 2 -3 5 5 -5 999 99 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 4 3 5 7 2 4 5 2 5 -8 -1 0 0 0 0 0 0 -3 5 -4 3.5 6.5 7.6 999 */ //java implementation below public int minSum(List vals, int sum, int runningValue){ if(vals.size() == 0) return -1; List less = new ArrayList(); List more = new ArrayList(); int pivot = vals.get(0); for(int i : vals.subList(1, vals.size())){ if(i > pivot) more.add(i); else less.add(i); } int moreListSum = 0; for(int i : more){ moreListSum += i; } if(moreListSum = sum) return more.size() + runningValue + 1; else if(moreListSum + pivot < sum){ return minSum(less, sum - (moreListSum + pivot), runningValue + more.size() + 1); } else { return minSum(more, sum, runningValue); } } import random def minimum_numbers(lst, l, r, k): '''returns list of minimum amount of numbers which sum is greater than k''' if l + 1 == r: return [lst[l]] elif l == r: return [] x = random.randrange(l, r) val = lst[x] lsum = 0 rsum = 0 b = l e = r while b val: e -= 1 t = lst[e] lst[e] = lst[b] lst[b] = t rsum += lst[e] else: lsum += lst[b] b += 1 if lsum + rsum = k: return minimum_numbers(lst, e, r, k) else: return minimum_numbers(lst, l, e, k - rsum) + lst[e:r] #include #include #include using namespace std; int partition(int A[], int begin, int end, int &left_sum, int &right_sum) { int x = rand()%(end-begin+1); x = x + begin; int tmp = A[x]; A[x] = A[end]; A[end] = tmp; int lsum = 0, rsum = 0; int i = begin; for(int j=begin; j= k) { for(int i=begin; i= k) begin = pos + 1; else if(right_sum + A[pos] >= k) { for(int i=pos; i 0) { end = pos - 1; } else if(pos > k; if(get_K(A, 7, k)) { cout << "Found !" << endl; } else cout << "No answer!" << endl; } } Show More Responses You could solve it in deterministic linear time using a combination of linear-time selection (median-of-medians solution) and binary search. At each iteration, find the median of the array being considered and partition around it. If the greater half sums to K, return it. If it sums to less than K, store all elements of the greater half and recurse on the lower half. Otherwise, recurse on the greater half. Once you get down to considering a small enough set, just sort and finish off the problem. We have to perform linear time selection and linear partition on n + 1/2n + 1/4n + 1/8n +... elements, which sums to 2n so O(n) running time. Iterate the list and get the average of the list, suppose the average number is A, then we can assume that the set's number should less than K/A = n. Iterate the list again and keep a max heap for n+1 elements I think this can beat O(n ln n) |

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

Implement a function rotateArray(vector<int> arr, int r) which rotates the array by r places. Eg 1 2 3 4 5 on being rotated by 2 gives 4 5 1 2 3. 18 AnswersI started with the trivial O(n) time and O(n) space algo. The best algo can do this in O(1) space. def rotate(vec, r) : if r <= 0 : return vec L = len(vec) r %= L (cnt, beg) = (0, 0) while cnt < L : cur = beg tmp = vec[cur] while True : next = (cur + r) % L tmp1 = vec[next] vec[next] = tmp tmp = tmp1 cur = next cnt += 1 if cur == beg : break beg += 1 return vec private static Vector rotateArray(Vector items, int r){ if(items==null){ return items; } if(r==items.size()){ return items; } LinkedList list=new LinkedList(items); for(int i=1; i (list)); } Show More Responses public static void rotateArray(int[] in, int r){ int i =0,j = in.length -1; reverseArr(in, i, j); reverseArr(in, 0, r -1); reverseArr(in, r, j); } public static void reverseArr(int[] in, int si, int ei){ int i =si,j = ei; while (i <= j){ int tmp = in[i]; in[i] = in[j]; in[j] = tmp; i++; j--; } } Algorithm mentioned by Kruk is incorrect. Here is an example: Given array:{1,2,3,4,5,6,7,8,9,10} and you want to rotate 7 times. The answer is {8,9,10,1,2,3,4,5,6,7}, but the above algorithm produces {4,5,6,7,8,9,10,1,2,3}. Sorry, I misunderstood the question as left rotation, instead of right rotation. http://ideone.com/yxWRl O(n) runtime, O(r) extra space http://ideone.com/Gv6Lo A very nice O(n) solution with O(n) space Using STL magic.. with O(r) extra space. void rotate(vector &vec, int r) { if(vec.size() tmp(vec.end()-r, vec.end()); vec.erase(vec.end()-r, vec.end()); vec.insert(vec.begin(), tmp.begin(), tmp.end()); } void rotate_inplace(vint &num, int k) { //inplace rotation of array o(n) time, o(1) space int size=num.size(); if(size==0) return; //k=-k; //if you want right rotate k=k%size; k=k<0?size+k:k; if(k==0) return; int pos=0, start=0; int initial,buffer; const int offset=size-k; for(int i=0;i the solution above is a generalized version of swap; however since the jump size was constant (=k), once we return back to starting index (after the swap circle) we can just increment the start by 1 to get new start, (i.e, in all elements were not covered already) however for a general swap you cannot do so import os import sys def unsort(array): s,f=0,float('inf') while(s%d,"%(s,f), #s has looped back to start print while s O(n) time with O(1) space #include using namespace std; int circle_number(int n, int k) { int c = 1; int sum = k; while(sum % n != 0) { sum += k; c += 1; } return n/c; } void rotate_arr(int arr[], int n, int k) { k = k % n; if(k == 0) return; int circle_num = circle_number(n, k); int num = n / circle_num ; int tmp, prev, start; for(int i=0; i< circle_num; i++) { start = i; tmp = arr[start]; for(int j=0; j O(n) time with O(1) space! Basically, popout the last element and insert it to the beginning! Do this r times! void rotate(vector arr, int r) { while (r--) { int temp = vector.pop_back(); vector.insert(0, temp); } } Show More Responses http://baibingz.wordpress.com/2012/10/26/rotate-array/ O(n) Time O(1) Space In-place, O(n) time, O(1) space. slightly quicker than the version using replace() as it is iterating the array twice while this version does just once. void rotate_array(vector& s, int r) { if(r == 0 || s.empty() || s.size() < 2) { return; } r %= s.size(); if(r == 0) { return; } int round = 0; int loopCnt = s.size(); while(loopCnt) { int cur_idx = round; int cur_val = s[cur_idx]; while(1) { int to = (cur_idx+r) % s.size(); int tmp = s[to]; s[to] = cur_val; cur_idx = to; cur_val = tmp; loopCnt--; if(to == round) break; } round++; } } I just took an array instead of a vector.. public static void rotateArrayByNPlaces(int oArray[], int places) { int length = oArray.length, destinationIndex = 0, startingIndex = 0, boundaryIndex = 0; int nArray[] = new int[length]; destinationIndex = places % length; boundaryIndex = destinationIndex; if(destinationIndex == 0) { printArray(oArray); } else { do { nArray[destinationIndex] = oArray[startingIndex++]; destinationIndex = (destinationIndex + 1) % length; } while(destinationIndex != boundaryIndex); printArray(nArray); } } I wonder if this would work: http://ideone.com/i2QMBw Perl version which works - http://ideone.com/UKxbqA |

### Software Engineer at USAA was asked...

A train leaves San Antonio for Huston at 60mph. Another train leaves Huston for San Antonio at 80mph. Huston and San Antonio are 300 miles apart. If a bird leaves San Antonio at 100mph, and turnes around and flies back once it reaches the Huston train, and continues to fly between the two, how far will it have flown when they collide. 16 AnswersFind out how long it will take the two trains to collide, then multiply that number by the birds flying speed. There are several scenarios to consider. Scenario 1 - Since trains rarely collide, the bird will hypothetically continue to fly forever, thus the answer is infinity miles. However, this is obviously not a rational outcome since the bird will tire, need to stop for nourishment, and require rest. In addition, one would need to know more about the bird such as the average lifespan and the realistic length of time the bird can fly at a sustained speed of 100 miles per hour. Of course, the term "bird" is sometimes used colloquially when referring to an airplane. Scenario 2 - Assuming both trains leave at the exact same moment, then the distance between them will be reduced by 140 miles per hour, which is the combined speeds of both trains. Therefore, it will take (300/140) = 2.14 hours before the two trains collide thus the bird would have flow (2.14*100) = 214 miles. However, this assumes both trains are traveling at a constant speed on a single track void of any modern collision avoidance systems, and that neither train makes any scheduled stops along the way, which again is not a real world scenario. Of course, the only bird capable of flying 100 mph sustained for more than 2 hours is an airplane. Scenario 3 - Assuming I am interviewing for an upper level management position and solving the problem will significantly impact the company's bottom-line and thus impact my bonus, I would hire a management consulting company specializing in mathematic modeling to solve the problem and offer suggestions to optimize the collision such that it would conserve as much energy as possible for both trains and the bird. Where is Huston, Texas? I didn't see it on the map. The only city that I see approx 300 miles of San Antonio is Houston. So since there is not Huston then there is no train and hence no collision. The bird flies till it dies. Show More Responses If the bird is flying between both trains when they collide, it won't have flown at all anymore since it would be dead (squashed between both trains). They won't collide; they're on separate tracks to stop this happening. Too far... that bird needs better navigational skills. Try a GPS. Actually, it needs some math and some imagination only. First of all, the collision point will be about 128.6 miles from San Antonio and the collision should happen after 128.6 minutes. Part 1: The bird will start travelling from San Antonio heading to Huoston and will meet the Huoston train after 2 Hrs and 40 Minutes (Relative speed between both is 180 mph) at a point which is 167 miles away from San Antonio and 133 miles far from Huoston. At this moment, the San Antonio Train will be 100 miles from San Antonio and 67 miles away from both the bird and Huoston train. The bird has flown 167 miles Part 2: The bird will fly back towards San Antonio train again at a relative speed between them of 160 mph and will meet the train after another 25 minutes at a point which is 125 miles from San Antonio. At this moment, the Houston train will be 133.5 miles from San Antonio and 8.5 miles from both the San Antonio Train and the bird. Part 3: The bird will fly again towards Huoston Train, and will reach it after about 3 minutes at a point which is almost the collission point. Previous "rough" calculations tells us that the bird has travelled a distance of almost 218 - 220 miles. I hope this is the right answer though. Train 1: x = 0, v = 60 mph Train 2: x = 300, v = -80 mph Bird: x = 0, v = 100mph 300 + (-80*t) = 0 + (100*t) -> t = 1.667 (60 * 1.667) = 100 (100 * 1.667) = 166.67 Train 1: x = 100, v = 60 mph Train 2: x = 167.7, v = -80 mph Bird: x = 167.7, v = -100mph 100 + (60*t) = 167.7 + (-80*t) -> t = .476 h (-100 * .476 ) = 47.6 Bird, total distance is 214.3 miles, or a displacement of 119.0 miles from its starting location. When who collides? The bird and the train or the trains? If the bird is literally "flying between the trains" until they collide.. Then, the answer is "not far enough to get out of the way before being squashed." 100*(300/(60+80)) = 1500/7 miles. It takes 300/(60+80) hours for the trains to collide, and the bird will travel at 100 mph during this time. The fastest flier in the world is the Peregrine Falcon. It can reach a "flat" speed of 124 mph (dives have been clocked at 168), but I do not believe any known bird can maintain 100mph when flying on an even plane for more then a few miles. So the birds quits, there is an opening. Whats It Pay? The distance is infinite as there is no relaxation time or turning time so such a thing is not possible practically. For an instance imagine the distance traveled by the bird when the distance between the two trains is just 10m and so on till 8 9 7 till the distance is just tending to 0. Show More Responses Here’s how to think about it so you can do it in your head: The 2 trains are closing in on each other at 60 mph + 80 mph = 140 mph. The have to cover 300 miles before they collide. They will collide in 300miles/140 mi/hr = 30/14 = 15/7 hours = 2-1/7 hours (a little over 2 hours). The bird is flying at 100 mph for 15/7 hours. The bird flies 100 mi/hr x 15/7 hours = 1500/7 miles. That is a little over 214 miles. Ballpark Reality Check: Trains crash in a little over 2 hours so the bird flies at 100 mph for a little over 2 hours which is a little over 200 miles. Yep, sounds right. Nothing else matters. Not how far the trains go, not how far the bird goes, not what direction the bird is flying, etc. Answer the question that was asked and don’t answer a question that wasn’t asked. The question is, “How far does the bird travel?” The answer is “Exactly 1500/7 miles which is a little over 214 miles.” I would first want to play upon the interviewer's geek tendencies, and ask, "what do you mean, African or European swallow"? and I'm assuming you mean an unladen one....http://webcache.googleusercontent.com/search?q=cache:http://style.org/unladenswallow/&gws_rd=cr&ei=GHpWVqKhJcLJmwXxyr3gDg I looked at this a bit differently than the answers below. Because the bird remains between the two trains until it crashes it has one of two options. Either it (A) flies back and forth between the trains at 100 mph or BB) maintains the same speed as the train it met up with. For A, the answer is 214.3 as it would maintain a constant speed of 100 mph and the trains would take 128.57 minutes to meet. I have yet to find a bird that can start and stop while maintaining a flight speed of 100 mph but this is a hypothetical as it is only 200 miles between the two. For B, the answer is 204.76 as the bird flew the 166.67 miles to the Houston train (H) and then maintains that trains speed until impact. In that scenario the two trains would have traveled 233.33 miles at the time the bird met the H train leaving 66.67 miles to go. with the H train traveling 80 mph they would meet in 28.57 minutes at which time the H train and the bird would have traveled 38.09 of those miles. 38.09+166.67=204.76. |

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

Given the daily values of a stock, find how you can lose the most with one buy-sell trading. 14 AnswersOr in other words, find the two points where the difference between the two are the largest in the function. "find the two points where the difference between the two are the largest in the function" - this is incorrect. You can not go back in time when it comes to stock trading :) e.g. {2,1,10} has a maximum loss of 1-2 = -1, but has a maximum difference of -9. [11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps Maintain two variables, min and max. Whenever cur value of array is less than max then upadate min do a diff between min and max and update curloss if it is less than curloss. update max variable if value is greater than or equal to max 11 11 0 11 20 0 11 24 0 11 51 0 10 51 -41 10 99 -41 15 99 -84 1 99 -98 1 199 -198 75 199 -198 Show More Responses Slight error in my previous post given above: [11,20,24,51,10,99,15,1,199,75] list of stock prices in increasing order of time stamps Maintain two variables, min and max. Whenever cur value of array is less than max then upadate min do a diff between min and max and update curloss if it is less than curloss. update max variable if value is greater than or equal to max, dont update curloss variable here. 11 11 0 11 20 0 11 24 0 11 51 0 10 51 -41 10 99 -41 15 99 -84 1 99 -98 1 199 -98 75 199 -124 package asaf; public class MaxLose { public static void main(String[] args) { int[] ticks = {5,7,4,2,77,8,9}; int[] worseSell = new int[ticks.length]; worseSell[worseSell.length-1] = ticks[ticks.length-1]; for (int index=ticks.length-2; index>=0; index--) { worseSell[index] = Math.min(worseSell[index+1], ticks[index]); } int lose = 0; for (int index = 0; index < ticks.length; index++) { lose = Math.max(lose, ticks[index] - worseSell[index]); } System.out.println(lose); } } double WorstSell(double *values, int n) { double maxBuySeenSoFar = 0.0; double minprofit = 0.0; // in-order lose most. we need to buy high and sell low. we can only sell after buying. for (int i = 0; i maxBuySeenSoFar) { maxBuySeenSoFar = values[i]; } else if (maxBuySeenSoFar - values[i] < minprofit) { minprofit = maxBuySeenSoFar - values[i]; } } return minprofit; } Recursive way to solve this in n logn public static int[] findMaxLost(int[] prices) { return rFindMaxLost(prices, 0, prices.length-1); } private static int[] rFindMaxLost(int[] prices, int p, int r) { if (p == r) { int[] ml_pos = new int[2]; ml_pos[0] = p; ml_pos[1] = p; return ml_pos; } int q = (p + r) / 2; int[] l_ml_pos = rFindMaxLost(prices, p, q); int[] r_ml_pos = rFindMaxLost(prices, q + 1, r); /*find the max_min cross the center point q*/ int[] m_ml_pos = new int[2]; m_ml_pos[0] = findMax(prices, p, q); m_ml_pos[1] = findMin(prices, q + 1, r); if ((l_ml_pos[0] - l_ml_pos[1]) >= (m_ml_pos[0] - m_ml_pos[1]) && (l_ml_pos[0] - l_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) { return l_ml_pos; } else if ((m_ml_pos[0] - m_ml_pos[1]) >= (r_ml_pos[0] - r_ml_pos[1])) { return m_ml_pos; } else { return r_ml_pos; } } private static int findMax(int[] prices, int p, int q) { int pos = 0; for (int i = p + 1; i prices[i]) { pos = i; } } return pos; } reader writer pointer soution. O(n) public class MaxLose { public static void main(String[] args) { MaxLose m = new MaxLose(); int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3}; int max = m.maxLose(a); System.out.println(max); } private int maxLose(int[] a) { int b = 0, max = 0; for (int s = 1; s max ? a[b] - a[s] : max; } return max; } } Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left. Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its left. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs. Most answers here are in correct. Here is the algorithm. You first identify all buy canditaes, and all sell candidates. A buy canditate is: a point which is bigger than everything on its left and also bigger than the next point on its right. A sell candiate is a point that is smaller than everything on its right and also smaller than the point on its left. Then you match buy canditates to sell candidates, for every buy candidate the matching sell canditate is the first sell candidate on its right. (multiple buy candidates can match multiple sell) After they are matched the pair with maximum difference will give you the max loss. O(n) needed to find candidates, les than O(n) neded to match pairs. public static int minPoint(List list){ if (!list.isEmpty()){ int minPoint = list.get(0); return Math.min(minPoint - findMax(list),minPoint(list.subList(1, list.size()-1))); } return 0; } private static int findMax(List list) { int max = list.get(0); for (int i=1; i max){ max = list.get(i); } } return max; } public static void main(String[] args) { int[] a = new int[]{10, 3, 20, 10, 12, 5, 20, 7, 5, 3}; List list = new ArrayList(); for (int i=0; i //Given the daily values of a stock, find how you can lose the most with one buy-sell trading. //A[] -> {5, 8, 6, 3, 9, 3, 2, 7} //B[] -> {0, 3,-2,-3,6,-6,-1, 5} ? diff A[i] = A[i] - A[i - 1] //C[] -> {0, 0,-2,-5,0,-6,-7,-2} -> min(0, B[i - 1] + B[i]) public int[] looseMost(int[] A) { int minRes = 0; int sIdx = 0; int eIdx = 0; int currRes = 0; int csIdx = sIdx; int prevB = 0; int currB; int currC = 0; for (int i = 1; i < A.length; i++) { currB = A[i] - A[i - 1]; currC = Math.min(0, currB + prevB); if (currC < minRes) { sIdx = csIdx; eIdx = i; } else if (currC == 0) csIdx = i; prevB = currB; } return new int[] {sIdx, eIdx}; } If I understand the question correctly, the task is to find the minimum consecutive sum of price differences, which is equivalent to a maximum consecutive sum algorithm (just google it). This can be solved in O(n) using a dynamic programming approach. Show More Responses The solution is here: http://www.geeksforgeeks.org/archives/6463 |

### QA Automation Engineer at BitTorrent was asked...

A dwarf-killing giant lines up 10 dwarfs from shortest to tallest. Each dwarf can see all the shortest dwarfs in front of him, but cannot see the dwarfs behind himself. The giant randomly puts a white or black hat on each dwarf. No dwarf can see their own hat. The giant tells all the dwarfs that he will ask each dwarf, starting with the tallest, for the color of his hat. If the dwarf answers incorrectly, the giant will kill the dwarf. Each dwarf can hear the previous answers, but cannot hear when a dwarf is killed. What strategy should be used to kill the fewest dwarfs, and what is the minimum number of dwarfs that can be saved with this strategy? 21 AnswersThere are 2 different strategies, each dependent on whether there are an even or odd number of white and black hats in play. The minimum number of dwarfs that can be saved with the correct strategy is 9. There is only one strategy, does not matter how many white or black hats they are. They are always 9 dwarfs that could be saved. You just have to know about XOR. Well... In my opinion all can be saved! The tallest dwarf can see 9 hats in front of him ( 4 white and 5 black hats or the other way around). Then he knows the color of his hat because there has to be 5black and 5 white hats. The next dwarf by the size just has to believe to the tallest dwarf that he is right-(and he is) In addition ,he can see 8 hats in front of him and when he adds the color of the tallest dwarf he knows which color he has. Again,the 3rd one in a row knows about 2 colors before and can see 7 colors in front of him.And when he adds 2 colors he already had heard of -he knows total number of 9 hats as well.So he just has to see which color is less presented and that is the color of his hat. And so on until the last dwarf...All saved Show More Responses the question does not mention that there will be equal number of white and black hats ! Since they do not know, how many black or white hats there are, the following strategy will save min 5 dwarfs: The first dwarf asked names the color of the hat of the 2. dwarf. He has a 50% chance that that's correct. Anyway, the second dwarf then knows, the color of his hat and names it correctly. the 3. dwarf again names the color of the hat of the 4th dwarf and has a 50% chance to survive, while the 4th dwarf can name the correct color of his hat. a.s.o. => all dwarfs with an even number will survive and all the others have a 50% chance Don't over-think it. Each dwarf simply has to state the color of the hat worn by the dwarf directly in front of him. The tallest would have to sacrifice himself in order to save the other 9. Easy. The tallest is the only one that cannot be saved so instead of trying to guess his color, he yells out a sequence of letters starting from the shortest like BWBBBWWBB. Next :) Your going to definitly get 9 because when the dwarves collude the tallest tells the next tallest his hat color and so on down the line. Now you have a 50/50 chance that the tallest will get his color correct and live so you have 9 with a 50% chance of 10 Each dwarf can state the color of the hat worn by the dwarf in front of him, but the thing is, that color may not be the color of his own hat.So he may be killed by the giant.In that case, as mentioned above all odds should tell the color of next so that all even number will be alive and they have 50% chance of surviving. Think broadband communication. Exploit the capabilities of the communications medium. A minimum of nine dwarves can be saved based on the information provided in the original post I viewed. The strategy is for each dwarf to employ the expected language to communicate the color of their own hat to the giant, while simultaneously employing a vocal pitch protocol to indicate the color of the hat of the dwarf in front of him, high pitch for white and low pitch for black. The original post, indicates the dwarves may collude prior to the distribution of hats, so there is opportunity to negotiate such a simple broadband communication protocol. The tallest dwarf only has a 50/50 chance since the number of black and white hats in play is not known (rhetorical question, what are the odds the tallest dwarf's hat is black if he turns to find that all nine hats in front of him are white? I don't know, but odds are high that the giant is a sadistic bloke). The original post I viewed is here. http://www.businessinsider.com/toughest-job-interview-questions-2013-7#a-dwarf-killing-giant-lines-up-10-dwarfs-from-shortest-to-tallest-each-dwarf-can-see-all-the-shortest-dwarfs-in-front-of-him-but-cannot-see-the-dwarfs-behind-himself-the-giant-randomly-puts-a-white-or-black-hat-on-each-dwarf-no-dwarf-can-see-their-own-hat-the-giant-tells-all-the-dwarfs-that-he-will-ask-each-dwarf-starting-with-the-tallest-for-the-color-of-his-hat-if-the-dwarf-answers-incorrectly-the-giant-will-kill-the-dwarf-each-dwarf-can-hear-the-previous-answers-but-cannot-hear-when-a-dwarf-is-killed-the-dwarves-are-given-an-opportunity-to-collude-before-the-hats-are-distributed-what-strategy-should-be-used-to-kill-the-fewest-dwarfs-and-what-is-the-minimum-number-of-dwarfs-that-can-be-saved-with-this-strategy-11 So reading the answers provided they all have some assumptions e.g. that there are as much white hats as there are black hats. I think that Christian's comment on aug 13-2013 was very close but I'm thinking about communication integrity confirmation techniques. One of them is using a parity bit to confirm the message was correct. This could be applied right here to save at least 9 with a 50/50 chance of saving the 10th (and tallest dwarf). I will explain it but for ease of explanation I will use binary 1 and 0 for black and white. Number 1 being black hat and number 0 being white hat. Let's say we got a (random) hat sequence of 0001011101 with the tallest dwarf on the right and the shortest on the left. While colluding prior to the distribution of hats the dwarfs agree upon even or uneven parity. This means the total amount of 1's (black hats) must be even or uneven including the parity bit. In this case the 10th dwarf will count as parity bit. So if we'll take an even parity, the number of 1's must be an even number in total. When the questioning starts the tallest dwarf will see the hats in front of him being 000101110. The tallest dwarf counts four 1's (black hats) so to make the parity even he has to say 0 (white hat). He will get killed but the dwarfs in front of him will know the parity bit is 0 so the 2nd tallest dwarf will see the hats in front of him as 00010111. He will also count 4 and knowing that the dwarf behind him said 0 he'll know that the total amount of 1's is an even number thus concluding he has a 0 (white hat) and will state he has a white hat. Same goes for the rest of the dwarfs and so 9 will be saved. The 10th would've been saved it the dwarfs agreed on an uneven parity. That's why there's a 50/50 chance the 10th will be saved. I'm pretty confident this is the answer but if you want to understand it better (maybe my explanation is a bit vague) go search for "parity bit" on the internet. @Kristen - you have so underthought it! What if the dwarf behind you says "black" and the dwarf in front of you has a white hat???? @JustJanek- Your solution is close, but not correct. Every dwarf needs to consider the parity of a number composed of all the following dwarfs and all the dwarfs behind. The first dwarf says the parity of the 9-bits number in front of him. Assuming that all the other dwarfs know the trick and they stay alive, each dwarf needs to compare the initial parity with the parity of an 8-bit number composed of the hats in front of him and the hats behind (assuming that the dwarfs behind gave the right answer), if the parity is the same, he knows that he has a white hat, otherwise he has a black hat. Show More Responses You can save 9 dwarves at least. Dwarves agree that the tallest one says he is wearing black hat if he sees odd number of black hats in front of him and he says white hat if he sees even number of black hats in front of him. So, the tallest one has 50-50 chance of survival and other dwarves survive 100%. What is the minimum number of dwarfs that can be saved with this strategy? 9 First of all, let's numerate the dwarfs as N1, N2, N3, etc. with N10 being the tallest. Now, N10 will state the color of N9 as his own answer, "My hat is WHITE". Based on this answer, N9 will state his color with a positive statement if the color of N8 is the same as his, "My hat is WHITE". Based on N8's answer, N8 knows that his color is WHITE, now, he will state his color depending on N7. Let's say N7 is black, so N8 will state, "My hat is NOT BLACK". N7 knows that his color is BLACK, but N6 is white, so he will use a negative statement, "My hat is NOT WHITE" and so on. Full example: N10 = BLACK N9 = WHITE N8 = WHITE N7 = BLACK N6 = WHITE N5 = WHITE N4 = WHITE N3 = BLACK N2 = BLACK N1 = WHITE N10: My hat is WHITE (Dies) N9 = My hat is WHITE N8 = My hat is NOT BLACK N7 = My hat is NOT WHITE N6 = My hat is WHITE N5 = My hat is WHITE N4 = My hat is NOT BLACK N3 = My hat is BLACK N2 = My hat is NOT WHITE N1 = My hat is WHITE N10 will have a 50/50 chances of survival... I'm sorry N10, I couldn't save you :'( What is the minimum number of dwarfs that can be saved with my strategy? - 10 My strategy doesn't make any unmentioned assumptions (such as equal number of white and black hats, etc). At the same time, it doesn't add any unmentioned constraints either. The strategy is simple to the point of appearing simplistic. But it meets all the requires. The strategy is: When asked, every dwarf answers "Not RED". This is not an incorrect answer and the Giant, if he were an honourable giant that is :), would have to let the Dwarf live. On a different page altogether, I went through all of the above answers. Not to sound patronizing, but some of the solutions were quite brilliant. I was thinking if I could even come up with that even after years of pondering. But I must admit, all of the above strategies are made by an outsider (ie. us) who is not impacted by this fate. Whereas in the casestudy, the strategy has to be devised by the 10 dwarfs, who face the impact of this strategy. Not to bring in factors such as emotion, the bell curve distribution of intelligence, and other such anal considerations. But I thought it was important to bring in Game Theory, and that all Dwarfs are rational, and that all rational people do not want to harm themselves in any way. In other words, when a strategy's success depends on the conformance to that strategy by ALL the participants, the strategy should also benefit ALL the participants if it is to succeed (or in the least, should not harm even ONE participant). In all the above strategies, since even in the best case scenario the poor Tallest Dwarf has only a 50% chance of living, can we assume that he would conform to this strategy? Each dwarf should pronounce color of hat of dwarf before him. This way they can save atleast 9 dwarf out 10. Well, Once the dwarfs are lined up in descending order. Without any kind of assumption, 9 people can be saved with a 50% probability of the 10th (tallest). Here is how it can be achieved, The strategy is to call the color of odd number of hat. Say for example, the tallest dwarf sees 3 Black and 6 whites, it will call out Black(it may or may not die with 50% chances). Now, the 9th tallest dwarf knows what the 10th dwarf could see and if it (9th) dwarf sees the same odd number of black hats, it will know it has white hat. Next, 8th dwarf knows number of odd (black) caps 9th dwarf could see and if it(8th) finds 1 less black cap, it would know it is wearing a black cap.. and so on. 10- White (calls out Black because it sees odd number of black hats) -dies(assume) 9- White (calls out White because it could still see 3 black hars) 8- Black (sees that there is one less black hat as mentioned by 9th, hence identifies that is wearing black) 7-White (calculates that 8th is wearing black and he could see 2 black, hence identifies itself wearing whiteO( 6-White 5-White 4- Black 3-Black 2-White 1-White Sorry if there is confusion in the way I have answered. all can b saved... They will exchange their hats in Circular form...person10 can see the person1 color of hat and after exchange every dwarf will tell color to their previous ones and person 10 knows the color before changing it from dwarf 1. d10->d9->d8->d7->d6->d5->d4->d3->d2->d1->d10 CIRCULAR EXCHANGE OF HATS First lets look at number of back and white hats...To satisfy the condition "black and white" hata there is minimum one black or white hat present. So its minimum (9 black & 1 white) or (1 white & 9 black) hat being distributed randomly amoung dwarfs. The story says dwarfs are alowed to speak before execution. Lets make a strategy of saying only one colour before execution eg) black or white. Minimum probability of (9 black & 1 white) hats and all the dwarfs say "white"...In this case one is saved but all nine dead. If all dwarfs say "black"..Nine are saved but one is dead. The same applies for the minimum probability of (1 black and 9 white)hats. Thus minimum one dwarf is saved and maximum nine dwarfs can be saved. If each dwarf say the colour of hat in front of him..(dwarf can hear previous answer) then at least five people are saved. |

**81**–

**90**of

**90,615**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Site Reliability Engineer
- Systems Engineer
- Intern
- Software Engineer III
- Software Engineer Intern
- Firmware Engineer
- Trader
- Analyst
- Production Engineer
- Business Development Engineer
- Associate
- Member of Technical Staff