# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

### Manager at Amazon was asked...

If you had 5,623 participants in a tournament, how many games would need to be played to determine the winner 61 AnswersBefore I could figure that out, I'd need to know whether the # of participants represents the number of individuals on larger teams, or the number of teams A specific numerical answer can be given, but there are multiple ways the tournament can be setup, for example, are there play-in games, byes, etc. I would think the question is being given to a manager to see how they think and process, and then come up with a specific numerical answer, as opposed to just a math problem. It can be just one game. A huge mock battle. Show More Responses 5,622. Assuming it is a single elimination tournament. All teams lose one game except the champs. It's always # of teams - 1 if each team plays until it loses in one(team)-on-one(team) contests, the answer is ln(5623)/ln(2) Assuming it is a simple process of elimination, it takes 5622 losers to get 1 winner from 5623 participants. So, it would require 5622 games. Assuming it is a simple process of elimination, it takes 5622 losers to get 1 winner from 5623 participants. So, it would require 5622 games. if it's a 1:1 type draw, then # rounds = (5623)**x where x is base 2. a good answer is between 12 and 13 rounds. 2**12 = 4096 so I'd draw up 13 rounds and give out 1,527 byes. There is no true answer as the question is very open ended. The interviewer is probably looking at task delegation, management and creativity skills. One One. Obviously. One game, all players participate. If participants equal number of teams involved, think power of 2. Show More Responses The interviewer is not looking for the right answer because there can be many. What he/she is looking for is your logical approach in solving the answer. So you could start by probing more is first I would like to understand if 5,623 participants represent the number of team or individuals. Then ask the next logical question based on the answer. Everyone who didn't ask a follow up question except Mike is right. The question says, "if YOU had ...". This requires no follow up questions, because YOU should decide how YOU are going to operate YOUR tournament. Why would Mike or any of the others think it's someone else's job to organize his/her tournament. Oh just a follow up. My tournament would be held in the top of a hardly dormant volcano. Everyone would get a backpack full of grenades and the first one out of the crater without dying wins. That makes 1 game. Also, I think most participants who got out of the volcano alive would consider themselves winners, but only one would get to keep the gold plated dancing chiquita banana. Yipee!!!! I'm right too! Take that Mike! it'd be one game if it was a battle to the DEATH I agree with Nancy there is no strict answer to this question it is all about problem solving. First thing to do is to get more information, if it is not forthcoming then make assumptions, as an interviewer I would not be impressed if the candidate didn't ask for more information, although I probably would not supply any more. Then looking for a logical (and humane) answer which is substantiated with appropriate reasoning. Ie number of people on a team, game being played, what is required to win a match, are there several games in a match? knockout style tornamant sounds like a good approach. I agree with Mike. Just show the interviewer how you think and how you will tackle the problem in a colloborative environment 1 I agree with the very first response. Many of you are perhaps making the assumption that this is a one-on-one tournament such as singles tennis. Isn't it possible the question could refer to a soccer or basketball tournament where there are multiple players on each team? That would certainly bring the number of games to be played down considerably. I'd give an approximate answer, stating my assumptions. The question asked is not the number of rounds (2 people per game: log base 2, giving approximately 13 rounds with everyone playing at least one game ) - it's the number of games. So, if two people per game, then it's the sum of 5623/2 + 5623/4 + 5623/8 + 5623/16 + ... The limit of this is not something I know off the top of my head, but it's less than 5623. Also, interestingly, you need to account for the original number being odd. That could be accommodated in a number of ways, none of them straightforward. 5622 ... if based on elimination between 2. Show More Responses I personally agree with most of you. If you read the posts here, you see all types of answers. Some say "1". Short and simple rules to a simple game. Others have posted all types of formulas and methods to figure out a process. The answers here are all a good example of different minds using different means to find an end. Those different answers are what a good interviewer would be looking for. If the job needs a person that is logical and takes time to plan things out, or perhaps someone that needs to think fast on their feet. That kind of question could come in handy for any kind of interview in my opinion. 1 I think the interviewer is asking you to ask for more information, ask three qualifieng questions to be exact in order to show you have the probing skills to fully understand a customers situation or company problem and have the ability to ask the appropriate questions to or to get the help to solve. Question 1) How many players are allowed per round? Question 2) Is there a time restriction on these rounds? (Daylight or Night as well) Question 3) Are there going to be different classes for the golfers? Are we taking handicaps into consideration? I guess there could be more questions but chances are the interviewer would stop you after the third question. The correct answer is: "I didn't come here to play bulls**t games for 8 hours, you Mac-slinging hipster. Ask me a real question." 5622....................................assuming single elimination 5623 is a prime number. Good luck dividing into even teams. Also, there is no use of the word "minimum" in the original question. This question is a good example of a problem with no absolute answer. If I were to ask this of an interview candidate (which I wouldn't because I think subjective questions are mostly a waste of time for everyone involved), I would look for someone who can: A) Ask questions to pin down a few details. B) Formulate options. C) Suggest options with recommendation and take feedback. D) Execute (pretty hard to demonstrate in the 10 minutes max I'd give this). p.s. I'd hire chapped. Good answer! Depends on the numbers of players per team. 'Excuse me, I'm just waiting for excel to open and my math wiz buddy in accounts to pick up to verify my calculation. I'll get back to you in two minutes with the answer.' 'Excuse me, I'm just waiting for excel to open and my math wiz buddy in accounts to pick up to verify my calculation. I'll get back to you in two minutes with the answer.' I would try and be creative and put my suggestions in front of them while I give them a reason for all the options that I choose. For instance, I'd say I would create 5 levels for each game as adding more levels makes the game more challenging and interesting. I wouldn't want to set up too many games as it would require a lot of overhead using up a lot of resources for organizing large number of games. Hence, in each round I would eliminate 20 participants. That would make 100 players getting eliminated after every game. After every 10 games, I would allow all the eliminated contestants to battle it out and 15 can re-enter the game as the eliminated ones would get a chance to observe, learn, refresh and get a second chance... (The interviewer might stop me eventually before it gets too long). Even though my answer was too long, I think I would show them how my logical thinking works. They would see that I am thinking aloud and in the end all that matters is how we approach the problem rather than giving them a vague answer with no reasoning. Show More Responses Oh and I agree with Toasty, I would hire chapped :) I like the way they think. Oh and I agree with Toasty, I would hire chapped :) I like the way they think. i dont know how everybody else thinks butI divided by two with an extra game for when the number is odd and came up with 5627. the question was straight forward, " How many games".... I would have been startled as well, just reading it. Congrats on keeping your calm! My intuitive answer would have probably been: Game theory - 1 or rather none - when it's a battle to death everyone loses, even the winner (last man standing, howling at the moon). I would have likened it to the company and customer situation - in good company EVERYONE is a winner (win-win scenario). Good luck with your endeavors! 1. I think, this question is for a management position. The size of team is given as a too big random number. One cannot control a team of 5627. Divide them in a measure size, e.g size of 10 or 20 (any measureble size). With 10, there will ve 563, which can be further divided into 10, leading to apx 57. that can be futher divided into 10, leaving it to 6 teams. proformance/ goals can be set and can be evaluated later. 2. or do a marathon. None. Our PC world demands everyone gets a trophy. ********************* Keep in mind the position, Nathaniel is right. YOU are organizing the tournament, make a rational decision and describe it. Your answer should be formulated to convey a skill. For example I might suggest something like this: 1 on 1 round robin, 5,623 players, SUM(1+2+3+...+5621+5622) games Quick and simple, shows some knowledge of algorithms but not very practical. The 1st participant plays 5622 others, the 2nd plays 5621, until the 5622nd plays 1 (5623rd participant). Notice you don't add 5623. Participant with the most wins is the champion. Supposed it is a single elimination. should be 5626 games because the first row would be 5623/2 = 2811.5 which means 1 person must be going to the next round to compete therefore we will have 2812 contestants then the second row would be 2812/2 = 1406 the third row would be 1406/2 = 703(odd number which means the one of them is going to the next round without a fight. ect... I believe I would have responded with "Is that how many applicants there are for this job?" Followed by "One game, one victor." Before answering you should read the interview report this question is linked from, where the question is explained in more detail -- """If you had 5,623 participants in a tournament, and each participant had to play games until he/she one or lost, and every game had a winner and loser, how many games would have to be played in order to determine the winner of the tournament""" So it's pretty unambiguous: Participants are individuals; the tournament is single elimination; games involve just two parties (a winner and a loser.) The question doesn't ask about the number of rounds involved, nor about timeframe. Just the sheer number of games. So we're left with an answer of 5622 games (because every game has one and only one loser and 5623 - 1 participants need to lose for there to be a single participant left as the winner, so that's how many games there must be.) Show More Responses Assuming in each game "n" people participate and there is just one winner in a game. If N is the total number of people (in this case 5623), then the approximate number of games would be: log(N)/log(g) -1 After each round, you would have half the number that started the previous round; except if it were an odd number it would he half + 1. So 13 rounds. 2812 1 1406 2 703 3 352 4 176 5 88 6 44 7 22 8 11 9 6 10 3 11 2 12 1 13 It is far simpler than you guys are making it out to be. In ALL single elimination tournaments there is one less game than the number of participants. Because in every game 1 team gets eliminated. And at the end 1 team has to be left standing. This will be a detailed explanation. Since they're asking for a tournament, that means one on one matches, and eliminations of 'participants' or players. With such a large number doing a round robin style tournament would not be very efficient, as every player would have to play every other player, ((N-1)^2)/2 =15,803,442 matches. I would first start to get more details of the tournament. If it were up to me to design the tournament and easily determine the number of matches, I would go with single elimination bracket because since its based on power of 2. Contrary to what what Bob InNorCal did, you dont start halving the at the beginning with 5623, because its not power of 2. You will get to a point where there wont be even numbers, and BYEs will have to be given, it would be unfair to give byes out at the end or middle of the tournament, players would complain that others got BYEs and they didnt. Detailed Explaination: In a single elimination bracket, the brackets end with 1 match between 2 players, then 2 matches and 4 player, and eventually for this tournament, 4096 matches between 8192 players. But since we dont have 8192 players, there will have to be BYEs which wont count as matches. In this case we'll have to use a 8192 single bracket, with the first 4096 players spread every other position then the last 1527 players spread evenly throughout the bracket and the remaining 2569 positions are BYEs (4096 + 1527 + 2569 = 8192). Here are how the rounds look like: A - 1527 matches, (4096 matches was suppose to happen, but 2569 BYEs are no counted) B - 2048 matches, C - 1024 matches, D - 512 matches, E - 256 matches, F - 128 matches, G - 64 matches, H - 32 matches, I - 16 matches, J - 8 matches, K - 4 matches L - 2 matches, M - 1 match From round B-M, its (2^12)-1 = 4095, so with Round A, its 4095+1527=5622. The calculated answer 5622 is one match less than the number of participants. However, just because its easy with single elimination to determine the number of matches, does not mean that it is what they initially asked, conversing with the interviewer for more details of the tournament is important. If the interviewer said it was a double elimination tournament then a player would have to lose twice in the bracket to be eliminated from the tournament. Depending on the number of players and the placement of the BYEs, then calculating the number of matches in a true double elimination maybe difficult. Also in Double Elimination, the winner maybe won by someone without a loss or with 1 loss, the winner without a loss means one less game. it is assumed that the competition is a head to head knockout competition like wimbledon. the only correct answer is 5,622. the quickest and smartest way to get that answer is to see that in a knockout tournament every body loses once and only once, except the winner. in every match, one person loses. therefore the number of matches required equals the number of players minus 1. PaulO, Jordan, madhur, simplebrain and key2success you are all hired! How many games are played? Well all of them of course, how else do you find the winner. It need only one game to find the winner If it is your game you can appoint a winner without playing any games. Then 0 is a possible answer. 1 is also a viable answer, if it is a game of life and death it is possible that no one lives then there are no winners on the first round. Such as a game that on the first round were everybody is exposed to a nuclear blast. Even those exposed to the fall out might be considered losers. A game like chess where you eliminate draw contestant then 1 round to 13 rounds would be required. You could divide by 2 to get the rounds or use logarithms to convert 2**13 which is greater than 5,623 to a log equation such as log(5,623)/log(2). Potentially everybody can loose on the first round because of the draw rule and the person with the bye on the first round can loose because they have no one to play to win. You can change the rules so that infinite rounds are required to determine a winner. One way to do this is to increase the elimination rounds so that it approaches infinity. As this goes on your interviewers glaze over and fall to sleep and when they wake up they decide not to give you the job. This can be poker tournament (as too many players). From 5-7 people - one wins. This can keep number of games to reasonable limit. Depends on how many rounds there are to determine a winner. Logical answer here could be 5623 Show More Responses 5,623 - each person plays, person with the highest score wins. There would be 5613 head-to-head games cosisting of 12 rounds with one team receiving a bye in each round except the fourth round, the tenth round, and, of course, the twelfth round. Assuming the tournament is Mortal Kombat everyone knows that earth realm has to win because out realm is evil and evil... Sucks. No games necessary. What kind of tournament? There will be 2 games. The first game is a question: Would you like to play a game? Which is then followed by the second game - one involving thrones. One 2 The simple answer is Number of Teams minus ONE. Simplified, a four team bracket plays 3 games. |

