Algorithm Interview Questions | Glassdoor

Algorithm Interview Questions

785

interview questions shared by candidates

Algorithm Interview Questions

Sort: RelevancePopular Date

Senior Software Engineer at Microsoft was asked...

Mar 18, 2009
 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. 5 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 etcIt 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 ResponsesHow 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

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

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

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.

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

Web Development Engineer at Amazon was asked...

May 24, 2009
 How would you implement integer division if your language did not offer it. 5 Answershttp://www.bearcave.com/software/divide.htm#Assumes positive numbers def divide(num, divide_by) answer = 0 return answer if divide_by == 0 while(num >= divide_by) num = num - divide_by answer = answer + 1 end answer end puts divide(10,0)I think this is all you need, as the question asks for integer division I.e. 2 integer inputs to provide integer output 3 / 4 = 0 (dividend is less than the divisor) 2 / 1 = 2 (divisor is 1) 4 / 2 = 2 (divisor is a factor) 7 / 5 = 1 (dividend is greater than divisor) Note: solution below is for positive integers public static double divide(int dividend, int divisor) { int remainder = dividend; int count = 0; while (remainder > divisor) { remainder -= divisor; count++; } return count; }Show More ResponsesEDIT: To also handle divide by zero and negative numbers public static int divide(int dividend, int divisor) throws ArithmeticException{ int remainder = dividend; int count = 0; if (divisor == 0) { throw new ArithmeticException("Divide by 0"); } if (remainder > 0 && divisor = divisor) { remainder -= divisor; count--; } } else if (remainder 0) { remainder *= -1; while (remainder >= divisor) { remainder -= divisor; count--; } } else if (remainder = divisor) { remainder -= divisor; count++; } } else { while (remainder >= divisor) { remainder -= divisor; count++; } } return count; }Simpler version (assuming you are allowed to use multiplication), just compute the sign at the end and multiply: function divide(a, b){ if(b == 0) throw "Cannot divide by zero"; var remainder = Math.abs(a); var dividend = Math.abs(b); var result = 0; while(remainder >= dividend){ result++; remainder -= dividend; } if(result > 0 && a*b < 0) result *= -1; return result; }

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