# Programming Interview Questions

interview questions shared by candidates

## Programming Interview Questions

What is your current employer doing better than we are? I work in marketing so I had to answer based on my research done prior to interview. I was so happy I did a ton of research/comparison before going in. 1 AnswerThey do a better job of promoting and communicating their programs. |

Number of 1's in binary representation of integer? 12 AnswersRun a loop, in which you binary-AND the integer with 1, and increment a counter, if the result is 1. Then right-shift the input-integer by 1 bit, and start over in the loop unsigned int ones(unsigned int number) { unsigned int n; for (n = 0; number != 0; number >> 1) { if (number & 1) { n++; } } return n; } Show More Responses i dnt knw wheather it correct or not.....do correct me if im wrng a=0 q=n/2 r=n%2 n=q if(r=1)then a=a++ continue.... ct = 0; while (val) { ct++; val = val & (val - 1); } Several of the above work, but use preincrement public static int population(int x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); return x; } in C++, how about: do { sum += n&1; } while (n>>=1); int ones( ) { int n; int number = 1100110111; n = 0; while (number!=0) { int temp = number % 10; if(temp ==1 ) n++; number = number/10; } return n; } Lets consider 14(1110) is the number int CountOnes(int Number) { int n=0; while(number !=0) { if(number%2==1) n++; number >> 1; } return n; } The function takes an int and returns the number of Ones in binary representation public static int findOnes(int number) { if(number < 2) { if(number == 1) { count ++; } else { return 0; } } value = number % 2; if(number != 1 && value == 1) count ++; number /= 2; findOnes(number); return count; } All the answers above will not get you to amazon... try code the function with o(m), where m is the number of 1's in the binary representation of an integer. (hint: look up "Programming Interviews Exposed") |

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

Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function). 9 AnswersI came up with a recursive solution something like this: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if (node != null) { if (node.left != null && node.left > max || node.right != null && node.right < min) { return false; } else { return (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)); } } else { return false; } } How come this function never returns true? And why would you need min and max? Ok, so I should have spent a little more time posting this (I was admittedly rushing through it so I could get access to more questions/answers). Here's a revised version that should hopefully make more sense: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if(node == null) { return true; } if(node.value > min && node.value < max && IsValidBST(node.left, min, node.value) && IsValidBST(node.right, node.value, max)) { return true; } else { return false; } } The main change is that I decided to avoid checking the children of the tree in the body, and leave it to recursion to take care of that. Thus, we just have to look at the current "node" and that's it... the constraints will be handled by passing min and max down. @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. Finally, the min and max values are required because a BST requires that each value in the left branch be smaller than ALL parent values on that branch (and similarly for those on the right branch being larger). Another way of saying this is that the entire left tree of any node must be smaller than the node's value, and the entire right tree must be larger than the node's value. Thus, in a recursive solution, you have to have a way to pass down the upper and lower bounds to the lower levels of the tree, otherwise the third level won't be able to check whether it's smaller/larger than the root two levels up. That's why we pass down the min and max values. Hope this helps. Show More Responses boolean isBST(TreeNode node) { if(node.isLeafNode( )) return true; else { if(node.value node.rightChild) return false; else return (isBST(node.leftChild) && isBST(node.rightChild)) } } traverse in order and see if they r same @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. ============= Those are just two function calls and the function never returns true. Alexander is right - you are missing a terminating clause in your recursion. Forgot to add - your second solution is correct since it returns true. // For +ve number OR use INT_MIN instead of -1(s) bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin rightMax ? leftMax : rightMax; return true; } // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } |

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

Write a function that divides two numbers without using the divide '/' operator. 10 AnswersI had to use recursive subtraction or addition. But, I think I took too long a time to figure out the fastest code and I was typing it out in google docs while the interviewer was on the phone with me. I was nervous. It was my first ever interview. But, it was a heck of a experience. X * Y^(-1) One way is to iteratively count the number of times Xn = Xn-1 - Y >= Y. No recursion needed. Also, if Y is a power of 2, you can use a right-shift to get the answer...even faster. If the number space is sufficiently small, you can use a lookup table. Show More Responses int positionOfFirstAndOnlyBitSet(int m) { int pos = -1; int x = 0; for (; x > x) & 1) if (pos == -1) pos = x; else return -1; // found more than one bit } return pos; } int divide(int n, int m) { if (m == 1) return n; if (m == n) return 1; if (m > n) return 0; int pos = positionOfFirstAndOnlyBitSet(m); if (pos != -1) return n >> pos; // how manny times one can multiply m before going over n int x = 1; int mm = m; while (mm <= n) { mm += m; x++; } return x - 1; } assuming you want to be able to handle doubles, I like the idea of x * pow(y,-1.0); ... why make the answer more difficult for yourself than it needs to be? I got this question in facebook interview as well. You usually are not allowed to use floats, or pow(), or % And also you have to consider both +, - integers, so Steve M answer is not valid. public static int divide(int a, int b) { if(a < b) return 0; int div = b; int k = 1; while((div<<1) <= a) { div = div<<1; k = k<<1; } return k + (div == a ? 0 : divide(a-div,b)); } int num; int div; int rem; // assume only positive numbers for(i=0; num>=0 ; num-=div) { i++; rem=num; } printf("\ni: %s%d rem:%d", i, rem ); Victor, whats the complexity of your solution ? Binary search will work ? Let's say you need x/y. And only integral solution is needed i.e. 10/3 = 3 , not 3.33. This won't work if we need float as a result Pseudocode If x > 2) if mid*y == x : return mid if mid*y > x : hi = mid - 1 else: lo = mid + 1 return lo -------------------- |

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

