# Software Engineering Interview Questions in San Jose, CA

Software engineering interview questions shared by candidates

## Top Interview Questions

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

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

### 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? 42 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. Smelling the box and writing the correct label on each. :) Just label the boxes correctly. I got this question in a video interview. He verbally read out the question, but either left out the mislabeled part or I not heard it correctly. Without that piece of information, it was impossible to answer the question. Didn't get the job. Open box which is labeled apple+oranges. This box have the wrong label so it cannot have both. Now, -If you pick apple then it is having apples only -if you pick orange it contains orange change the label accordingly |

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

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

Find a sequence with max sum in an array of negative and positive real numbers. 15 AnswersYou construct a sub-sequence within the array where all entries are >= 0.0. Trick question. Given an array a[n], find the subsequence with the greatest sum (without reordering the elements). Let p[i] = the max sum of elements up to and including a[i]. It may or may not include a[i-1], a[i-2], etc. but it must include a[i]. Then p[i+1] = max(a[i+1], p[i] + a[i+1]). The basis is p[0] = a[0]. This recurrence is simple enough to perform in O(n) time and O(1) space. At each step, we need only decide whether to extend the current run or start a new one. float bestsum = sum = a[0]; int i, besti = 0; int len, bestlen = 1; for (i = 1; i bestsum) { bestsum = sum; besti = i; bestlen = len; } } printf("Elements %d through %d sum to %g\n", besti, besti + bestlen - 1, bestsum); function bestSum (array a): size = count of items in array bestsum = a[0] + a[1] //this assumes zero-indexed arrays for (i=0; i bestsum bestsum = sum endfor endfor return bestsum end function Show More Responses lamont, your solution assumes that all elements are positive. No. The (sum < 0) condition accounts for negative elements. My solution does assume that sequences of length 1 are allowed. In the case of ALL negative input, it chooses the single largest element (i.e. the one closest to zero). I tested it against monkeysdown's O(n^2) solution on a variety of mixed positive/negative inputs. They produce the same results except in the case mentioned above. The only error in my solution was the printf. It should read: printf("Elements %d through %d sum to %g\n", besti - bestlen + 1, besti, bestsum); If the minimum sequence length is 2, then it's still possible to solve in O(n). Briefly: float sum = a[0] + a[1]; float bestsum = sum; for (int i = 2; i bestsum) bestsum = sum; } return bestsum; 1) convert the sequence of pos/neg numbers into another sequence of pos/neg numbers where pos/neg numbers are alternating. ie: original sequence 2, -1, 3, 4, -5, -1, 10, 2 into 2, -1, 3+4, -5 + (-1), 10 + 2 ==> 2, -1, 7, -6, 12 with the new sequence, start with first number, as long as next pair of pos/neg number adds together is more than 0, then keep using those numbers in the sub-sequence. The result is O(n) for worst case. It's little more complicated to program. public static double maxSequenceSum(double[] array) { double maxSum = Double.MIN_VALUE; double maxElm = Double.MIN_VALUE; double curSum = 0; for(int i = 0; i maxElm ? array[i] : maxElm; maxSum = curSum > maxSum ? curSum : maxSum; if(curSum + array[i] >= 0) curSum += array[i]; else curSum = 0; } maxSum = maxElm > maxSum ? maxElm : maxSum; return maxSum; } small correction to my previous answer! public static double maxSequenceSum(double[] array) { double maxSum = Double.NEGATIVE_INFINITY; double maxElm = Double.NEGATIVE_INFINITY; double curSum = 0; for(int i = 0; i = 0) { curSum += array[i]; maxSum = curSum > maxSum ? curSum : maxSum; } else { curSum = 0; maxElm = array[i] > maxElm ? array[i] : maxElm; } } maxSum = maxElm > maxSum ? maxElm : maxSum; return maxSum; } I can't believe they would still ask this question - easiest in the book. huh! dynamic programming written all over it! public int computeDP() { int[] V = new int[L.length]; V[0] = L[0]; int max = -1; for(int i = 1 ; i V[i-1] + L[i]) { V[i] = L[i]; } else { V[i] = V[i-1] + L[i]; if(V[i] > max) { max = V[i]; } } } return max; } public void maximumSumSubsequence(int [] array){ int currentMaxSum = 0; int startIndex = 0; int maxSum = 0; int maxStartIndex = 0, maxEndIndex = 0; for (int i = 0; i = maxSum ){ maxSum = currentMaxSum; maxEndIndex = i; maxStartIndex = startIndex; } if ( currentMaxSum < 0 ){ startIndex = i + 1; currentMaxSum = 0; } } System.out.println ("Current max sum " + maxSum ); System.out.println("current start index " + maxStartIndex); System.out.println("End index " + maxEndIndex); } Show More Responses The answer to this problem is the submaxarray algorithm. Find it here: http://en.wikipedia.org/wiki/Maximum_subarray_problem Kadanes algorithm |

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

