Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

767

interview questions shared by candidates

## Algorithm Interview Questions

Sort: RelevancePopular Date

### Software Development Engineering Intern at Amazon was asked...

Jun 23, 2012

Mar 22, 2011
 Write a function that computes the intersection of two arrays. The arrays are sorted. Then, what if one array is really larger than the other array?6 Answerspublic static void printIntersectionOfSortedArrays(int []a, int []b) { int i = 0, j = 0; while (i < a.length && j < b.length) { if (a[i] == b[j]) { System.out.println(a[i] + " "); i++; j++; // INC BOTH } else if (a[i] < b[j]) { i++; } else { j++; } } } if one array is really larger than the other array: iterate over smaller ans binary search in larger.Create a hash table. hash[50] = 0; Set hash[array1[i]] =1 for all elements in array 1. loop through array2. if hash[array2[i]] == 1, then true; // the element intersects... this will work even if array 2 is longer than array 1.O(n log N) where n size of smaller array N size of bigger array public static void printIntersection(int[] arr1, int[] arr2) { int[] big = arr1.length > arr2.length ? arr1 : arr2; int[] small = arr1.length > arr2.length ? arr2 : arr1; for (int i = 0; i 0) { while ( n value) end = mid-1; } return -1; }Show More ResponsesDon't forget about the case of duplicate values. A= 1 3 3 B= 2 3 3 You don't want to output 3 twice.It's very interesting that people who are offered a job get very simple questions like this one. It's like they decide in advance whom they hire.Should be just as simple as O(n) public static void printIntersection(int[] a1, int[] a2) { int i = 0; int j = 0; int n1 = a1.length; int n2 = a2.length; while (i < n1 && j < n2) { if (a1[i] == a2[j]) { System.out.println(a1[i]); i++; j++; } else if (a1[i] < a2[j]) { i++; } else { j++; } } }

Mar 21, 2010
 You have a genealogy: 1) Describe a data structure to represent it. 2) Given any two people within the genealogy, describe an algorithm to determine if they share a common ancestor. You just need to return true/false, not all ancestors.6 Answers1) Each person is represented by an object, with two pointers: "mom" and "dad" that point to their respective parent. 2) Choose one of the two people arbitrarily. Perform depth-first traversal and create a set of ancestors reachable from that person. Perform depth-first traversal on the 2nd person and for each node visited check if they are in the set; if yes, return true. Use a hash-set for best performance.calculate the height of person 1 in the tree, calculate the height of person 2. Move them up to be the same height. Then keep going until they intersect.@user: Its not a tree. A genealogy is a graph due to the fact that you have maternal and paternal trees intersecting. Therefore there is no root from which to calculate height.Show More ResponsesIf you've optimizing for worst case, hash set is O(n) for search. You'd do better in worst case with a sorted structure. You'd do even better if you store a "visited" flag at each node. Alternately you can number each node and keep an array of visited flags. since depth first seach might find a longer link through dad before checking mom, you're better off with breadth first search. Anything reachable in one hop would be seen before anything reachable at best in 2 hopsYes. Good points. The second traversal should be breadth first. The first traversal it doesn't matter, as you need to visit all ancestors anyways. The use of a visited flag is a good optimization. Based upon the way the question was worded, it wasn't clear if you could design the data structure to optimize the algorithm or not.I belive both the first and second should be BFS traversals

Nov 13, 2012
 find 3 elements in an array that sum to 0.6 AnswersI would construct a hash of all entries in the array and then iterate through a 2d product of all elements in the array and see if that sum was in the hash as first mentioned. Any comments ?@Richard no, that's not the way to do it actually. Your naive solution would take a N^3 / 2 complexity. A N^2 lgN complexity can be achieved if you first sort the array. A pair a[i] and a[j] is part of a triple that sums to 0 if and only if the value -(a[i]+ a[j]) is in the array(and not a[i] or a[j]). You need to sort the array, then do N (N - 1)/ 2 binary searches that each take time proportional to log N, for a total running time proportional to N^2 log N. Here's an example in java : http://algs4.cs.princeton.edu/14analysis/ThreeSumFast.javaThanks for the comment. However, I'm not sure how I am that far off.. If you just replace my hash with an ordered array, then essentially it's the same algorithm. How did I get to n^3 though .. I take it on board that a hash array take longer to construct than an ordered list in which to do a binary search - is that the additional order of magnitude?Show More ResponsesRichard, The solution using a Hashtable is better, because its time complexity would be O(N^2).public void sumIsZero(int[] a){ int n = a.length; for(int i=0; iMore elegantly, RIchard is correct. Compute the 2sum (N^2/2 +N/2 operations) and store it in a has table (potentially O(1)) or sort the answer (potentiall O(n\lg n)). For each element in the list, look up the negation in this list (O(n) for has tables, O(nlg(n)) for sorted arrays).

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