Number of 1's in binary representation of integer? 13 AnswersRun a loop, in which you binary-AND the integer with 1, and increment a counter, if the result is 1. Then right-shift the input-integer by 1 bit, and start over in the loop unsigned int ones(unsigned int number) { unsigned int n; for (n = 0; number != 0; number >> 1) { if (number & 1) { n++; } } return n; } unsigned int ones(unsigned int number) { unsigned int n; for (n = 0; number != 0; number >> 1) { if (number & 1) { n++; } } return n; } Show More Responses i dnt knw wheather it correct or not.....do correct me if im wrng a=0 q=n/2 r=n%2 n=q if(r=1)then a=a++ continue.... ct = 0; while (val) { ct++; val = val & (val - 1); } Several of the above work, but use preincrement public static int population(int x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); return x; } in C++, how about: do { sum += n&1; } while (n>>=1); int ones( ) { int n; int number = 1100110111; n = 0; while (number!=0) { int temp = number % 10; if(temp ==1 ) n++; number = number/10; } return n; } Lets consider 14(1110) is the number int CountOnes(int Number) { int n=0; while(number !=0) { if(number%2==1) n++; number >> 1; } return n; } The function takes an int and returns the number of Ones in binary representation public static int findOnes(int number) { if(number < 2) { if(number == 1) { count ++; } else { return 0; } } value = number % 2; if(number != 1 && value == 1) count ++; number /= 2; findOnes(number); return count; } All the answers above will not get you to amazon... try code the function with o(m), where m is the number of 1's in the binary representation of an integer. (hint: look up "Programming Interviews Exposed") int num = 31; int mask = 1; int counter = 0; while (num > mask ) { if ((num & mask) == mask) { counter++; } mask = mask << 1; } Console.Write(counter); Console.ReadKey(); |

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