Phone interview 1 : a) Simulate a Queue with stacks ? b)Find repeated occurrence of character in a string ? Phone interview 2 : a) Given a 2D matrix of numbers find the position of number . Constraints of matrix number always in increasing order left to right and top to bottom . b)When should version control be used . And a tricky discreet math problem ? 13 AnswersWow, a lot of questions: 1. a) Something like this: public class StackBasedQueue { private final Stack store; public StackBasedQueue() { this.store = new Stack(); } public void addToTail(final Integer v) { this.store.push(v); } public Integer popHead() { final Stack temp = new Stack(); while(!this.store.isEmpty()) { final Integer v = this.store.pop(); temp.push(v); } final Integer head = temp.pop(); while(!temp.isEmpty()) { final Integer v = temp.pop(); this.store.push(v); } return head; } public int size() { return this.store.size(); } } 1. b) Something like this: O(n) runtime. public void findRepeats(final String str) { this.map.clear(); final char[] array = str.toCharArray(); for(int i = 0; i < array.length; i++) { final Character c = array[i]; Integer count = this.map.get(c); if(count == null) { this.map.put(c, 1); continue; } count++; this.map.put(c, count); } } For a) further challenge was to simulate a double ended queue , but we ran out of time . you could maintain temp stack as permanent variable and get around doing that. b) Kind of sort of what I wrote I was asked to optimize even further , so I said XOR the array make a note of elements left , remove from original list and you have set of repeated elements . Show More Responses 2a. My idea is to first identify the column that might contain our element, then use binary search to see if our element is in that column. The column that might contain our element is the rightmost column where the first row's element is less than or equal to our target element. int[] matrixSearch(int[][] m, int numRows, int numCols, int target){ int[] firstRow = m[0][]; // not sure this works, can just use for loop to populate int targetCol = findWhichCol(firstRow, 0, numCols-1, target); int targetRow = findWhichRow(m[][targetCol], 0, numRows-1, target); if (targetRow == -1) { return null; // Element not found } return new int[] { targetRow, targetCol}; } int findWhichColumn(int[] a, int low, int hi, int target) { int midIndex = (hi+low)/2; int mid = a[midIndex]; if (mid > target) { return findColumn(a,low,midIndex-1,target); } while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } return midIndex--; } int findWhichRow(int[] a, int low, int hi, int target){ int midIndex = (low+hi)/2; if (midIndex == target) { return midIndex; } if (hi-low == 0) return -1; // Element is not in the matrix if (midIndex < target) { return findWhichRow(a,midIndex+1,hi,target); } return findWhichRow(a,low,midIndex-1,target); } Average: O(log n) Worst: O(n/2) = ~ O(n) This isn't very elegant. How would you do it? @above: I think the run time is log(n)*log(m) Sorry, Log m + log n for 2a you had to describe the properties of the matrix , the diagonal elements have some unique properties which you can recognize . So a good start is initialize the search from of the corners of the non leading diagonal . and yes iterative or divide and conquer from thereon after. @Anonymous That's correct, but this part: while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } makes it O(n) in the worst case. Right? @Interviewee Thank you for the additional explanation. You seem quite qualified. Is there a particular reason you think you weren't given a offer? Did any one interview go poorly? It's a little worrying to look through these interview reports and see so many apparently intelligent people not receive offers. I recently passed my phone interview and am waiting to schedule my on-site. As much as I agree with hiring only the best, I'm finding it difficult to feel optimistic in light of the evidence on this site. Thank you for sharing your experience. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. @Interviewee: Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. I guess they evaluate that over questions in lunch . Answer to 1b in C++11: list findDupes(string s) { list ret; map m; for(char c : s) { m[c]++; if(m[c] == 2) { ret.push_back(c); } } return ret; } |

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

