# Companies matching "Facebook"

## Facebook Interview Questions

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

Write some pseudo code to raise a number to a power. 10 Answerspretty trivial... int raise(num, power){ if(power==0) return 1; if(power==1) return num; return(raise(num, power-1)*num); } double Power(int x, int y) { double ret = 1; double power = x; while (y > 0) { if (y & 1) { ret *= power; } power *= power; y >>= 1; } return ret; } Show More Responses In Ruby: def power(base, power) product = 1 power.times do product *= base end product end puts "2^10 = 1024 = #{power(2,10)}" puts "2^0 = 1 = #{power(2,0)}" puts "2^1 = 2 = #{power(2,1)}" If I were an interviewer, I would ask the Aug 29, 2010 poster why he used bitwise operators, and whether he would deploy that code in a production environment, or if he merely wanted to demonstrate, for purposes of the interview, that he understands bitwise operations. Because it uses dynamic programming and is lots more efficient than your algorithm. If the power is not integer, use ln and Taylor series If I'm the interviewer, none of above answers is acceptable. What if y < 0? what if y < 0 and x == 0? I'm seeing an endless recursion that will eventually overflow the stack, and the none-recursive one just simply returns 1. There is a way to do this in a logN way rather than N. function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1); } This is from Programming pearls.. interesting way. small mistake function power(x, n) { if n == 1 return x; // Even numbers else if (n%2 == 0) return square( power (x, n/2)); // Odd numbers else return power(x, n-1) * x; } |

Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this? 6 AnswersIt can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming. Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!? Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Show More Responses Awesome!! The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features It wasn't 100% clear to me, then I found the Wiki page http://en.wikipedia.org/wiki/Summed_area_table |

### Account Executive at Facebook was asked...

If you were handed 50 new target accounts how would you start? 1 AnswerI would segment the customers into territorial zones in terms of proximity. I would then rank the prospects in terms of size and potential. I would then begin to aggressively seek out business from the group zones on a daily basis. I would seek the appointment to be a two pronged initiative, in which I seek to introduce myself and find out the current status of the business. I would then conduct this for 8-10 customers per day until the fifty calls are completed, and follow up calls have been scheduled. This is assuming that these 50 calls are my only account base. If I am to fit these in on top of active customers, I would then fit them in my normal call list and seek to target 2-3 per day starting with the largest potential customers in a given area which I am already scheduled to be in for that day. |

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

### Data Scientist at Facebook was asked...

You're about to get on a plane to Seattle. You want to know if you should bring an umbrella. You call 3 random friends of yours who live there and ask each independently if it's raining. Each of your friends has a 2/3 chance of telling you the truth and a 1/3 chance of messing with you by lying. All 3 friends tell you that "Yes" it is raining. What is the probability that it's actually raining in Seattle? 30 AnswersBayesian stats: you should estimate the prior probability that it's raining on any given day in Seattle. If you mention this or ask the interviewer will tell you to use 25%. Then it's straight-forward: P(raining | Yes,Yes,Yes) = Prior(raining) * P(Yes,Yes,Yes | raining) / P(Yes, Yes, Yes) P(Yes,Yes,Yes) = P(raining) * P(Yes,Yes,Yes | raining) + P(not-raining) * P(Yes,Yes,Yes | not-raining) = 0.25*(2/3)^3 + 0.75*(1/3)^3 = 0.25*(8/27) + 0.75*(1/27) P(raining | Yes,Yes,Yes) = 0.25*(8/27) / ( 0.25*8/27 + 0.75*1/27 ) **Bonus points if you notice that you don't need a calculator since all the 27's cancel out and you can multiply top and bottom by 4. P(training | Yes,Yes,Yes) = 8 / ( 8 + 3 ) = 8/11 But honestly, you're going to Seattle, so the answer should always be: "YES, I'm bringing an umbrella!" (yeah yeah, unless your friends mess with you ALL the time ;) I thought about this a little differently from a non-bayes perspective. It's raining if any ONE of the friends is telling the truth, because if they are telling the truth then it is raining. If all of them are lieing, then it isn't raining because they told you that it was raining. So what you want is the probability that any one person is telling the truth. Which is simply 1-Pr(all lie) = 26/27 Anyone let me know if I'm wrong here! Here's another perspective on how to answer a question like this: Bring an umbrella. It's Seattle - if it's not raining right now, it probably will be by the time you get there. Show More Responses I flagged Nub data scientist's answer as useful, because it shows an interesting flaw in reasoning. The 3 random variables are not to be treated as intrinsically independent. Only conditioned on the truth (raining/not raining) are they independent. Isn't the answer 2/3. The key thing is that they are ALL saying "Yes". You can't have all 3 says yes and have some people lying and some people telling the truth. It either is raining or it isn't. Not both. They either are all lying or all telling the truth. Since they are all in agreement (all lying or all truthful), they are essentially voting as one person. What is the probability that one person is telling the truth? 2/3 Answer from a frequentist perspective: Suppose there was one person. P(YES|raining) is twice (2/3 / 1/3) as likely as P(LIE|notraining), so the P(raining) is 2/3. If instead n people all say YES, then they are either all telling the truth, or all lying. The outcome that they are all telling the truth is (2/3)^n / (1/3)^n = 2^n as likely as the outcome that they are not. Thus P(ALL YES | raining) = 2^n / (2^n + 1) = 8/9 for n=3 Notice that this corresponds exactly the bayesian answer when prior(raining) = 1/2. I'm not sure why it's not just as simple as this: All three friends say it is raining. Each friend has prob. 1/3 of lying. Since the friends all say the same thing, they are either all telling the truth or all lying. The question asks what is the probability that it is raining. This is equivalent to asking, what is the probability that all three friends are telling the truth. And that is equivalent to asking, what is the probability that not one of them is lying. Since the the friends were asked independently, this should equal 1 - (1/3 * 1/3 * 1/3) = 0.962. Ah. Looks like my answer agrees with "nub data scientist". What is the probability that both he and I are wrong? :-) TLP and nub data scientists, Your answers include possibilities which are not feasible; we cannot have any combination of 2/3 and 1/3 together... what about (2/3)^3? I agree with TLP and nub scientist. For me, the question is really (1 - the odds that all three of your friends are lying to you) Clearly 1 - 1/3 * 1/3 * 1/3. It's convenient that they all gave the same answer, otherwise it would be more difficult. Let Y denote rain, N denote no rain Actual Answer probability ------------------------------------------ Y=> 8/27 YYY, 1/27 NNN, 12/27 YYN, 6/27 YNN N=> 1/27 YYY, 8/27 NNN, 6/27 YYN, 12/27 YNN So, P(Y|YYY) = (8/8+1) = 8/9 The probability of raining is that they are all telling the truth, therefore, (2/3)^3. P(rain / yes yes yes) = (2/3)^3 / ((2/3)^3 + (1/3)^3) =(8/27) / ((8/27) + (1/27)) = 8 / (8 +1) = 8/9 26/27 is incorrect. That is the number of times that at least one friend would tell you the truth (i.e., 1 - probability that would all lie: 1/27). What you have to figure out is the odds it raining | (i.e., given) all 3 friends told you the same thing. Because they all say the same thing, they must all either be lying or they must all be telling the truth. What are the odds that would all lie and all tell the truth? In 1/27 times, they would the all lie and and in 8/27 times they would all tell the truth. So there are 9 ways in which all your friends would tell you the same thing. And in 8 of them (8 out of 9) they would be telling you the truth. Show More Responses There is an obvious conceptual reason as to why several answers here (ones that don't use Bayes' formula) are incorrect. The probability in question has to depend on the probability of rain in Seattle. If, for the sake of discussion, it ALWAYS rains in Seattle, i.e. P(rain)=1, then the required prob. is always 1 as well. Likewise if it's a place where it never rains, or if the question asks about the prob. of it raining elephants given the 3 friends said yes, it'd be still 0. I believe this is a std. textbook example of the Bayes' formula, anything short of that I don't think will work out. Please correct me if incorrect. But I would just prefer to condition. either they are all telling the truth and its it raining or they are all lying and it is not raining. P(rain)=P(rain|truth,truth,truth)*P(truth,truth, truth)+P(rain|lie,lie,lie)*P(lie,lie,lie) notice that truth does not mean yes it is raining, it simply corresponds to them telling the truth. Since they said yes, IF they were lying and we knew they were lying then the probability of rain would be zero, thus eliminating the second term. P(rain)=P(rain|3xtruth)*P(3xtruth) and the probability of the truth is (2/3)^3 and the probability of rain if they are telling the truth is 1. I did a little skipping of steps, since truth doesnt equal yes, but i just sort of meshed it toegher towards the end YES=yes,yes,yes T=truth, truth, truth L=lie,lie,lie P(Rain|YES)=P(Rain|YES,T)*P(T)+P(Rain|YES,L)*P(L) P(Rain|YES,L)=0==> whats the probability of rain given we know that they are lying and theyve told us it is raining. P(Rain|YES)=P(Rain|YES,T)*P(T) P(Rain|YES,T)=1==> whats the probability of it raining given that they are telling the truth and have told us its raining then P(T)=(2/3)^3 its obvious. why in the world would i do bayesian methods when its certain I think the first answer is incorrect. The basic flaw is that it is assumed that all three friends lie together or be honest together, so it does not take the cases of Yes.no.Yes or Yes.Yes.no ...etc For the correct answer we need to update posterior probability after each yes so Assuming P(raining) =0.75 prior probabilty P(raining | yes) = (2/3)*0.75 / ( (2/3)*0.75 + (1/3)*0.25 ) = 6/7 P(raining | yes,yes) = (6/7)*(2/3) / ( 6/7*2/3 + 1/7*1/3) = 12/13 P(raining | yes,yes,yes) = (12/13)*(2/3) / ( 12/13*2/3 + 1/13*1/3) = 24/25 I dont see the interview saying that all friends are sitting together so they are independent which means they can lie separately I agree with (2/3)^3. Interview Candidate solves this problem using Bayesian stats despite the fact that no enough information is given to do Bayesian probability analysis i.e. he had to pull the probability of it raining in Seattle out of thin air when it was not given in the interview question. With only the information from the interview question, we have to assume that friends are either all lying or all telling the truth. Let truth=T and lie=L P(TTT)=8/27, P(LLL)=1/27, P(TLL)=2/27,P(TTL)=4/27. But we know that they all had the same answer, so we must compare P(TTT) to P(LLL). P(TTT) is 8 times more likely than P(LLL), so we have P(All same answers|TTT)=8/9, P(All same answers|LLL)=1/9. Therefore the solution given ONLY THE INFORMATION GIVEN is P(Rain)=8/9, P(Dry)=1/9. This problem requires the marginal probability of rain to solve, following Interview Candidate's answer. M.B. provides the rationale behind why the bayes approach is necessary: if the pr(rain) = 0, then the pr(rain|y, y, y) = 0. (maybe it is July in Seattle). A few conceptual problems in many answers that I want to point out: 1) There is lots of conflation between Pr(truth) and Pr(Y). Pr(truth) = Pr(Y|R) does not equal Pr(Y). 2) Consider there is only a single friend and they say yes, the logical conclusion from a lot of these answers is that Pr(Rain|Yes) = Pr(Yes|Rain) = 2/3, which is not correct. Bayes' rule is very clear in this simpler case. 3) The friends' answers are conditionally independent assuming no collusion. The combinations of their honesty/lying adds no additional information. The marginal probabilities are not independent, Pr(y,y,y) does not equal pr(y)^3, it equals pr(y,y,y,rain) + pr(y,y,y, no rain), the integration of the joint space over rain. Using conditional independence and bayes rule, this becomes: pr(y|rain)^3*pr(rain) + pr(y|no rain)^3(1-pr(rain)). A more general solution using Pr(rain) = r. Pr(rain|y,y,y) = Pr(y,y,y|rain)*pr(rain)/pr(y,y,y) #Bayes' formula pr(y,y,y|rain) = pr(y|rain)^3 = (2/3)^3 #conditional independence pr(y,y,y) = pr(y|rain)^3*pr(rain) + pr(y|no rain)^3*pr(no rain) #by definition, see point 3 the answer: r*(2/3)^3 / [r*(2/3)^3 + (1 - r)*(1/3)^3] It should be (2/3)^3, I think zen and todo is correct. As a big dumb animal, I have to write out a probability tree and thing about this simply. You only have 2 scenarios where all three say it is raining (all three are telling the truth-raining OR all three are lying - not raining). Assume the probability of rain is 0.5 for simplicity. P(Rain and YYY) = 1/2 * 2/3 * 2/3 * 2/3 = 8/54 P(Not Rain and YYY) = 1/2 * 1/3 * 1/3 * 1/3 = 1/54 Thus P(Rain | YYY) = P(Rain and YYY) / [P(Rain and YYY) + P(Not Rain and YYY)] = 8 / (8+1) = 8/9 I know it isn't the most mathematically rigorous or syntactically correct solution, but I'd bet a pretty penny that the answer is 8/9 with the following assumptions (P(rain) = 0.5 and naive bayes - friends didn't collaborate). Most of the answers/comments made all unconditional assumptions except a few reasonings that lead to the 8/9 probability. Note that the question states that "Each of your friends has a 2/3 chance of telling you the truth". This essentially means P(raining, yes) + P (non-raining, no) = 2/3. Any attempts to interpret this as conditional probability P(raining | yes) = 2/3 or P(yes | raining) = 2/3 are making other assumptions. Show More Responses 8/27 is not the answer. For the weather to be nice in this case, all 3 of your friend NEED to have lied to you. Therefor the odds are 1/27. It's really shocking to see how many people post incorrect answers here with such confidence. That said, Bayes' rule is somewhat counterintuitive if you're not familiar with probability theory. Let P(y|r) = prob of each yes given raining = 2/3, P(y|n) = prob yes given not raining = 1/3. Let P(r) = probability of rain = 1/4 given the prior knowledge. P(n) = probability of no rain = 3/4. P(r | y^3) = ( P(y^3 | r) P(r) ) / ( P(y^3 | r) P(r) + P(y^3 | n) P(n) ) = ( P(y | r)^3 P(r) ) / ( P(y | r)^3 P(r) + P(y | n)^3 P(n) ) = ( (2/3)^3 (1/4) / ( (2/3)^3 (1/4) + (1/3)^3 (3/4) ) = (2/27) / ( (2/27) + (.75/27) ) = 2/2.75 = 8/11 What if the answer is 50% since the chance of rain and not rain does not depend on what your friends tell you. In the absence of further information, the only correct answer is the posterior probability of rain p is in the interval (0, 1). In the absence of further information any prior is as good as any other, so by implication the posterior can take any value as well. The interval for p can be restricted to [0, 1] on the assumption that the question to the friends would not be posed if the prior is absolute certainty whether it will rain or not. With the further assumption that the prior probability is measured with limited precision (e.g. rounded to a percentage point), the posterior would be in the interval (0,075, 1). If the alternative assumption is made that information from the friends will be requested only if it had any chance to move the posterior below or above 0.5, the posterior interval for the probability is (0.5, 1). any more precise answer than that requires further information about the prior which is not supplied in the original problem formulation. Also note that even a precise answer about the probability of rain is not sufficient to answer the question whether an umbrella should be brought or not. Assume probability of raining in Seattle P(R) = 1/4 Assume friend says Y 50% of the time (Theoretical probability) P(Y) = 1/2 Probability of friend saying yes given its raining P(Y/R) = 2/3 Probability of 3 friends saying yes given its raining = P(YYY/R) = 8/27 Probability of 3 friends saying yes = P(YYY) = 1/8 P(R/YYY) * P(YYY) = P(YYY/R)*P(R) P(R/YYY) = 8/27*1/4/(1/8) = 16/27 (About 59%) A posterior probability of 59% given 3 yes and a prior probability of 25% sounds reasonable to me The probability of each of the friend say "YES" is 2/3 * 2/3 * 2/3 = 8/27. Now the probability that it is actually raining in Seattle depends on that how do I select them to phone. There is only three way to select and phone them. So, the probability that it is actually raining in Seattle is 3 * (8/27) = 8/9. Probability that it is raining given that all 3 of them said "yes" = P(AT LEAST one of them is telling the truth) = P(exactly 1 of them telling the truth) + P(2 of them telling the truth) + P(all 3 of them telling the truth) P(exactly 1 of them telling the truth) = P(of first person telling truth) * P(of 2nd person telling lie) * P(of 3rd person telling a lie) = (2/3) * (1/3) * (1/3) = 2/27 + P(exactly 2 of them telling the truth) = P(of first person telling truth) * P(of 2nd person telling the truth) * P(of 3rd person telling a lie) = (2/3) * (2/3) * (1/3) = 4/27 + P(exactly 3 of them telling the truth) = P(of first person telling truth) * P(of 2nd person telling the truth) * P(of 3rd person telling the truth) = (2/3) * (2/3) * (2/3) = 8/27 ANSWER: Probability that it is raining given that all 3 of them said "yes" = P(AT LEAST one of them is telling the truth) = P(exactly 1 of them telling the truth) + P(2 of them telling the truth) + P(all 3 of them telling the truth) = (2/27) + (4/27) + (8/27) = 14/27 |

