# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

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

Considering a 2-dimension matrix that can only be traversed by 1 adjacent position at a time and never diagonally. Create an algorithm to traverse that matrix from its upper-left corner to its lower-right corner using the shorter possible path in the most efficient way. 6 AnswersThis is a very interesting problem. Although I knew immediately that I had to use recursion to effectively traverse the matrix and eventually got a working algorithm, the catch to make the algorithm much more efficient is to traverse the matrix backwards. How back traverse make the algo efficient? Why not just go all the way down then all the way right? Without diagonal moves the path length is fixed. Unless they provide a different definition for 'shortest length' Show More Responses For a thinking outside the box answer.... assuming the set is closed for indexing, go up -1 and left -1. I guess it's the traversal of a graph's depth first search (DFS) using Adjascent matrix... it is similar to two way BFS. Start from top left and bottom right and then keep moving until they meet. |

Write a function in Java that will take a sorted array of ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation. 5 Answerscreate temp array; starting from the second element copy the i'th char if input[i-1] != input[i] return temp oh efficiency is O(n) you can't create a temp array because you don't know the size until after you process. you could count the number of dupes in one pass, then allocate the array, then do the compacting. or you could allocate the array equal to the size of the original and accept that some elements will be null (or -1, or whatever). or you could use some dynamic data structure like an ArrayList to build the compacted list and convert it to an array at the end (ArrayList.toArray(...)). regardless, it's still O(n) and uses 2x the memory. makes me think there's a more elegant solution though. Show More Responses do bitwise XOR of consecutive numbers. When the xor is 0, you know the number is duplicate. It will require single pass thru the array to identify number of duplicates in the array. you can also use 2 index, at the beginning they both = 0, then you will have a previous and a next, if previous value = next value increment next index until next value != previous value then increment previous index by 1 and assign "next value" to it and so forth until you "next index reach the end of the array and then increment all previous index assigning null or -1. O(n) without using 2x memory. Anyway, I hope it is not too confusing, its late but I hope you got the big picture. |

Write an algorithm to verify if a tree is a binary search tree. 5 AnswersBST(Node * p) { if (p==null) return false; if(p->left! null& p->dataleft) return false if(p->right&&p->data>=max(p->right)) return false if(!BST(p->left) && BST(p->right)) return true return false; } This solution is wrong. if (p==null) return false; - Why is this false? isBST(node n) if(n.left == null || n.right == null) return true; if(n.left.val < n.right.val) return isBST(n.left) && isBST(n.right) else return false; Show More Responses This solution is also false. It's going to return true if there is no right node and the left node is greater than the parent. It's basically right, and is a simple fix to change that, so I'll leave it to the reader as an exercise. :) Assume that we have a binary search tree like this: RootNode has value 6. RootNode->LeftChild has value 3. RootNode->LeftChild->LeftChild has value 2. RootNode->LeftChild->RightChild has value 7. We know that in a binary tree 1.all nodes' values which are at left side of a node must be less than Node's value. 2.all nodes' values which are at right side of a node must be greater than Node's value. In anonymous algorithm it does not check: 1. if node's left child's value is less than node's value && node's right child's value is greater than node's value 2. node's all left childrens' values must be less than node's value. |

Suppose you have 100 GB of data that you want to sort, but you only have 1 GB of memory. How would you sort this data? 8 AnswersHint: This isn't really a difficult question (just was an unexpected one for me). You don't really need to know the answer to figure this out. As it turns out, the obvious thing actually works here (and it is a known sorting algorithm). Can you expand on this? What is sorting algorithm? Sorting algorithm = a computer algorithm to sort a list of objects. Well pretend you just have 2 GB of data (for simplicity, assume they are integers) and 1 GB of memory, since the technique is the same. And pretend you want to sort these integers in increasing order. What would you do? Like, what's the first idea that comes to your mind? Show More Responses You do an on disk merge sort, bring chunks in to memory and sort using quick sort, then had the sorted data in to buckets (files). When your done merge them using a merge sort. Yep, exactly. External sort bucket sort. Sort each bucket, then merge. Mark |

### Software Engineer at TripAdvisor was asked...

