Algorithm Interview Questions | Glassdoor

# Algorithm Interview Questions

786

interview questions shared by candidates

## Algorithm Interview Questions

Sort: Relevance Popular Date

May 9, 2012

Nov 13, 2012
 find 3 elements in an array that sum to 0. 6 Answers I 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.java Thanks 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 Responses Richard, 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; i

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

Jun 23, 2012
 You are given an array with n positive integers where all values in the array are repeated except for one. Return the one that is not repeated. 7 Answers public static int notRepeated(int[] given) { Map m = new HashMap(); for(i=0; i < given.length; i++) { if(m.get(given[i])) { m.put(given[i], 2); } else m.put(given[i], 1); for(x:m) { if(x == 1) return x; } } } If you have an array of positive integers with only ONE non repeated integer, the easiest thing is just xor them all. Whatever you return will be the answer. Perl answer below sub findNotRepeated{ my (\$arr) = @_; if(@\$arr==0) { return - 1; } my \$val = 0; foreach(@\$arr) { \$val ^= \$_; } return(\$val); } sub findMissingElement{ my (\$arr,\$arr2) = @_; if(@\$arr==0 || @\$arr2 == 0 ) { print " arr2=" .@\$arr2 . "X\n";; return - 1; } my \$val = 0; foreach((@\$arr , @\$arr2)) { \$val ^= \$_; } return(\$val); } first sort the array.n then 1)for i=1 to n { if ( element [i] !=element [i+1] ) { cout<

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 Answers public 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 Responses Don'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 Answers 1) 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 Responses If 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 hops Yes. 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

### 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 Answers Use 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 Responses More 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 Answers Question 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 Responses You 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.