### 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<size;) { start=pos; initial=num[pos]; do{ pos = (offset+pos)%size; pos = pos<0?size+pos:pos; buffer=num[pos]; num[pos]=initial; initial=buffer; i+=1; }while(pos!=start); pos+=1; } } 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<len(array): if(array[s][2]==1): s+=1 else : break return map(lambda x: x[1],array) def indsort(array): indarray=[] for i,a in zip(xrange(len(array)),array): indarray.append([i,a,0]) return sorted(indarray,key=lambda x: x[1]) def main(): array=[1,5,2,9,4,8,3,1,9,7,4,5,9,5,6,7,8] indarray=indsort(array) print "array : " print array print "swap circles :" uarray=unsort(indarray) print "unsorted array :" print uarray if __name__=='__main__': main() 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<num-1; j++) { prev = (start + n - k)%n; arr[start] = arr[prev]; start = prev; } arr[start] = tmp; } for(int i=0; i<n; i++) cout << arr[i] << " "; cout << endl; } int main() { int arr[] = {1, 2, 3, 4, 5, 6}; rotate_arr(arr, 6, 4); return 0; } 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 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. 13 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]; } |

Function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in Linear time and constant space. n = 3. 1 1 1 1 2 2 1 3 Ans = 4 13 Answers$cache = array(); $cache[1] = 1; $cache[2] = 2; $cache[3] = 4; function stepways($input) { global $cache; if ($input < 4) { $ret = $cache[$input]; } else { $start = 4; $ways = 4; while ($start < $input) { $ways = $cache[$start - 3] + $cache[$start - 2] + $cache[$start -1]; $cache[$start] = $ways; $start++; unset($cache[$start - 3]); } return $ways; } return $ret; } import java.io.*; import java.util.*; class NumSteps{ public static Integer[] getR(Integer[] a, int i){ Integer [] c = new Integer[a.length-1]; for(int j =0; j q = new LinkedList(); q.add(a); while(q.size() >0){ Integer [] tmp = q.poll(); for(int i = 0; i 2) q.add(tmp1); tmp1 = null; } } System.out.println(N); }catch(IOException e){} }//end of main } //end of class numSteps javascript version: var countSteps = (function () { var cache = { 1: 1, 2: 2, 3: 4 }; return function (n) { if (n < 1) throw new Error('number must be positive'); if (n < 4) return cache[n]; var result = (cache[n - 1] || countSteps(n - 1)) + (cache[n - 2] || countSteps(n - 2)) + (cache[n - 3] || countSteps(n - 3)); cache[n] = result; return result; } })(); Show More Responses edit: the above can be improved a bit by replacing if (n<4) with if (cache[n]) int numSteps( int n ) { if ( n < 0 ) return 0; if ( n == 0 ) return 1; int result = 0; result += numSteps( n - 1 ); result += numSteps( n - 2 ); result += numSteps( n - 3 ); return result; } import sys def Calculate(n): '''Calculates no of ways steps can be climbed''' if n == 1: return 1 elif n == 2: return 2 elif n == 3: return 4 Count=[0]*4 Count[0],Count[1],Count[2] = 1,2,4 shifter, a, b, c, d = 0, 0, 0, 0, 0 for i in xrange(3,n): a, b, c, d = shifter%4, (shifter+1)%4, (shifter+2)%4, (shifter+3)%4 Count[d] = Count[a] + Count[b] + Count[c] shifter = shifter+1 return Count[d] print Calculate(input()) this is the one that works for me: 1 #!/usr/bin/python 2 #-*- encoding: utf-8 -*- 3 4 steps = [1, 2, 3] 5 6 def find_all_ways(n=3): 7 stack = [] 8 ways = 0 9 stack.append((1, 0)) 10 max_len = 1 11 while len(stack) != 0: 12 (s, sum) = stack.pop() 13 if sum == n: 14 ways += 1 15 if sum > n: 16 continue 17 for step in steps: 18 stack.append((step, sum + step)) 19 if len(stack) > max_len: 20 max_len = len(stack) 21 return ways, max_len This problem is related to Fibonacci series type problem where f(n) =f(n-1)+f(n-2)+f(n-3) We can employee dynamic programming to provide the answer in liner time and space. As shown below Code in Java:: ------------------- import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Fibonacci { /** * @param args * @throws IOException * @throws */ public static void main(String[] args) throws IOException { // TODO Auto-generated method stub int a=1; int b=1; int c=2;//Storing the predefined value int input = Integer.parseInt((new BufferedReader(new InputStreamReader(System.in))).readLine()); if(input < 0) System.out.println("Negative Number Inserted... Plx Insert Positve Number!!!"); else if(input == 0) System.out.println("0"); else if(input == 1) System.out.println("1"); else if(input == 2) System.out.println("2"); else { int sum=0; for(int i=2;i<input;i++) { sum = a+b+c; a=b; b=c; c=sum; } System.out.println(sum); } } } Recursive solution in Java: public static void countSteps(int n) { if (n == N) { count++; } else { if (n > N) return; for(int step=1; step < 4; step++) { countSteps(n+step); } } } Where: N = the input number of steps; count = the final result; Another Javascript answer. function getSteps(n) { var lookUp = { 1: 1, 2: 2, 3: 4 }; if (lookUp[n] != null) { return lookUp[n]; } else { for (var i = 4; i <= n; i++) { lookUp[i] = lookUp[i - 1] + lookUp[i - 2] + lookUp[i - 3] } return lookUp[n]; } }; o(n^2) import java.util.Scanner; public class StairsCombo { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.print("Enter total stairs : "); int n = in.nextInt(); System.out.println(countCombos(n)); } } private static Integer countCombos(int n) { System.out.println("counting for " + n); if (n < 1) return 0; switch (n) { case 1: return 1; case 2: return 2; case 3: return 4; default: return countCombos(n - 1) + countCombos(n - 2) + countCombos(n - 3); } } } public class StairClimber { /** * iterative solution: O(n) time, O(1) memory * @param stairs * @return stair partition */ public static int countStairPathsIter(int stairs){ //base cases and record of preceding values //for values of "stairs" > 3 int[] pathCounts= {1,2,4}; //v0,v1,v2 if(stairs <= 3){ return pathCounts[stairs-1]; } for(int i=4; i<=stairs; i++){ pathCounts[2]= pathCounts[0]+pathCounts[1]+pathCounts[2]; //v0+v1+v2 pathCounts[1]= pathCounts[2]-pathCounts[0]-pathCounts[1]; //v2 pathCounts[0]= pathCounts[2]-pathCounts[0]-pathCounts[1]; //v1 } return pathCounts[2]; } /** * tail-recursive solution: O(n) time , O(1) memory * @param stairs * @return stair partition */ public static int countStairPathsRec(int stairs){ return cntStrs(stairs,1,2,4); } private static int cntStrs(int input, int v1, int v2,int v3){ if(input==1){return v1;} if(input==2){return v2;} if(input==3){return v3;} return cntStrs(input-1,v2,v3,v1+v2+v3); } public static void main(String[] args){ System.out.println( countStairPathsRec(8)); } } |

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