Write a program that given 4 coin denominations and a dollar amount finds the best way to express that amount using the coins given. I.e. you have coins with denominations of 1c, 7c, 13c,19c and you have to express $2.12 with the least number of coins. There is always a 1c coin but the other 3 are arbitrary. 6 AnswersTurns out , this problem only has an elegant solution when the coin denominations are divisible by each other, such as the US coins (1, 5, 10, 25). Otherwise, it requires a (slightly optimized) brute force algorithm. I was told so by the interviewer after struggling with it using different approaches for about 40 minutes. If you have a coin of value 1, you can use a greedy algorithm: always select the most valued coin, until you have less money left that this value. Remove the coin, try again with less coins and the money left. Otherwise, just bruteforce and memoization, to implement a simple dynamic programming approach where you want to minimize the number of coins used, caching on the amount of money left to divide. Greedy algorithm is not right at all for general cases. This is a very classical questioin. If you fail on this question, I would say that it is probably your fault. Show More Responses In all my years of giving and receiving interview questions I have never seen this one. It is definitely NOT a classical programming problem. Asking whether a candidate knows of an obscure academic puzzle does not sound like a good interview question. int main() { int currency[] = {19,13,7,1}; int money = 212; int i=0; int div=0; while (money>0) { div = money/currency[i]; money = money%currency[i]; if(div>0) { cout It is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics. |

Consider an X x Y array of 1's and 0s. The X axis represents "influences" meaning that X influences Y. So, for example, if $array[3,7] is 1 that means that 3 influences 7. An "influencer" is someone who influences every other person, but is not influenced by any other member. Given such an array, write a function to determine whether or not an "influencer" exists in the array. 12 AnswersThis was a tough one that forces you to consider how best to traverse the array and eliminate possibilities as soon as possible. Not_Influencers[n] = 0; //Make all elements 0 for (i = 0 ; i< n ; i++){ if(Not_Influencers[i] == 1) continue; row_sum = find_row_sum(a[i]); if(row_sum == n-1 && find_col_sum(i) == 0) return Found; for(j = i; j < i; j++) if (a[j] == 1) Not_Influencers[j] = 1; } X should be equal to Y, right? Show More Responses //if vec[i][j] == 0 then i is not an influence //if vec[i][j] == 1 then j is not an influence //so time complexity is O(n) bool find_influences(vector > &vec) { int n = vec.size(); vector not_influence(n); for (int i = 0; i = 0; --j) { if (!vec[i][j]) { break; } not_influence[j] = 1; } if (j < 0) { return true; } } not_influence[i] = 1; } return false; } Run a BFS or DFS. For each node keep going to influencer. Find a node which can be reach by all nodes. Sort of finding sink node. public static int influencer(final int[][] jobs, final int r, final int c) { int[] degree_in = new int[jobs.length]; int[] degree_out = new int[jobs.length]; for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { if(jobs[i][j] == 1) { // i influences j degree_out[i]++; degree_in[j]++; } } } for (int i = 0; i < r; ++i) { if (degree_out[i] == r - 1 && degree_in[i] == 0) { return i; } } return -1; } Consider the input as Graph given in adjaceny matrix representation. Find whether a semi-eulerian path is present in the graph or not. Take the XOR product of the original matrix with the transposed matrix and sum by row. If any row counts equal the rank then they are influencers. private static boolean hasInfluencer(int[][] matrix) { if (matrix == null) return false; if (matrix.length == 0) return false; boolean result = false; for (int i=0; i the XOR suggestion I think is incomplete. The condition sum(row_influencer) = 1 and sum(column_influencer) = N so a simple matrix multiplication with the transposed should give for the vector v[influencer] = N and v[N-influencer] = 1. I assume influencer influences himself. def find_influencer(matrix): for row in range(len(matrix)): following_none = not any(matrix[row]) if not following_none: continue all_following = True for r_no in range(len(matrix)): if not row == r_no: continue if not matrix[r_no][row]: all_following = False break if all_following: return row return -1 Here is a different view. Please comment if you find any issues with the logic. 1st. condition: An influencer can not be influenced by any one. Let's say the in a matrix of [x.y], there is an influencer with index 2. So, the column=2 (3rd column) in the matrix must be all 0s, since the influencer can not be influenced. Step 1: Find a column with all 0s. If found, remember the column index or there is no influencer. Let's say, it is m Second condition: An influencer must have influenced everyone. So, in our example: row=2 (third row) must be all 1s except for column=2, since influencer can not even influence self. Step 2: Check row=m and find that all values are 1 except for [m][m]. If found, we have an influencer. |

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

Given a set of people, one of them is a celebrity. You have a 2D array which describes which people know each other, that is [N, M] is true if N knows M. The celebrity will not know anyone (except them self) and everyone will know the celebrity. Find an order N algorithm to find the celebrity. 7 AnswersDon't think there is an O(n), but O(n*m) yes. The key here is that the celebrity knows nobody AND everybody knows the celebrity. So for each iteration, you can rule out 1 person. [Notation: A->B -- A knows B] If A->B then A is not the celebrity .. rule out A Next check would skip B->A since we don't care if B->A etc It is not so simple. You can construct a matrix of relationships to defeat this algorithm. For example, start with A knows B. Then check if B knows C, and say answer is false. Then check B -> D, answer is false. And so on. That's O(N) operations. B looks like a good candidate. But then you check B-> A, you get true, so after all that work B is ruled out. Need to examine C now. Same thing. You end up checking perhaps half of all possible pairs, that's O(N^2). Show More Responses How about constructing a graph with edges between who know each other.. and then checking if target is reachable.. http://courses.cs.vt.edu/~cs5114/spring2010/notes.pdf Please correct me if I've made some incorrect assumptions here. It seems like the matrix is an adjacency matrix, so M is always equal to N. The solution is to follow the diagonal. If A is the celebrity then following are the patterns possible along the diagonal. If A is the first element in the matrix, i.e. i=0 and j=0 then [0,0] = 1, [0,1]=0, [1,1]=1, [1,0]=1. If A is the last element in the matrix, i.e. i=M and j=M then [M,M]=1, [M-1,M-1]=1,[M,M-1]=0,[M-1,M]=1 The third case is when A is an element somewhere other than the above cases. In this case, you're looking for the following pattern [i,j]=1,[i-1,j]=1,[I+1,j]=1,[i,j+1]=0,[i-1,j]=0. Looking at the time complexity, it is going to be a tad higher than O(N) but certainly not O(M^2). Traverse the MxN matrix to find all the row, column pair whose value is 1 (true), Create a separate 2d array with [row col]. Now iterate the rows of this array by reversing the column values and checking if their value is 0 then we can say that row,col pair is a celebrity. |

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

Given a set of non-overlapping integer ranges (1,3) (5,8), etc., and an input integer, what is the best way to organize the data and allow for quick search based on the input, etc. 5 AnswersProbably a BST or a balanced tree of some kind Some sort of a balanced tree would be optimal. Each tree node represents a an interval. We just need to define the less than, equal to operators. Less than is simply defined if the value x you are searching for is less than the beginning of the interval in the node. Equals is if x is within the interval. BST is more than enough given the non overlap. Also defining the less operator would be good. Show More Responses Interval search tree. It's made exactly for this purpose. Why not just sort the ranges based on the lower key. and for each query, just perform a binary search, always find answers in O(lgn). |

### Software Engineer at AppNexus was asked...

You have an analog clock with two hands, one for the hour and one for the minute. Given a time of the day, what is the angle between the two hands? 5 AnswersThe easiest way is to have the angle of each hand between midnight and the given time. For the minute hand, the angle is: minute_angle = ((minute % 60) / 60) * 360 The hour hand angle depends on both the hour and the minute. For example, if it is 8:30, the hour hand is halfway between 8 and 9. The hour angle is: hour_angle = ((hour % 12) / 12 + minute / 60) * 360 So the angle between the two hands is: hour_angle - minute_angle The overall approach is correct with a few problems. 1. minute%60 and hour%12 are meaningless because minute<60 and hour < 12, so the remainder is always the same as itself. 2. if this is all integer calculation, the result is ways 0. 3. the hour hand calculation is incorrect. 4. the final result should take the absolute value instead of simple subtraction. Taking the example of 8:30 according to the posted logic using floating calculation minutes_angle = 180 hour_angle=(8/12+30/60)*360= (4/6+3/6)*360=420 420-180=240 The correct answer should be 45 instead of 420. minute_angle=minute*360/60 hour_angle=(minute*360/60+hour*360)/12 answer = |hour_angle-minute_angle| = | hour*30 - minute*11/2 | Again using 8:30 as example: |8*30-30*11/2| = |240-165| = 45 Show More Responses you are all wrong try hh*30 - m*60.5 keep in mind the hours hand advances with the minutes as well. 8:30 should be closer to 90 degrees the 45. 8:00 would be 60, 9:00 would be 90 12:00 as 0 degree Assume time is x:y minute_angle = f(y)= y * 360/60=6y hour_angel = f(x,y) = x*360/12+ (y/60) *(360/12) = 30x+0.5y angle = |minute_angle - hour_angle| = |5.5y - 30x| if angle > 180, can also get 360 - angle. So 8:30 would be |165 - 240| = 75 8:00 would be |-240| = 240, also 360 -240 = 120 |

### Software Engineer at Microsoft was asked...

How many unique paths are there from B-L point to the T-R point of a chess table? What would be your approach to calculate this? 6 AnswersZhat would depend on whether there exist restrictions on the moves your piece can make. No it wouldn't. The question asks how many unique paths there are, not how many unique paths a certain piece can make. Also, I think we must assume the unstated rule that a given square may only be crossed in a given path once - otherwise the answer is infinity! @NCLrry: If you can only move up and right, but not left or down, then there are fewer paths and that is usually how I have seen this puzzle worded. Show More Responses Use dynamic programming. 3432 If only allow moving in vertical or horizontal direction: f(x, y) = f(x-1, y) + f(x, y-1); where f(1,1) = 1 f(8,8) = 3432 If allow moving in vertical or horizontal or diagonal direction: f(x, y) = f(x-1, y) + f(x, y-1) + f(x-1, y-1); where f(1,1) = 1 f(8,8) = 48639 |