Dec 17, 2009

Apr 27, 2013
 Given a series of words written using a scrambled alphabet, figure out what order the letters of the alphabet are in.7 AnswersUse a graph!More than three words would be helpful. Do what with a graph? How would you build it? How would you search it?Given a ciphertext C, and plaintext P, the problem is to find a key K that converts the ciphertext to plaintext. Without considering the asymptotic complexity, it should be straighforward to generate the key combinations using a backtracking search algorithm.Show More ResponsesMore specifically, you would be given a list of words in the ciphertext which are in alphabetical order. Your job is to determine the alphabetic order of the ciphertext letters. In a graph, each node would represent a letter, the directed edge would indicate ordering of the two letters it connects. Once the graph is built you can do a simple traversal of the graph to generate your alphabetical ordering. Hope that helps!I think I didn't get the question. Could someone elaborate on it a bit please?@Alexander An example of what I believe the question is presenting to the applicant is as follows. Say I knew one of the words was 'CAT'. Now, if I look at the scrambled 3 letter word, and it was ZBS, then I know that C = Z, A = B, and T = S. Essentially, potentially every letter in the alphabet (up to 26 letters in total) are not of the same value. So, if I had another example word, say 'TACS', and the given scrambled word is 'SBCY', then I now know that S = Y as well. This is not an explanation of how to approach the problem, as we're not given any sample words; This is simply my interpretation of how the question is supposed to be interpreted as @Alexander is probably not the only person who does not understand the question. Of course, I could have it wrong too, so who knows.http://www.careercup.com/question?id=19114716

Jan 24, 2010
 Given a stream of integers of unknown (possibly large) length, how would you pick one at random? Now prove its random.6 AnswersQuestion was not worded very well, however we eventually reached mutual understanding. Answer: Store one integer at most. For each pop, decide whether or not to store it in the one slot with probability 1/N (N is current count of integers encountered).proof is easy: probability of an object appearing (being chosen) to be in some previous slot K starts with 1/K as per the algorithm. To "survive" to the Nth slot, the probability is (let M be distance of K to N: M = N - K or N = K + M) 1/K * K/(K+1) * (K+1)/(K+2) * ... * (K+M-1)/(K+M) , the last denominator simplifies to N All the numerators and denominators cancel except 1/N.Can you explain how you got this? 1/K * K/(K+1) * (K+1)/(K+2) * ... * (K+M-1)/(K+M)Show More ResponsesYou can prove by induction, probably simpler. If the list only contains 1 member, probability is 1/1 = 1, which is correct. For the induction step, consider what happen when k-th member is encountered: case(a): for the k-th member, probability of being picked is 1/k, which is what we want. case(b): for each of the previous (k-1) members, probability of being picked become P(k-th not picked) * P(original, i.e. 1/(k-1)) = (k-1)/k * 1/(k-1) = 1/k, which is what we want. [] It is more fun if we were to picked m members at random, then the prove becomes less trivial (though almost equally as straightforward).Thank you for the clear, concise explanation, Shards! I get everything except for one part: P(being picked) = P(k-th not picked) * P(original) Where does that come from? Is that a probability rule? If you could point me to a link on the web (or even what keywords to search on Google), that would be much appreciated. Thank you!Just run rand() function to get a number for each member, always keep the member with the minimum number associated with it. Need a little extra effort to handle tie case.

Jan 24, 2010
 Define binary search tree. Develop a procedure to verify a binary search tree.6 AnswersNot very difficult. Asked for answer in code. Interviewer took notes for each line I wrote. Was interested in each statement I made about the algorithm, esp. why I took each approach.How do you verify a binary search tree? Will you get all the values from binary search tree and check if they are in order? can someone explain?@Bala Recursively: Check node.left node.value. Also, that all subvalues of node.left node.value. Make sure you do checking for edge cases (ie. leaf nodes, etc).Show More Responsesrecursive solution is a good option i guess.. its definitely easy to code. However i think we can have it done more efficiently if we just perform a BFS on the given tree. and every time just check tht the left child is smaller and right chiled is greater than or equal to the current node. If we successfully search the entire tree then it is a proper BST otherwise its not.public static boolean checkTree(BSTNode node, Integer leftLimit, Integer rightLimit) { if(node == null) return true; if(leftLimit != null && leftLimit > node.info) { return false; } if(rightLimit != null && rightLimit < node.info) { return false; } return checkTree(node.left,leftLimit,node.info) && checkTree(node.right,node.info,rightLimit); }bool IsValidBST(Node root, int min, int max) { if(root == null) return true; if (root.iData > min && root.iData < max && IsValidBST(root.LeftChild, min, root.iData) && IsValidBST(root.RightChild, root.iData, max)) return true; else return false; }

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

Aug 29, 2009