Given an array of numbers, replace each number with the product of all the numbers in the array except the number itself *without* using division. 26 AnswersCreate a tree, where the leaf nodes are the initial values in the array. Given array A[1..n] create array B[1..n]= {1} // all elements =1 ; for (i=1; ij) B[i] *=A[j]; } } A=B; To husb: Your answer will work, but it's O(n^2) solution. Can you do better? Show More Responses Am I missing something? It can't be this easy: given array[0..n] int total = 0; for(int i=0; i<=n; i++) { total += array[i]; } for(int i=0; i<=n; i++) { array[i] = total-array[i]; } Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;) Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this given int array[1...n] int level_size = n/2; while(level_size != 1){//build the tree int new_array[1...level_size]; for ( int i=0; i left = array[i*2]; (and also from child to parent) new_array[i] -> right = array[i*2+1] new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product) } array= new_array; level_size /=2; } for(int i=0; iparent; if( parent->left == node){//find the other node under the parent brother = parent->right; } else{ brother = parent->left; } p *= brother; node = parent; } return p; } btw, it's O(n*logn) It seems to me that for any number array[i], you're looking for PRODUCT(all array[j] where j i]) we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So, leftProduct[0] = array[0]; for j=1; j = 0; j-- rightProduct[j] = rightProduct[j+1]*array[j]; then to get our answer we just overwrite the original array with the desired product array[0] = rightProduct[1]; array[n-1] = leftProduct[n-2]; for j=1; j < n-1; j++ array[j] = leftProduct[j-1] * rightProduct[j+1] and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell. betterStill, I think you have the answer the interviewer wanted.. But... if the array is google sized, don't we have to worry about overflows? it looks to me can be done in order n time given the following relation: product[n] = product[n-1]*array[n-1]/array[n] for example we have array 2 3 4 5 6 product[0]=3*4*5*6 product[1]=2*4*5*6 array[0] = 2; array[1]=3 product[1]=product[0]*array[0]/array[1] Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e. tolal = A[0]*A[1]]*....*A[n-1] now take a loop of array and update element i with A[i] = toal/A[i] Since division is not allowed we have to simulate it. If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g. 2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input void ArrayMult(int *A, int size) { int total= 1; for(int i=0; i< size; ++i) total *= A[i]; for(int i=0; i< size; ++i) { int temp = total; int cnt = 0; while(temp) { temp -=A[i]; cnt++; } A[i] = cnt; } } Speed in O(n) and space is O(1) narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000 so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else.... narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot. You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array. void ArrayMult(int *A, int size) { runningProduct = 1; int *B = new int[size]; for(int i = 0; i = 0; --i) { B[i] *= runningProduct; runningProduct *= A[i]; } for(int i = 0; i < size; ++i) { A[i] = B[i]; } } Show More Responses <strong>Brutefoce Method : </strong> The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time. <strong>Other Solution : </strong> The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be : #include int main() { int n,i=0; scanf("%d",&n); int arr[n]; int brr[n]; int product = 1; for(i=0;i This solution will take O(n) time. The space complexity of this solution will be O(1). If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows." polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4. i.e. {A[0],A[1],A[2],A[3]} Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element. temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]} temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1} And then we will correspondingly multiply temp1 and temp2 and store in B. B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]} The C code to this solution will be : #include int main() { int n,i=0; scanf("%d",&n); int A[n],B[n]; int temp1[n], temp2[n]; for(i=0;i=0;i--) { temp2[i] = product; product *= A[i]; } for(i=0;i The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n). var nums = new[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; var newnums = new int[nums.Length]; for (var i = 0; i index != i).Aggregate((a, b) => a*b); } We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n) Not commentary nt a[N] = {1, 2, 3, 4}; int products_below[N]; int products_above[N]; int p=1; int p1=1; for (int i=0;i def solve(arr,n): product_arr=[1]*n product=1 for i in xrange(n): product_arr[i]*=product product*=arr[i] product=1 for i in xrange(n-1,-1,-1): product_arr[i]*=product product*=arr[i] return product_arr {{{ If A = {a0, a1, a2, ... an} Construct two arrays called left_p left product and right_p right product: left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1} right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1} prod_p[i] = left_p[i] * right_p[i]; }}} O(N) Solution!!! static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i < iArr.Length; i++) { total *= iArr[i]; } for (int i = 0; i < iArr.Length; i++) { iArr[i] = (int)(total * (1 / (double)iArr[i])); } } The answer I post above this uses division. Oops. Here is an answer without division static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Sorry, that last one didn't paste properly static void Calculate(int[] iArr) { int total = 1; for (int i = 0; i 0) { temp -= iArr[i]; newVal++; } iArr[i] = newVal; } } Show More Responses p = 1 g = 1 for x in nums: g = g* x + p p = p + x return g Way easy with a simple negative exponent var arr = [2,3,4,5] var prod = arr.reduce((a,b,arr)=>a*b) arr.map((x)=>Math.pow(x,-1)*prod) console.log(arr) //[60,40,30,24] I don't know if this is correct. But i think it is. I have done it with python def multiply(numbers,n): total = 1 for x in numbers: if x != n: total *= x return total a = [10, 3, 5, 6, 2] n = 4 prod = [] for i in a: re = multiply(a,i) prod.append(re) |

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