List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god -- output dog, god, act, cat 10 AnswersThankfully I was taking a theory course and one trick used in the course was "encoding" programs as a large natural number using product of primes. 1. Adapt the encoding as follows -- generate the first 26 primes and assign a prime to each letter 2a. For each word, take the product of each letter's prime. So #(act) = 2*5*prime(t) 2b. As you can see, #(cat) = 5*2*prime(t) = #(act) 3. Insert a handwavey argument about inserting the number/word pairing into a HashMap> Sort the words. Anagrams appear next to each other in the sorted list. Sorry, sort the letters in each word, then sort the words. Anagrams appear next to each other in the list. For example the sorted list for the input would be: act act ddd dgo dgo goo Show More Responses Thanks for sharing Bill For this set of input, the expected output should contain only [cat, act, god, dog]. I'm curious to see what "next steps" your algorithm will perform to provide this expected output You keep track of the mapping from the sorted word to the actual word in a pair, for example: [act, cat] [act, act] [ddd, ddd] [dgo, god] [dgo, dog] [goo, goo] Then you go through this list and count if you have a duplicate entry or not. If you do, like for act, you print out those duplicate entries: cat, act. Bill, your algorithm is O(n*log(n)) while the candidates would be O(n) - provided he uses a decent hash function donutello, bills algo is not n log n it is n*log(k) where as candidates algo is n * k again (multiplications for each word) where k = length of the longest word on top of that calculating primes is expensive anyway I would go with bills answer Bills algo is nlogk + nlgn. After sorting the k letters for n times you also have to sort the n words. #Get inputs a = [] f = open('input.txt','r') for line in f: line = line.strip() a.append(line) #Sort letters in a word def sort_letter(s): r = [] for i in s: r.append(i) t = sorted(r) v = ''.join(t) return v #Find anagrams d = {} for v in a: sv = sort_letter(v) if sv in d: d[sv].append(v) else: d[sv] = [v] #Print results for k,v in d.items(): if len(v) > 1: for s in v: print s think of each line as a set of characters, not a word, then create set of sets of characters which you fill from the input. then print the set (order does not matter as its not specified) |

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

Given a string find the first non-repeated character. 10 AnswersHint: use a hash table public static char getFirstNonRepeatedChar(String s) { List charList = null; char nonRepeatedChar ='?'; if (s != null) { s = s.trim(); charList = new ArrayList(); for (int i=0; i<s.length(); i++) { Character c = s.charAt(i); if (!charList.contains(c)) { charList.add(c); } else { charList.remove(c); } } } if (charList != null && !charList.isEmpty()) { nonRepeatedChar = charList.get(0); } return nonRepeatedChar; } @Rajiv : Your solution is completely wrong. It will fail for input of "aaa" Reason: on first check, you insert "a". On next check you remove it. On next check you again insert it and return that as your answer, even though it was repeated thrice. Show More Responses hash of non repeating characters tied to a double linked list, remove any repeating character from the hash and the list. at the end the head of the list is the answer. you can use the same hash to keep the counters. public static String findFirstNonRepeatedCharacter(String S) { int[] T = new int[256]; for (int i = 0; i < S.length(); i++) { char next = S.charAt(i); T[next] = T[next] + 1; } for (int i = 0; i < S.length(); i++) { if(T[S.charAt(i)] == 1) return String.valueOf(S.charAt(i)); } return null; } Three ways to find first non repeating character in a string c# find the code below - public char firstNonRepetitive(string inputString) { int nextOccurrence = 0; char firstDistinctChar = ' '; for (int i = 0; i < inputString.Length; i++) { nextOccurrence = 0; for (int j = (i + 1); j < inputString.Length; j++) { if (inputString[i] == inputString[j]) nextOccurrence++; } if (nextOccurrence == 0) { firstDistinctChar = inputString[i]; break; } } return firstDistinctChar; } Check out amazing two more way - program to find first non repeating character in a string c# - three ways http://www.dotnetbull.com/2013/08/find-first-non-repeating-character-string.html program to find first non repeating character in a string c# - three ways My python implementation: def firstNonRepeatingCharacter(inputString): hashmap = {} for x in inputString: if (x in hashmap): hashmap[x] = hashmap[x] + 1 else: hashmap[x] = 1 for x in inputString: if (hashmap[x] > 1): continue else: return x return "No nonrepeating character found" for (int index = 0; index < str.Length; index++) { if (str.LastIndexOf(str[index]) == str.IndexOf(str[index])) { return str[index].ToString(); } } I will have one variable x to store the first non repeating character, variable y as a backup And a set of characters already encountered. I will start from position n to position 0 where n is the lenght of the string. If char(n) is not present in the set, then check if x=char(n), if yes, x = y. If no, y=x and x=char(n). The idea is to keep updating the newest character that has not been repeated and also keeping the second newest character as a backup. In the end return x. |

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