Given an array of integers, now we want to erase all 0's (can be other value), and we want the result array condensed, meaning no empty cell in the array. 16 Answers#include #include void main() { clrscr(); int i,j,k.a[20]; cout>n; cout>a[i]; } cout<<"entered array is"; for(i=0;i<n;i++) { cout<<a[i]; } for(i=0;i<n;i++) { if(a[i]==0) /*operation for deleting zero's*/ for(j=i;j<n;j++) {a[j]=a[j+1]; }} cout<<"array left is"; for(i=0;i<n;i++) { cout<<a[i]; } getch(); } Assuming that the array is named iArray and the unwanted number is named delthis. I think this should work: public condense(int[] iArray, int delthis){ ArrayList iList = new ArrayList(); for (int i=0; i<iArray.length; i++){ if (iArray[i] != delthis) iList.add(iArray[i]); } return iList.toArray(); } Test on Java 6: public Integer[] condense(int[] iArray, Integer delThis){ ArrayList iList = new ArrayList(); for (int i=0; i<iArray.length; i++){ if (iArray[i] != delThis) iList.add(iArray[i]); } return iList.toArray(new Integer[iList.size()]); } Show More Responses void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1+1; } test on gcc void erase( int arr[] , int size , int &new_size ) { int p1 = 0, p2 = 0; while ( p1 < size && p2 < size ) { if ( arr[p1] == 0 ) { while ( p2 < size && arr[p2] == 0 ) { ++ p2; } if ( p2 == size ) { break; } arr[p1] = arr[p2]; arr[p2] = 0; ++ p1; ++ p2; } else { ++ p1; ++ p2; } } new_size = p1; } // This is erase/remove idiom one liner. Too much code with C. std::vector v; v.erase(std::remove(v.begin(), v.end(), 0), v.end()); #include using namespace std; int main() { int a[] = { 0,2,3,0,4,0,5,0,0,0}; int i,nz = 0; for(i = 0; i<=9 ; i++) { if (a[i] == 0) nz++; else a[i-nz] = a[i]; } for(i = 0; i <=9-nz ; i++) cout << a[i]<<" "; return 0; } Python: ------------- s = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] for k in xrange(len(s), 0, -1): if not s[k-1]: s.pop(k-1) -------------- after: [1, 2, 4, 5, 1, 1, 7, 8, 2, 4, 5, 1, 2, 8, 5, 6, 8] void erase(int arr[], int sz, int errasedVal) { int i = 0, j = -1; while(i < sz && j < sz) { if(arr[i] == errasedVal && j == -1) j = i; else if(arr[i] != errasedVal && j != -1) { cout << arr[i]<< " " << j << endl; swap(arr[i], arr[j]); j++; while(arr[j] != errasedVal && j < sz) j++; } i++; } } void RemoveZeros(vector& input) { int p1 = 0, p2 = 0; int len = input.size(); while (p1 < len && p2 < len) { while(input[p1] == 0) { ++p1; } input[p2++] = input[p1++]; } input.resize(p2); for (int i = 0; i < p2; ++i) { cout << input[i] << endl; } } @Bikash is my favorite answer because it uses constant space, unlike some of the above answers. Completely trivial in C#. The only thing to note about the solution is that it does not do the replacement "in place" and returns a new array. But that was not specified as a constraint in the question. int[] RemoveZeros(IEnumerable input) { return input.Where(x => x != 0).ToArray(); } Objective-C NSArray *input = @[@2, @3, @1, @2, @0, @2, @0, @1, @3, @1, @2, @0]; input = [input objectsAtIndexes:[input indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) { return ![obj isEqualToNumber:@0]; }]]; ----------------------- output:(2, 3, 1, 2, 2, 1, 3, 1, 2) Show More Responses def eraseDigit(aList, aDigit): theResult = [int(''.join([x for x in str(X) if x != str(aDigit)])) for X in aList] return theResult theList = [432, 4409, 85, 6887, 87, 1386] theDigit = 8 print eraseDigit(theList, theDigit) import java.util.Arrays; public class facebook1 { public static void main(String[] args) { int [] givenArray = new int[] {3,4,45,5,0,3,0,32,4,5,40,23,0,43,0,0,43,2,4}; int rightPointer = givenArray.length -1; for(int leftPointer = 0; leftPointer 0; i--){ if(givenArray[i] == 0){ int [] tempArray = new int[givenArray.length-1]; System.arraycopy(givenArray, 0, tempArray, 0, givenArray.length-1); givenArray = tempArray; } } System.out.println(Arrays.toString(givenArray)); } } Here is a short python solution: a = [1, 2, 4, 0, 5, 0, 1, 0, 0, 1, 7, 0, 8, 0, 2, 4, 5, 1, 2, 8, 0, 5, 6, 8] a = [x for x in a if x != 0] |