You are trying to rob houses on a street. Each house has some +ve amount of cash. Your goal is to rob houses such that you maximize the total robbed amount. The constraint is once you rob a house you cannot rob a house adjascent to that house. 14 AnswersNot that difficult to answer. You need to keep track of houses that are marked robbed. You can do some sort of recursion and at everys step evaluate sequence of 3 houses. At each step either you can add the middle house or the two adjascent houses to rob list (provided they are OK to rob.) The cumulative return would be the value of the immediate houses and the value returned by the function when called recursively on the remainder of the houses with the current houses marked robbed. I probably should just paste code here. Explaining it in word is twisted. My complain is I was given all of 2 minutes to think about the question and all of 5-7 minutes to write code for it. I was asked this in 38th minute of a 45 minute interview. this is actually a typical dynamic programming question: int getMaxValue(int[] values) { if (values.length < 3) return max(values[0], values[values.length - 1]); int[] best = new int[values.length]; best[0] = values[0]; best[1] = values[1]; best[2] = values[0] + values[2]; for (int i = 3; i < values.length; i++) { best[i] = max(best[i - 3], best[i - 2]) + values[i]; } return max(best[best.length - 2], best[best.length - 1]); } It is a dp problem and it is typical, but your solution is incorrect. Show More Responses public static int maxRob(int[] amount){ return maxAmount(amount, amount.length-1); } public static int maxAmount(int[] amount, int house){ if(house<=1){ return amount[house]; } return Math.max(amount[house]+ maxAmount(amount, house-2), maxAmount(amount, house-1)); } Here is the working solution!! static public int maxRob(int[] housePoints){ int length = housePoints.length; switch(length){ case 0: return 0; case 1: return housePoints[0]; case 2: return Math.max(housePoints[0],housePoints[1]); } Hashtable> prev, best = new Hashtable>(3); ArrayList scores = new ArrayList(1); scores.add(housePoints[0]); best.put(0,scores); scores = new ArrayList(1); scores.add(housePoints[1]); best.put(1,scores); scores = new ArrayList(1); scores.add(housePoints[0]+housePoints[2]); best.put(2,scores); for(int i=3;i>(3); best.put(i-1,prev.get(i-1)); best.put(i-2,prev.get(i-2)); int tmp = housePoints[i]; scores = new ArrayList(); for(int sc : prev.get(i-3)) scores.add(sc+tmp); for(int sc : prev.get(i-2)) scores.add(sc+tmp); best.put(i,scores); prev = null; } int max = 0; for(int sc : best.get(length-2)) if(sc>max) max = sc; for(int sc : best.get(length-1)) if(sc>max) max = sc; return max; } public int maxRob(int[] W) { int sz = W.length; int[] V = new V[sz]; if(sz == 0) { return 0; } else if(sz == 1) { return W[0]; } else if(sz == 2) { return max(W[0], W[1]); } V[0] = W[0]; V[1] = max(V[0], W[1]); for(int i = 2; i < sz; i++) { V[i] = max(W[i] + V[i-2], V[i-1]); } return V[sz]; } 1. We need an int array same size as house values array to keep track of dp local results. 2. We need the local results to construct path, i.e., which houses we want to rob. Here's Java code with unittest /* * MaxRob(n) = Max(MaxRob(n-2)+value(n), MaxRob(n-1)) */ public class RobHouse { public static void MaxRob(int[] values) { if (values.length==0) { return; } if (values.length==1) { System.out.println("only 1 house to rob. Value: " + values[0]); return; } if (values.length==2) { System.out.println("only 1 house to rob. Value: " + Math.max(values[0],values[1])); return; } int[] maxValues = new int[values.length]; maxValues[0] = values[0]; for (int i=1; i0; i--) { if (maxValues[i]!=maxValues[i-1]){ System.out.println("Rob house " + i + " value: " + values[i]); } } if (maxValues[0]==maxValues[1]){ System.out.println("Rob house 0 value: " + values[0]); } System.out.println("Rob done."); } public static void main(String[] args) { MaxRob(new int[] {5,2,4,1});//1010 MaxRob(new int[] {5,2,9,1});//1010 MaxRob(new int[] {1,2,1,1});//0101 } } If I were interviewer, I would give no hire for everyone above - Only Hee solution above is correct (but waaay overcomplicated). When writing code consider: 1,3,1,3,100 Found solution online, your interviewer must be from CMU: http://www.cs.cmu.edu/afs/cs/academic/class/15451-f10/www/solutions/hw3soln.pdf solve(0,0) //previous indicate whether previous house was looted or not solve(int house, bool previous) { if(house == N) return 0; int &res = dp[house][previous]; if(res != -1) return res; int res = solve(house+1, 0); if(!previous) res = max(res, cash[house]+ solve(house+1, 1)); return res; } A set of data: input: 4 4 3 5 9 output: 13 input: 10 4 3 5 9 2 6 8 1 10 7 output: 31 input: 100 46 62 74 1 88 77 69 92 67 16 83 79 25 22 56 34 14 91 58 64 65 66 89 75 5 17 51 78 8 47 52 41 81 96 95 28 33 35 4 85 70 9 63 7 27 36 71 48 43 94 80 60 26 13 50 90 10 20 39 55 15 49 23 82 29 57 73 68 59 31 18 97 40 93 100 54 38 44 2 84 37 45 99 98 21 86 24 53 3 61 42 6 19 12 30 72 87 76 11 32 output: 2895 public class Solution { public int findMax(int[] houses) { if (houses == null || houses.length == 0) { return 0; } else if (houses.length == 1) { return houses[0]; } else if (houses.length == 2) { return Math.max(houses[0], houses[1]); } int[] res = new int[houses.length]; res[0] = houses[0]; res[1] = Math.max(houses[0], houses[1]); int max = res[1]; for (int i = 2; i max) { max = res[i]; } } return max; } } public static int rob (int[] amounts) { if (amounts == null) return 0; int[] max = new int[amounts.length]; max[0] = amounts[0]; max[1] = Math.max(amounts[0], amounts[1]); for (int i = 2; i < amounts.length; i++) { max[i] = Math.max(max[i-2] + amounts[i], max[i-1]); } return max[max.length - 1]; } Show More Responses public class MaxRob { public static void main(String[] args) { int[] houseValues = new int[]{1, 3, 1, 3, 100}; int[] selfPlusMax = new int[houseValues.length]; int[] selfMinusMax = new int[houseValues.length]; selfPlusMax[0] = houseValues[0]; selfMinusMax[0] = 0; for (int i = 1; i < houseValues.length; i++) { selfPlusMax[i] = selfMinusMax[i - 1] + houseValues[i]; selfMinusMax[i] = Math.max(selfPlusMax[i - 1], selfMinusMax[i - 1]); } System.out.println( "Max Rob : " + Math.max(selfPlusMax[houseValues.length - 1], selfMinusMax[houseValues.length - 1])); } } |

**1**–

**10**of

**6,128**Interview Questions

## See Interview Questions for Similar Jobs

- Senior Software Engineer
- Software Developer
- Software Development Engineer
- Intern
- Software Engineer Intern
- Data Scientist
- Analyst
- Engineer
- Product Manager
- Software Engineer II
- Business Analyst
- Consultant
- Associate Software Engineer
- Staff Software Engineer
- Java Developer
- Director
- Project Manager
- Senior Software Developer
- Software Engineering Intern
- Software Engineer III