# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

### Data Scientist Intern at LinkedIn was asked...

Find the second largest element in a Binary Search Tree 16 Answersfind the right most element. If this is a right node with no children, return its parent. if this is not, return the largest element of its left child. One addition is the situation where the tree has no right branch (root is largest). In this special case, it does not have a parent. So it's better to keep track of parent and current pointers, if different, the original method by the candidate works well, if the same (which means the root situation), find the largest of its left branch. if (root == null || (!root.hasRightChild() ) { return null;} else return findSecondGreatest(root, root.getValue()); value findSecondGreatest(Node curr, value oldValue) { if(curr.hasRightChild()) { return (findSecondGreatest( curr.getRightChild(), curr.value)); } else return oldValue; } Show More Responses Above answer is wrong. it has to be something like this. public static int findSecondLargest(Node node) { Node secondLargest = null; Node parent = null; Node child = node; if (node!=null && (node.hasLeftChild()||node.hasRightChild())) { if (node.hasRightChild()) { while (child.hasRightChild()) { parent = child; child = child.rightChild(); } secondLargest = parent; } else if (node.hasLeftChild()) { child = node.leftChild(); while (child.hasRightChild()) { child = child.rightChild(); } secondLargest = child; } } return secondLargest; } The above answer is also wrong; Node findSceondLargest(Node root) { // If tree is null or is single node only, return null (no second largest) if (root==null || (root.left==null && root.right==null)) return null; Node parent = null, child = root; // find the right most child while (child.right!=null) { parent = child; child = child.right; } // if the right most child has no left child, then it's parent is second largest if (child.left==null) return parent; // otherwise, return left child's rightmost child as second largest child = child.left; while (child.right!=null) child = child.right; return child; } Soln by "mindpower" works. Thank you. I am trying to solve a similar problem Find the 2nd nearest high(in in-order traversal) value for a given node Eg: Given nums: 12 7 14 3, construct a BST. If the given value is: 7 then we should return 14 (in the sort order: 3, 7, 12, 14) if the given value is: 3 then we should return 12 (in the sort order: 3, 7, 12, 14) Generic solution in C# for any k. Notice that this example can be easily changed to find the k-th smallest node by doing a depth-first recursion on root.Left first, and then a tail recursion on root.Right. public Node GetKthLargest(int k) { return GetKthLargest(ref k, this.Root); } Node GetKthLargest(ref int k, Node root) { if (root == null || k < 1) return null; var node = GetKthLargest(ref k, root.Right); if (node != null) return node; if (--k == 0) return root; return GetKthLargest(ref k, root.Left); } recursion is not needed. SecondLargest(Node root, Node secondLarge) { if(root.right==null) return root.left; Node secondLargest = root; while(secondLargest.right.right==null) secondLargest=secondLargest.right; return secondLargest; } int getmax(node *root) { if(root->right == NULL) { return root->d; } return getmax(root->right); } int secondmax(node *root) { if(root == NULL) { return -1; } if(root->right == NULL && root->left != NULL) { return getmax(root->left); } if(root->right != NULL) { if(root->right->right == NULL && root->right->left == NULL) { return root->d; } } return secondmax(root->right); } In-order traverse the tree. The second last element in the array in the answer. In Python: def find_second_largest_bst_element(root, parent=None): if parent is None: # BST root if root.right is None: # no right subtree if root.left is not None: # if a left subtree exists... return root.left else: # root is the only element of the BST return False else: if root.right is None: # right-most element if root.left is not None: # left subtree exists return root.left else: # leaf return parent else: # check right subtree find_second_largest_bst_element(root.right, root) find_second_largest_bst_element(root) For kth smallest, descend the left subtree first. class Node: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def findKthLargest(root, k): global count if root is None: return findKthLargest(root.right, k) count += 1 if count == k: print root.value return findKthLargest(root.left, k) count = 0 r = Node(10, Node(5, Node(2), Node(7)), Node(30, Node(22), Node(32))) findKthLargest(r, 3) // solution in java // main routine Node findSecondMax(Node root) { if(root == null || (root.left == null && root.right == null) return null; else { Node max = findMax(root); return (max.parent == null) ? findMax(max.left) : max.parent; } } //helper routine, recursive implementation.... can also be done non-recursively Node findMax(Node root) { return (root.right == null) ? root : findMax(root.right); } Show More Responses Find the largest number in the binary tree and delete it. And again find the largest number. Short and fast. Reverse in-order traversal of the BST, keeping a count of # of visited nodes. This methods works great to return the kth largest element in a BST. mindpower's solution looks right |

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 |

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

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

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

Number of 1's in binary representation of integer? 12 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") |

### 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? 15 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"); } |

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

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 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; } |