# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

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. 13 Answerspublic 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< Show More Responses This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer. public int returnNonRepeat(int[] input) { if(input.length < 3) return -1; else { int repeat = null; if(input[0] == input[1]) repeat = input[0]; else if(input[0] == input[2]) return input[1]; else return input[0]; for(int i = 2; i Cant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) space only 2 possible solutions 1.) using sorting 2.) using additional space. which will be less than o(n) sub find_odd { my @a = @{$_[0]}; my ($i, $n); $n = $a[0]; for $i (1 .. $#a) { $n = $n ^ $a[$i]; } printf("number is %s\n", $n); } Use xor idea: 2(1 + 2 + 3) - (1+2+3+2+3) = 1 array = [1, 2, 3, 2, ,3] return( (2*sum(set(arr)) - sum(arr)) This person from Amazon told me what to expect in this interview. it was really good info and helpful. Here's their profile: https://www.rooftopslushie.com/profile/ask public static int NotRepeated (int ar[], int n) { int answer = -1; ArrayList arList = new ArrayList(); System.out.println(Arrays.toString(ar)); int n1 = 0; int n2 = 1; for (int i = 0; i < n; i++) { n1 = i; n2 = i +1; if (i == ar.length && (ar[i] != ar[i-1])) answer = ar[i]; else if (ar[n1] == ar[n2]) i++; else if (ar[0] != ar[1]) answer = ar[0]; else { if (ar[n1-1] == ar[n1]) { if (ar[n2] == ar[n2+1]) i++; else answer = ar[n2]; } else answer = ar[n1]; } } Wondering is getting a referral really critical? Seems like tons of people asking referrals on rooftop slushie: http://bit.ly/referral127 I think the key in generic questions like this is to be careful to cover the fundamentals, and to be familiar with all the followups so you're prepared for whatever they throw at you. Maybe do a mock interview with one of the Amazon Software Development Engineer Intern experts on PrepTick to get a real-world answer? They give lots of guidance and pro tips on how to deal with this kind of stuff. https://www.preptick.com/practice-interviews |

### Software Engineer at Google was asked...

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

### Software Engineer at Google was asked...

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 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 Engineer at Facebook was asked...

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

What are the first 2 integers that, when added together, equal 10 in a "very large" array of unsigned integers? 6 AnswersMy in-interview answer was bad!!! I came up with a better one using a 2d array with 11 rows and 2 columns. First column to hold the first occurrence of each integer 0-10 (conveniently, the indices of each row match a relevent integer) and second column to hold the second occurrence of 5. When you first encounter an integer that can be used to equal 10, add the index to the first column. When encounter 5 for the second time, add it to the second column. Each time you update a value, check to see if both sides of the equation are populated...if so, you have your answer, if not continue on with the original array. Note: Adding the index enables you to keep track of WHERE the integers were in the original array, however if that doesn't matter, you could update it with any value that works for your evaluation logic. It's a specific case of the problem of finding two integers that add up to a given number in a list of integers. In general case, you do need to sort first and use two pointers from start and end and use an elimination to search in O(n). In this case, since sum is already given (a constant) we just need to maintain last unique indices of integrers <= 10. Any time we find two that adds up to 10 is the answer. if it is a "very large" collection, avoid sorting; i think we are creating a time consuming cycle there. i have given a little piece of code for a similar question in this forum itself, which can be used as a starting point for bettering your answers. i got this question few years ago, when i went for an interview, with a bay area network security company.. as a UI developer !! Show More Responses should not sort it. Create an array or length 11 (index of 0-10), call it H, fill it with null (you can use -1 as null) Call original array A. Code is very simple: i = 0 while(i++) complement = 10 - A[i] if(H[complement] == null) H[complement] = i else break at this point A[H[complement]] + A[i] == 10 I'm essentially using H as a hash table where hash(n) = n this solves the problem in O(n) I believe. I think hashing is preferred in this case. @maxzed2k I'm not entirely sure if your solution will cover all cases. What if the complement (i.e. 10-A[i]) is negative? H[ ] will give you a segmentation fault. |

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

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

### Software Engineer at Google was asked...

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

### Software Engineer at Google was asked...

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 Responses recursive 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...

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 Responses EDIT: 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 Developer at Epic was asked...

I have a log that consists of more than 100 million lines. Each line is just a data about user login, login time, etc. I want to sort them based on user login, and then if there is a tie based on login time, etc. However, I have limited memory, so don't think of storing all of them in an array. The memory can only hold n data where n is much smaller than 100 millions. You can access the disk though although it is much slower. How will you do it so that it is as efficient as possible? 5 Answershint: the memory can only hold n data, use them wisely. we can solve this problem using n^2 complexity time we scan the whole enters to find the smallest value and we do that in a for loop its complexity is bad, n square anyone knows better answer? how about using hash table? Show More Responses Use an external mergesort http://en.wikipedia.org/wiki/External_sorting hash table |