Write a function Brackets(int n) that prints all combinations of well-formed brackets. For Brackets(3) the output would be ((())) (()()) (())() ()(()) ()()() 11 Answerspublic class Parenth2 { static int total = 3; static private void Brackets(String output, int open, int close, int pairs) { if ((open == pairs) && (close == pairs) && output.length() == total * 2) { System.out.println(output); } else { if (open < pairs) Brackets(output + "(", open + 1, close, pairs); if (close < open) Brackets(output + ")", open, close + 1, pairs); } } public static void main(String[] args) { Brackets("", 0, 0, total); } } You almost got thte answer, just a couple of errors... /* * To change this template, choose Tools | Templates * and open the template in the editor. */ /** * * @author Owner */ public class Parenth4 { static private void Brackets(String output, int open, int close, int pairs, boolean opened, boolean closed, int total) { if ((open == pairs) && (close == pairs) && output.length() == total * 2) { System.out.println(output); } else { if ((open < pairs)) Brackets(output + "(", open + 1, close, pairs,true, closed, total); if ((close < open)&& opened) Brackets(output + ")", open, close + 1, pairs,opened,closed, total); } } public static void Brackets(int total) { Brackets("", 0, 0, total,false,false, total); } public static void main(int number){ Brackets(number); } } This is a DP/memoization question, I believe. The base case is 0 and 1 bracket (the answer is empty or (). The recurrence is: bracket(n) = all combination of results from bracket(n-1) and from bracket (1) from bracket(n-2) and bracket(2) . . from bracket(1) and bracket(n-1) lastly, '(' . bracket(n-1) ')' The DP version of the above recurrence is straightforward. (Btw, this recurrence obviously will produce duplicate, but it's not hard to produce a modification that does not produce duplicate.) ;) Show More Responses Here is a F# implementation: let rec Br total output openp closep = if openp = total && closep = total then printfn "%s" output else if openp < total then Br total (output + "( ") (openp + 1) closep if closep < openp then Br total (output + " )") openp (closep + 1) let Brackets total = Br total "" 0 0 Brackets 5 let read = System.Console.ReadLine() void parens(int nPairs) { parens("", nPairs, nPairs); } void parens(string ans, int leftCount, int rightCount) { if (leftCount==0 && rightCount==0) { cout 0) { parens(ans+"(", leftCount-1, rightCount); } if (rightCount>leftCount) { parens(ans+")", leftCount, rightCount-1); } } To Remove duplicates simply use java Set :) public static String bracket(int a) { Set s = new TreeSet(); bracketIntern(s, a, "", ""); System.out.println(s); return s.toString(); } public static void bracketIntern(Set set,int a, String preFix,String suffix) { if(a == 1) { set.add(preFix+"()"+suffix); return; } bracketIntern(set, a-1, preFix+"()", suffix); bracketIntern(set, a-1, preFix+"(", ")"+suffix); bracketIntern(set, a-1, preFix, "()"+suffix); } I think you can also build a trie, and the traverse the trie to print out all the combinations. Complete python program to print the all combinations of well-formed brackets. How to calculate its Big-o? The recursive recurrence seems a little bit complicated. ---- def brackets(n): sol = [] li = [' ' for x in range(n*2)] def recu_brackets(opened, closed): if n - opened: li[opened + closed] = '(' recu_brackets(opened + 1, closed) if n - closed and opened > closed: li[opened + closed] = ')' recu_brackets(opened, closed + 1) if opened == n and closed == n: sol.append(''.join(li)) recu_brackets(0, 0) print ' '.join(sol) brackets(3) wasn't all that neat. o well public class MakeBrackets{ static List make(int number){ List list = new LinkedList(); if (number == 0) {list.add(""); return list;} if (number == 1) {list.add("()"); return list;} for (int i = 0; i < number; i++){ for (String item : make(i)){ for (String item2 : make(number - 1 - i)){ list.add("(" + item + ")" + item2); } } } return list; } public static void main(String[] args){ System.out.println(make(Integer.parseInt(args[0]))); } } def brackets(n): return bracketsPrefix("", n, n) def bracketsPrefix(prefix, opens, closes): total = 0 assert opensopens: total += bracketsPrefix(prefix+")", opens, closes-1) if opens>0: total += bracketsPrefix(prefix+"(", opens-1, closes) return total if __name__=="__main__": for i in range(6): n = brackets(i) print i,n x = raw_input("** ") This question gets so popular and I found this article has a really good explanation: https://goo.gl/E0m0EC |

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

Given an array of integers where each element points to the index of the next element how would you detect if there is a cycle in this array? 18 AnswersThe catch is to realize that if there is a cycle, it will result in an infinite loop What as the time and space complexity of the best solution? Can you do it in O(n) time and O(1) space? One possible solution is to keep a list for all visited positions. If we hit a position that is already in the list, we've detected a cycle. For this solution, time complexity is O(n) and space complexity is O(n). How to do this in O(n) time and O(1) space? Show More Responses use the contents of a position as an index into array and while traversing the contents, negate the contents after you visit it. if at any time you find the contents of a position as negative (given that every element points to the next element in array, you cannot have -ve numbers in array) this will run in o(n) with constant space e.g. array = [1,2,3,4,5,2] (zero based index) a[0]=1 go to a[1] and negate a[0] to -1 a[1]=2 go to a[2] and negate a[1] to -2 like this when you hit a[5] =2 and then you see a[2] = -3, which is already visited so there is a loop/cycle The problem is imprecisely stated. If every element a[i] contains a value that is an index into a (i.e. a value in the range 0..length(a)), then there *must* be at least 1 cycle, assuming a is of finite size. On the other hand, if a is allowed to contain values that are not valid indexes (negative, or >= length(a)), then it indeed takes some work to determine if a has cycles. So let's assume the latter. If a is allowed to contain negative values to start with, then the negate-as-you-see-it solution doesn't work. To determine if there is a cycle starting at any given element (isCycle(elemindex)) in O(1) space and O(n) time, you could walk 2 pointers starting at elemindex. One would go at normal speed (nextelem = a[thiselem]) and one would go at double speed (nextelem=a[a[thiselem]]). If the 2 pointers meet, isCycle() returns true. However, since you'd have to run isCycle(index) on every index to ask if there is a cycle *anywhere* in the array, this algorithm is O(n**2) in time. I'd have to ponder if there's an O(1) space / O(n) time algorithm for this... if the array is not "full," then it must contain sentinel values which represent NULL references. You could use Integer.MIN (in Java parlance) or just -a.length. this fixes the above criticism of the negate-as-you-see-it approach. What it doesn't fix is the fact that that the "graph" can be disconnected. for instance [1,2,NULL,4,5,1] a[0]->a[1]->a[2]->NULL a[3]->a[4]->a[5]->a[1]->a[2]->NULL in this case there are multiple references to element a[1], but it's not a cycle. I think you're stuck with the N^2 solution. Define two pointers One pointer move one step each time, The other pointer move two steps each time. If the pointers ever meet together (besides the start point) before one of the pointer reaches the end, then there is a loop. Otherwise, there isn't. This takes O(n) time and O(1) space. if there is a loop then that means that is a number repeated in the array. put the number in the array into a hashmap and compare the size of the hashmap to the size of the array. if less than there is a loop If you interpret the question strictly, then the answer is TRUE -- it always has a loop. Unless an element can point to nothing (with a negative index for instance) signaling that the iterator must terminate. How about incrementing a counter every time you follow a pointer and seeing if the final count is greater than the array length? If you've done more iterations than the array's length, that should indicate a cycle. Can some one explain the question ? If you have an array of integers then the ONLY interpretation of " ...each element points to the index of the next element" is the following array : a = [1,2,3,4,5,6,7 ...] . If that is the case - then what does it even mean to "have a cycle" ? Sort it and see if we have duplicates works too. Is that the full version of the question? The one I heard before said that we just have a limited memory resource. But because my version and the one mentioned above don't prohibit us to modify the given data, so I think we just need one variable and one pointer for this question. We assign the value of the first element in the array provided to our variable and pointer. Then we jump to the next element in the array and check if the value of that element is equal to the one in our variable. If not, assign the value of that element to the pointer and then change that value to the one we have in the variable. Jump to the next element by using the pointer and continue to do the same task like what we do with the previous element. The program will alert an infinite loop when it found there is an element with the same value in the variable. Show More Responses Multiple approaches are possible. If space of O(n) is allowed, add all pointers to a Set. If set size is less than array size, there is a cycle. If linear time and constant space is desired, start 2 pointers at index 0, First pointer is incremented by 1 index, second incremented by 2 indices. If end is reached by either pointer, no cycle. If fast pointer '.next' is every slow pointer, there is a cycle. public void detectCycle(int[] arr,int n){ int slow=0,fast=arr[arr[slow]]; boolean flag=false; while(fast=n) System.out.println("Cycle not present in arr"); } "turn" & check the first The question is not clear . If each element's value is the next element's index then there'd be no cycle as mentioned above. I like the sets solution in terms of simplicity. To add to the possible solutions I propose hashing each index encountered with the value being the number of occurrences. Each time update the value of a key if it is already a 1 we've found a cycle. This should be O(n) for both time and space complexity. One doubt I have with the fast/slow double pointer solution is the assumption that the existence of a cycle has to send the fast pointer back exactly to where it eventually meets the slow pointer. In situations where this isn't true an additional condition should be if the slow pointer reaches the end before the fast. If an array starts at index 0 and it has value 2. If the index 2 has value 1 and index 1 has value 0. Then it would be cyclic array. Because it starts and ends in the same index 0. |

Implement a power function to raise a double to an int power, including negative powers. 11 AnswersCould be implemented many ways. I got the feeling that the interviewer wanted to see you approach the problem in multiple ways and demonstrate confidence in your math and recursive skills. #include #include #define MAX_ARRAY_LENGTH 256 double power(double, unsigned int); int main(int argc, char** argv) { double a = atof(argv[1]); int b = atoi(argv[2]); double result = power(a, b >> 31 == 0 ? b : -b); if ((unsigned int) b >> 31 == 1) { result = 1 / result; } printf("%f\n", result); return 0; } double power(double a, unsigned int b) { switch (b) { case 0: return 1.0; case 1: return a; default: return (b & 1) == 0 ? power(a * a, b >> 1) : power(a * a, b >> 1) * a; } } c implementation of the above (no recursion): int ipow(int base, int exp){ int result = 1; while(exp){ if(exp & 1) { result *= exp; } exp >>= 1; base *= base; } return result; } Show More Responses int power(double n, int exp) { bool npower = (exp < 0) ? true : false; double result = 1; exp = abs(exp); // get the absolute value for (int i = 0; i < exp; i++) { if (npower) { result = result/n; } else { result = result*n; } } return result; } C# code verified: static double Power(double d, int exp) { if (d == 0 || exp == 0) { if (exp >= 0) { return 1; } else { return double.PositiveInfinity; } } int expAbs = Math.Abs(exp); double res = d; for (int i = 1; i 0) ? (res) : (1 / res); } double power(double x, int y) { if(y == 0) return 1; int sign = 1; if(y < 0) sign = -1; y = abs(y); double d = power(x, y/2); if(y%2 == 0) d = d*d; else d = x*d*d; if(sign == -1) return 1.0/d; else return d; } I am surprised that not a single person here had noticed that the guy asked to raise a DOUBLE to a given power. Men, double are not integers. Their exponent is stored in a part of their binary representation. If you multiply n times a double you will make n times a rounding error and n useless calculations. Just changed the binary part of the double that is related to its exponent, and here it is, your double has been raised to a given power, a you absolutely lost no precision, and you've made 0 calculations. This is basic stuff, every university teaches that to its students... floating numbers representation... I believe interviewer is expecting for this public static double Power(double x, int y) { double result = 1; bool isNegative = y 0) { if ((y & 1) > 0) { result *= x; } y = (y >> 1); x *= x; } if (isNegative) result = 1 / result; return result; } Verified C# static double Pow(double b, double exp) { if (exp == 0) return 1; else if (exp > 0) return b * Pow(b, exp - 1); else return 1 / Pow(b, -exp); } Does it get more compact? TD's answer is interesting, but not very useful. If you actually try it you'll find that since the double's base is 2, any changes to the exponent portion approximately multiply (or divide) numbers by a power of two. I say approximately here, since TD forgot to mention that the number itself isn't stored in float point numbers, only the digits after the implied 1. So yes, it's important to know how floating point numbers work, but modifying the exponent portion of a floating point number is a fundamentally incorrect solution. public double power(double num, int exp) { if(exp == 0) return 1; double res = 1; for(int e=Math.abs(exp);e>0;num*=num,e>>=1) { if( (e&1) == 1) res *= num; } return (exp>0)?res:1.0/res; } |

### Software Engineer at Dropbox was asked...

Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient 15 AnswersShould do a running sum, storing previous sum values in a hash table along with array index if you ever get a sum value you’ve already seen, return the array indices (1+the index in the hash table, and the current index) This solution is O(n) Although the above algorithm runs in O(N) time, will it cover all cases? What about if the input array is [1,2,1,-3,-4]? In this case, the subsequence would be [2,1,-3]. I feel though that the algorithm described above will miss this subsequence since you are only keeping a running sum from the start of the array. Do you mean a subsequence (can be discontinue) or a sub array (continue)? Show More Responses Yes, the solution by Interview Candidate (do a running sum and return when you see a sum already seen) works for all cases. If the list is [1, 2, 1, -3, -4], S1 = 1; S2 = 3 (1 + 2); S3 = 4 (1 + 2 + 1) S4 = 1 (1 + 2 + 1 -3) ... since we have already seen this sum at index 1. the answer is list of numbers at [old_sums_index + 1, new_sums_index] = [2, 1, -3] [100 7 1 2 -3] the above method will not work for this array, It will work for [100 7 1 2 -3]. Index: 0, Sum = 100 (put in hashtable) Index: 1, Sum = 100 + 7 = 107 (put in hashtable) Index: 2, Sum = 107 + 1 = 108 (put in hashtable) Index: 3, Sum = 108 + 2 = 110 (put in hashtable) Index: 4, Sum = 110 + (-3) = 107 107 already exists in hashtable with index = 1. Hence we return (1+1, current index) meaning (2, 4) Doesn't work for [-1,-1,-3,4]. This looks like a classical NP-complete problem: http://en.wikipedia.org/wiki/Subset_sum_problem. And generating all sub sequences is not O(n^2) but O(n!) which is the cost to generate all permutations. It works for [-1 -1 -3 4] too. The subset sum problem allows discontinuous subsets, but this question asks for a subsequence implying no discontinuity. Here is a solution using Python 3: def findZeroSequence(list): hash = {} sum = 0 startIndex = -1 hash[sum] = startIndex # a sum of zero later in the list means the sequence starts at index 0 (== -1 + 1) for i, v in enumerate(list): sum = sum + v # print(i, ' has sum ', sum) try: startIndex = hash[sum] return list[startIndex+1:i+1] except KeyError: hash[sum] = i return [] # no subsequence print(findZeroSequence([1,2,-3,1])) print(findZeroSequence([1,2,1,-3,-4])) print(findZeroSequence([-1,-1,-3,4])) print(findZeroSequence([100, 7, 1, 2, -3])) print(findZeroSequence([-7, -3, -2, 5, 8])) Checking every sub-sequence is O(2^n) not O(n!), which is the cost for generating all subsets. Contrary to what the previous poster said, sub-sequence implies both continuity and discontinuity: http://en.wikipedia.org/wiki/Subsequence and the algorithm fails for this case: [2, 2, 1, -4]. How about these: [1,2,-3,4] or [-3,3,1] ? May be user should check for zero also? def hasSubSeqOfZero(a): if not a: return [] partialSums = {} partSum = 0 for i in range(len(a)): partSum += a[i] if (partSum in partialSums): return a[partialSums[partSum] + 1: i + 1] if (partSum == 0): return a[:i+1] partialSums[partSum] = i return [] Show More Responses public int[] ssz(int[] nums) { if (nums == null || nums.length == 0) return null; Map map = new HashMap(); int sum = 0; int index = 0; for (int n : nums) { if (n == 0) return new int[] { index, index }; sum += n; if (map.containsKey(sum)) { return new int[] { map.get(sum) + 1, index }; } map.put(sum, index); index++; } return null; } Check out this Dropbox employee's profile. It looks like you can get some info about the interview from them. https://www.rooftopslushie.com/profile/whodis |

### Software Development Engineer at Amazon was asked...

Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function). 9 AnswersI came up with a recursive solution something like this: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if (node != null) { if (node.left != null && node.left > max || node.right != null && node.right < min) { return false; } else { return (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)); } } else { return false; } } How come this function never returns true? And why would you need min and max? Ok, so I should have spent a little more time posting this (I was admittedly rushing through it so I could get access to more questions/answers). Here's a revised version that should hopefully make more sense: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if(node == null) { return true; } if(node.value > min && node.value < max && IsValidBST(node.left, min, node.value) && IsValidBST(node.right, node.value, max)) { return true; } else { return false; } } The main change is that I decided to avoid checking the children of the tree in the body, and leave it to recursion to take care of that. Thus, we just have to look at the current "node" and that's it... the constraints will be handled by passing min and max down. @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. Finally, the min and max values are required because a BST requires that each value in the left branch be smaller than ALL parent values on that branch (and similarly for those on the right branch being larger). Another way of saying this is that the entire left tree of any node must be smaller than the node's value, and the entire right tree must be larger than the node's value. Thus, in a recursive solution, you have to have a way to pass down the upper and lower bounds to the lower levels of the tree, otherwise the third level won't be able to check whether it's smaller/larger than the root two levels up. That's why we pass down the min and max values. Hope this helps. Show More Responses boolean isBST(TreeNode node) { if(node.isLeafNode( )) return true; else { if(node.value node.rightChild) return false; else return (isBST(node.leftChild) && isBST(node.rightChild)) } } traverse in order and see if they r same @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. ============= Those are just two function calls and the function never returns true. Alexander is right - you are missing a terminating clause in your recursion. Forgot to add - your second solution is correct since it returns true. // For +ve number OR use INT_MIN instead of -1(s) bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin rightMax ? leftMax : rightMax; return true; } // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } |

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

