# Algorithm Interview Questions

interview questions shared by candidates

## Algorithm Interview Questions

### Software Engineer at Facebook was asked...

You are given an integer N and an integer M. You are supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average. 8 AnswersI just started working on this problem, but here is a rough outline: 1. Generate all subsets of N coins. 2. For each subset, generate the minimum multi-set required to materialize the total values 1...M; say for subset of coins N(i), we name each multi-set of coins N(i),M(j) where j is some value between 1 and M. 3. For fixed i, get the average over j for each multi-set N(i),M(j). 4. Choose the subset N(i) that maps to the lowest average size of the multi-sets that are generated from N(i). Time will be O(2^N), since we are generating each subset of N. Feedback much encouraged to get this down to a polynomial solution. We need some way to narrow down the subsets of N that we consider. Perhaps we could start by enumerating the subsets of N lexicographically, and then performing a binary search on the array of subsets to help us choose? Just a thought, not very developed yet. Why is 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1? Should it not be 10+10+1+1+1+1? Show More Responses I doubt this question really was a Facebook interview question (although I am not a Facebook employee nor do I have any connection with Facebook). Anyway, here is a research paper precisely on this problem: http://www.cs.uwaterloo.ca/~shallit/Papers/change2.pdf It is written by a well known researcher in algorithms and he says on page 6 (problem 5) that this problem is hard and that he wasn't able to find a polynomial time algorithm for it. So the best way to do do it is to enumerate all possible denomination subsets, and then for each value and each denomination system, compute what the minimum number of coins for that value is using the well known dynamic programming approach. And to the previous commenter (A): you are absolutely right. Just based on the reading of the problem it sounds very much like a variation of the Knapsack problem (optimization) which is NP Hard. The problem grows exponentially harder as N grows. Except for small values of N, algos for computation are not likely to return for a long time. very slow... need to reduce generating coins sets... public class Solution { private static ArrayList coins = new ArrayList(); private static void generatesets(int[] n, int k, int M, int N) { if (k == N) { coins.add(n.clone()); return; } for (int i=n[k-1]+1; i averagecnt) { minc = averagecnt; res = coinset; } } System.out.println(Arrays.toString(res)); } } Not sure of the proof of correctness; just an iterative algo trying to implement pattern; more test-cases will be helpful. import java.io.IOException; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class BestCoins { public static void main(String[] args) throws IOException { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter total number of coins : N : "); int n = in.nextInt(); System.out.println("Enter max coin value : M : "); int m = in.nextInt(); Set coins = new TreeSet(); findBestCoinsThatMinimizeAverage(m, n, coins, true); System.out.println("Best coin set is " + coins); } } private static void findBestCoinsThatMinimizeAverage(int m, int n, Set coins, boolean minimize) throws IOException { System.out.println(m + " " + coins + " " + minimize); // new BufferedReader(new InputStreamReader(System.in)).readLine(); if (m <= 1) { coins.add(1); return ; } int coin = minimize? m/n : m-m/n; if (coin == 0) { coin = 1; } coins.add(coin); if (coin == 1) { coins.add(m-1); return; } int remainingM = minimize? coin-1 : m-coin; findBestCoinsThatMinimizeAverage(remainingM, n, coins, !minimize); } } Here is my solution to it: https://dotnetfiddle.net/qnCdop Exponential time complexity. BTW for M=100, N=4 I get {38, 11, 3, 1}, not {1, 5, 18, 25} as the question specifies. One of us is wrong. |

### 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<n-1; i++) for(int j=i+1; j<n; j++) { int num1 = a[i]; int num2 = a[j]; for(int k=j+1; k<n; k++){ int num3 = a[k]; int sum = num1 + num2 + num3; if(sum == 0){ System.out.println("a["+i+"]="+num1+", a["+j+"]="+num2+", a["+k+"]="+num3); } } } } 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). |

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 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<<element[i] break } else { i=i+2 } } I dnt have any idea about its time complexity... 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<input.length; i++) { if(input[i] != repeat) return input[i]; } } return -1; } 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); } |

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

### Software Engineer at TripAdvisor was asked...

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 Responses In 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) { cout It is a classical programming question that derives from the first fit decreasing algorithm in discrete (decision) mathematics. |