Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

766

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

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

Mar 19, 2009
 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 ResponsesFor 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.

### Software Engineer Intern at Motorola Mobility was asked...

Mar 19, 2009
 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 tempoh 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 Responsesdo 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.

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

Jan 4, 2010
 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 ResponsesThis 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.

### Quant Research Intern at Susquehanna International Group (SIG) was asked...

Mar 17, 2013
 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 ResponsesYou 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 sortbucket sort. Sort each bucket, then merge.Mark

Apr 27, 2012
 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 ResponsesIn 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) { coutIt is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics.

Aug 1, 2013
 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; ithe 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 -1Here 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...

Mar 18, 2009

May 31, 2011
 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 kindSome 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 ResponsesInterval 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...

Jul 20, 2013
 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_angleThe 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| = 45Show More Responsesyou 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 9012: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...

Apr 29, 2009
 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 ResponsesUse dynamic programming.3432If 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
3140 of 766 Interview Questions