Given a matrix print it clockwise from the first element to the very inner element. 6 AnswersNeed to design the program first and then implement it very carefully yet fast! void PrintMatrix(int** a, int n) { for (int i = 0; i = i; j--) { printf("%d ", a[n - i -1][j]); } } void PrintColInc(int** a, int n, int i) { for (int j = i; j = i; j--) { printf("%d ", a[j][i]); } } struct point { point(int a, int b) { row = a; col = b; } int row; int col; }; void printMatrixSpiral(int a[][5], int r, int c) { int direction = 1; // 1 - right // 2 - down // 3 - left // 4 - up point upper_left = point(0,0); //point upper_right = point(0,c-1); point lower_right = point(r-1, c-1); //point lower_bottom = point(r-1, 0); while(true){ if(direction==1){ int row = upper_left.row; for(int i=upper_left.col; i= upper_left.col;--i){ cout= upper_left.row;--i){ cout lower_right.row) || (upper_left.col > lower_right.col)){break;} } } Show More Responses int matrix[][3] = { {1, 2, 3}, { 4, 5, 6}, {7, 8, 9} }; void PrintMatrix() { int start = 0; int end = 2; while(end >= start) { for(int col = start; col = start; col--) cout start; row--) cout << matrix[row][start] << " "; start++; end--; } } int main() { int m, n; cin >> m >> n; int matrix[m][n]; for (int i = 0; i > matrix[i][j]; int l = 0, r = n, t = 0, b = m; while (l = l; i--) cout = t; i--) cout << matrix[i][l] << ' '; l++; } return 0; } ^ Above anon, your solution is almost correct. But for the 3rd and 4th for loops you first need to check whether you've already printed the corresponding previous for loop. Ok I didn't explain that too clearly. Here's an example: Matrix: {{1,2,3,4},{5,6,7,8},{9,10,11,12}} will print 1 2 3 4 8 12 11 10 9 5 6 7 6 That last 6 is because of the 3rd for-loop. You don't need to run that opposite for-loop (R-L) once you've already printed 6 from L-R. Just use an if-loop to rectify this. Same for the 4th loop. |

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

Assume that you are given the head and tail pointers of a doubly linked list where each node can also have a single child pointer to another similar doubly linked list. There are no cycles in this structure outside of the traditional double links. Write a procedure in C++ that flattens this structure into a single list. 7 AnswersI found out later that this problem is one of several classic programming questions taken from an interview book. Such a list has an obvious recursive structure, but it is large and so recursion is not practical. Consequently, an iterative approach is necessary. The invariant for such an approach maintains the flat list to the "left" and the possibly fat list to the "right." Do you know the name of the book? I don't know the particular book it was taken from. However, a colleague recommends the book: _Programming Interviews Exposed_ by John Mongan The second edition is available, but a third edition (with two additional authors) is on its way and available for pre-order on Amazon. There are several other similar books. For example, _Cracking the Coding Interview: 150 Programming Questions and Solutions_ by Gayle Laakmann McDowell _Programming Pearls_ by Jon Bently _Puzzles for Programmers and Pros_ by Dennis Shasha _How Would You Move Mount Fuji?: Microsoft's Cult of the Puzzle -- How the World's Smartest Companies Select the Most Creative Thinkers_ by William Poundstone and many others you can probably find by looking at Amazon's recommendations when viewing the descriptions of those books. Show More Responses Didn't get any notification that you had replied to this, and just found it again when reviewing my studies. Thanks! Glad to help! And many of those coding-specific books include lots of questions about operations on linked lists. I have a feeling that the questions asked to me probably come from that set of books (or a book that shares a source with one of those). There might be some variation, but the basic principles should be the same. PseudoCode Solution: class ListNode(prev, next, sub_list) def flatten_list(node): if node == None: return [] elif is_tailI(node): return [node.value] + flatten_list(node.sub_list) else: return [node.value] + flatten_list(node.sub_list) + flatten_list(node.next) The PseudoCode solution mentioned above is *NOT* the desired answer because it involves recursion. As mentioned in the first comment, recursion is not allowed due to the very large structure of this list. The correct solution makes use of loop invariants. |