Given a string, remove all the duplicate characters (not necessarily consecutive) 9 Answersvoid removeDuplicates(char *in, char *out) { bool seen[NUM_CHARS] = {false}; while (*p != 0) { if (seen[*p] == 0) { *out++ = *p; } seen[*p] = true; } } public class StringRemove { private final String baseString = "abcdefghijklmnopqrstuvwxyz12345678910"; private final List finalMap = new ArrayList(); private StringBuffer sb = new StringBuffer(); private void findDup(){ for(int i=1 ; i <= baseString.length() ; i++) { String sLocal = baseString.substring(i-1, i); if(finalMap.contains(sLocal)){ finalMap.remove(sLocal); }else{ finalMap.add(sLocal); } } String s = finalMap.toString(); s = s.replace('[',' ').replace(']',' ').replace(',', ' ').replace(',', ' ').trim().replaceAll(" ", ""); System.out.println(s); } public static void main(String s[]){ StringRemove sr = new StringRemove(); sr.findDup(); } void RemoveDuplicates(char[] arr, int length) { Map charMap = new Map(); int currenPosition = 0; for (int i=0;i Show More Responses to the last two - just use a boolean array instead of a map or list like Interview Candidate public class Duplicates { public static String removeDuplicates(String str){ int[] chars = new int[26]; StringBuffer sb = new StringBuffer(); for(int i = 0; i < str.length(); i++){ int val = (int)str.charAt(i)-97; if(chars[val]==0){ chars[val]=1; sb.append(str.charAt(i)); } } return sb.toString(); } public static void main(String[] args){ String res = removeDuplicates("faaabook"); System.out.println(res); } } each char has ASCII code number, so just XOR all those numbers together, duplicates will eliminate each other. void remove_duplicate(char * str, int len) { bool appeared[NUM_CHARS]; memset(appeared, 0, sizeof(appeared)); int i = 0, j=0; while(i < n) { if(!appeared[str[i]]) { str[j] = str[i]; j ++; appeared[str[i]] = true; } i ++; } str[j] = '\0'; } store each characted in hashset and them combine I mean combine them |

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

(a) first, write a function to calculate the hamming distance between two binary numbers (b) write a function that takes a list of binary numbers and returns the sum of the hamming distances for each pair (c) find a solution for (b) that works in O(n) time. 10 Answers(for question 1) public static String addBinaryStrings(String a, String b) { if ((null == a) || (null == b)) return null; return int2bstring(bstring2int(a) + bstring2int(b)); } public static int bstring2int(String a) { int sum = 0; int multiplier = 1; while (a.length() > 0) { String lastChar = a.substring(a.length()-2, a.length()); if (lastChar.equals("1")) sum += multiplier; multiplier *= 2; a = a.substring(0, a.length()-1); } return sum; } public static String int2bstring(int i) { if (0 == i) return "0"; String s = ""; while (i > 0) { if ((i % 2) == 0) { s = "1" + s; } else { s = "0" + s; } i /= 2; } return s; } (for question 2) public static int hammingDistance(String a, String b) { int numDigits = Math.max(a.length(), b.length()); int numDiff = 0; for (int i = 0; i < numDigits; i++) { String ithDigitA = extractDigit(a, i, numDigits); String ithDigitB = extractDigit(b, i, numDigits); if (!ithDigitA.equals(ithDigitB)) numDiff++; } return numDiff; } public static String extractDigit(String a, int i, int n) { if (i < n - a.length()) return "0"; return a.substring(i-n+a.length(), i-n+a.length()+1); } public static int setHamming(String[] a) { int numDiff = 0; int numDigits = 0; for (int i = 0; i < a.length; i++) { numDigits = Math.max(numDigits, i); } for (int i = 0; i < numDigits; i++) { int num0s = 0; int num1s = 0; for (String aa : a) { String ithDigitAA = extractDigit(aa, i, numDigits); if (ithDigitAA.equals("0")) { num0s++; } else { num1s++; } } numDiff += (num0s * num1s); } return numDiff; } A: int distance( int num1, int num2 ) { int distance; while( num1 != 0 && num2 != 0 ) { distance += num1&1!=num2&1; num1=num1>>1; num2=num2>>1; } return distance; } B: int distanceSum( std::vector nums ) { std::unordered_map digits; for( auto& num : nums ) { int digit = 1; while( num != 0 ) { digits[digit]+=num&1; num = num>>1; digit++; } } int distanceSum = 0; for( auto& p : digits ) { distanceSum += nums.length()-p.second; } return distanceSum; } Show More Responses for Problem C: /** * This solution is O(n) *I wrote it this way so its easier to be understood. **/ public int getHammingTotalFromBinaryNumbersList(List binaryNumbers){ Map binaryCounter = new HashMap; // Key is the _[1 or 0] on the binary number, so if you're at position 1, and you get 0, the key will be 0_1 String positionKey; int totalCount; int maxPosition = 0; foreach(String binaryNumber in binaryNumbers){ if(binaryNumber.Length-1 > maxPosition){ maxPosition = binaryNumber.Length-1; } for(i = 0; i 10001 10101 int GetHammingDistance(string s1, string s2) { Debug.Assert(s1.Length == s2.Length); int distance = 0; for(int i=0; i input, int n, out List distances) { if(n==2) { distances.Add(GetHammingDistance(input[0], input[1])); } for(int i=0; i {XY} GetAllPairsHammingDistance(zyx, 2, "")=> {XY, ZY} GetAllPairsHammingDistance(zxy, 2, "")=> {XY, ZY, ZX} XYZ 0 1 2 = 3 X Y Z | | | 0 1 | Y | |_ 0 1 = 2 Y Z | | | |_Z |_Y Problem 1. Add two binary numbers represented as ASCII strings with result also in form of an ASCII string // // Add two binary strings, the solution as follows: // 1) convert binary strings to unsigned integers // 2) Add resulting integers // 3) Convert the result back to binary string // 4) Reverse the string to obtain the resulting string // // // Convert binary ASCII string to unsigned integer by successive divide by 2 // uint binStr_to_uint(const char *pStr, int *size) { char *pEnd = pStr; uint num = 0; while(*pEnd) num = (num >= 1; //divide by 2 } *pStr = 0; //terminate the string } // Reverse a string void reverseString(char *pStr) { char *pEnd = pStr; while(*pEnd++) ; pEnd -= 2; //point to last string char char *pTmp; while(pStr size2 ? size1 : size2; char *pResult = malloc(sizeRes + 2); //add space for carry and EOS if(pResult == 0) return 0; uint_to_binStr(num2, pResult); reverseString(pResult); return (pResult); } Problem 2. Find Humming distance between two numbers. The problem did not specify what format the numbers are in, so I assumed unsigned integers. // // Find Humming distance // int hummingDistnce(uint num1, uint num2) { num1 = num1 ^ num2; //Humming distance is simply an XOR num2 = 0; while(num1) { ++num2; //count '1' bits num1 &= num1 - 1; } return num2; } The second part of the problem is simple, just traverse the list selecting pairs of numbers and call hummingDistance() function each time. Corrections to my previous example: // Convert binary ASCII string to unsigned integer by successive divide by 2 should say ....multiply by 2 instead of divide by 2 Another minor error fix, function uint_to_binStr(uint num) definition should also have a pointer to char parameter like below: void uint_to_binStr(uint num, char *pStr) Third correction, In function reverseString(), the temporary char variable should be defined as "char tmp;" instead of "char *pTmp", so the code block should be: char tmp; while(pStr < pEnd) { tmp = *pEnd; *pEnd-- = *pStr; *pStr++ = tmp; public static int hammingDistance(int a, int b) { int xor = a ^ b; int distance = 0; while (xor > 0) { xor = (xor - 1) & xor; distance++; } return distance; } public static int hammingDistance(int[] array) { int sum = 0; for (int i=0; i<32; i++) { int mask = 1 << i; int num0s = 0; int num1s = 0; for (int value : array) { if ((value & mask) != 0) { num1s++; } else { num0s++; } } sum += num0s * num1s; } return sum; } |

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

Print a singly-linked list backwards, in constant space and linear time. 10 AnswersOne can create a function that takes a node as an argument and checks whether the next of the passed node is NULL or not.In case it is not NULL,the same function is again called for the NEXT node.if the Next of the passed node is NULL,the function prints the value of the node and returns. void f1(node* p) { if(p->next!= NULL) { f1(p->next) } else { print ("%d",p->value); } } Arpit, that's not constant space, that's linear (stack) space, since you will have as many function calls waiting to be returned on the stack as there are nodes. The trick is to reverse the list first (constant space, linear time when done iteratively or tail-recursively) then print it in order (against constant space, linear time). void f1(LinkedListNode lln) { if(lln.next != null) f1(lln.next); System.out.print(lln.value); } Show More Responses Bobby, that is not constant space because it uses O(N) stack space. There are obvoius O(N^2)-time O(1)-space algorithms, and obvious O(N) time O(N) space algorithms. This is my best guess. Assuming you have exclusive access to the list, you can reverse it, walk it, and then reverse it again. Something like this: #include #include struct node { int value; struct node * next; }; void print_backwards( node * head ) { node * prev = NULL; node * cur = head; node * next; while( cur ) { next = cur->next; cur->next = prev; prev = cur; cur = next; } cur = prev; prev = NULL; while( cur ) { printf( "%d\n", cur->value ); next = cur->next; cur->next = prev; prev = cur; cur = next; } assert( prev == head ); } main() { node a, b, c; a.value = 1; a.next = &b; b.value = 2; b.next = &c; c.value = 3; c.next = NULL; print_backwards( &a ); } Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. Reverse the list, print, then reverse it back. 3 O(n) operations = O(n). O(1) space used. void BWDisplayLinkedList(node* pHead) { if(!pHead) return; BWDisplayLinkedList(pHead->next); cout data "; } Does this work well? Reverse a list, print it, and then reverse it again. struct node *reverse(struct node *oldlist) { struct node *newlist = NULL; while(oldlist!=NULL) { struct node *temp = oldlist; oldlist=oldlist->next; temp->next=newlist; newlist=temp; } return newlist; } void display(struct node **q) { struct node *temp; temp = *q; if(*q==NULL) { printf("List is empty\n\n"); } else { while(temp!=NULL) { printf("%d=>",temp->data); temp=temp->next; } printf("||\n\n"); } } //p is our list p = reverse(p); display(&p); p = reverse(p); Thanks to recursion :) void print_backward(node* n) { if(n == NULL) return; print_backward(n->nxt); cout val << endl; } Yes recursion does the job in linear and constant time. :-) |