# Coding Interview Questions

interview questions shared by candidates

## Coding Interview Questions

Suppose you have a matrix of numbers. How can you easily compute the sum of any rectangle (i.e. a range [row_start, row_end, col_start, col_end]) of those numbers? How would you code this? 6 AnswersIt can be done in constant time by precalculating sums of some basic rectangles (extending all the way to the border of the matrix). That precalculation times time O(n) by simple dynamic programming. Please elaborate, which "basic rectangles"? Are you recursively dividing each rectangle into 4 smaller rectangles? Precalc time for doing that is not O(n)?!? Compute the sum of the rectangles, for all i,j, bounded by (i,j), (i,m), (n,j), (n,m), where (n,m) is the size of the matrix M. Call that sum s(i,j). You can calculate s(i,j) by dynamic programming: s(i,j) = M(i,j) + s(i+1,j) + s(i,j+1) - s(i+1,j+1). And the sum of any rectangle can be computed from s(i,j). Show More Responses Awesome!! The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_features It wasn't 100% clear to me, then I found the Wiki page http://en.wikipedia.org/wiki/Summed_area_table |

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

Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree. 7 AnswersCorrect answer should be something like this: int FindNthElement(Node *node, int &n) { if (node->Left && n > 0) { k = FindNthElement(node->left, n); if (n == 0) return k; } if (n == 0) return node->value; else if (n > 0 && node->right) { k = FindNthElement(node->right, n); if (n == 0) return k; else return -1; } } int findNthElementByInorder(Node *node, int &n) { if (node == null) return -1; findNthElementByInorder(node->left, n); if (n == 0) return node-> value; else n--; findNthElementByInorder(node->right, n); } Seems it should be something like this, get the to bottom and start counting up from there. int start(Node *node, int &n) { int element = 0; if (node == null) return -1; return findElementIndex(node, element, n); } int findElementIndex(Node *node, int ¤tNumber, int findNumber) { if(node->left != null ) { int result = findElementIndex(node->left, currentNumber, findNumber); if(result != -1) return result; } if(node->right != null ) { int result = findElementIndex(node->right, currentNumber, findNumber); if(result != -1) return result; } currentNumber++; if(currentNumber == findNumber) return node->value; else return -1; } Show More Responses //Assumption is that the node values are not negative. //If the tree has less than n nodes, -1 will be returned. int findNthElementByInorder(Node *node, int &n) { if ((node != null) && (n > 0)) { findNthElemetnByInorder(node>left, n); n--; //Count the current node findNthElemetnByInorder(node>right, n); return node->value; } else return -1; } def nth_inorder_node(treeNode, counter) # Check left node if treeNode.left rv = nth_inorder_node(treeNode.left, counter) return rv if rv end # Check current node counter.value -= 1 puts "counter: #{counter.value} \t node: #{treeNode.data}".green return treeNode.data if counter.value == 0 # Check right node if treeNode.right rv = nth_inorder_node(treeNode.right, counter) return rv if rv end return nil end int nthelement(Node node, int n){ int ret; if( node.left != null) { ret = nthelement(node.left, n); if(ret != -1) return ret; } n --; if(n ==0) return node.data; if(node.right != null) { ret = nthelement(node.right, n); if(ret!= -1) return ret; } return -1; } int [] results; int count = 0; int returnNthElement(Node rootNode, int element) { fillArray(rootNode); return results[element]; } void fillArray(Node node) { if (node == null) { return null; } if (node.left == null && node.right == null) { count++; results[count] = node; return; } fillArray(node.left); count ++; results[count] = node; fillArray(node.right); } |

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

You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently. 7 AnswersThe problem is not too difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete. Does this really work? If I the empty spot is expected to be the same, but the positions of two (or more) cars are switched, how to rearrange it without a complete search? It's the Tower of Hanoi Problem. Show More Responses So there are actually 2 empty spots then or is there a way to 'stack' cars I don't know of? The parking lot problem has nothing to do with Tower of Hanoi, which requires O(2^n -1). This problem, however, can be solved in O(n) - that's because all you need to do is to perform (0 or more) rotations using the empty parking spot. Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable> RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -> spot Dictionary pending = initial.ToDictionary(p => p.Value, p => p.Key); // remove emptySpot from lookup TSpot emptySpot = pending[emptyCarMarker]; pending.Remove(emptyCarMarker); while (pending.Any()) { // check if the empty spot is where is should be if (desired[emptySpot].Equals(emptyCarMarker)) { while (true) { // pick a car (any car would do) var carToMove = pending.First(); // check if this car is already in its desired position if (desired[carToMove.Value].Equals(carToMove.Key)) { // remove from pending, no moving is necessary pending.Remove(carToMove.Key); if (pending.Any() == false) yield break; } else { yield return new Tuple(carToMove.Key, carToMove.Value, emptySpot); // move the car TSpot newSpot = emptySpot; emptySpot = carToMove.Value; pending[carToMove.Key] = newSpot; break; } } } // move the car into its desired spot var car = desired[emptySpot]; var newEmptySpot = pending[car]; yield return new Tuple(car, newEmptySpot, emptySpot); emptySpot = newEmptySpot; pending.Remove(car); } } Note that there is a while-loop inside another while-loop. However, the complexity is still O(n) since at every iteration of internal or external loop, the "pending" map is reduced by one element. Below are some examples (emptyCarMarker == ""). EXAMPLE 1: Input: initial == { "", "B", "A"} desired == { "", "A", "B"} Output: (B, 1, 0) // move car B from spot #1 to #0 (A, 2, 1) // move car A from spot #2 to #1 (B, 0, 2) // move car B from spot #0 to #2 EXAMPLE 2: Input: initial == { "", "B", "A", "D", "C" } desired == { "A", "B", "", "C", "D" } Output: (A, 2, 0) (D, 3, 2) (C, 4, 3) (D, 2, 4) Here is a Java Implementation, using Google's guava library for the BiMap. It takes O(n) to first create the BiMap and O(n) to move the cars, total O(2n), i.e. O(n) time complexity. import com.google.common.collect.BiMap; import com.google.common.collect.HashBiMap; import java.util.Map; import java.util.Set; class ParkingAttendant { static class ParkingConfiguration { static final Integer EMPTY = -1; Integer moves = 0; BiMap conf, i_conf; static ParkingConfiguration getInstance(int[] conf){ return new ParkingConfiguration(conf); } private ParkingConfiguration(int[] conf){ this.conf = arrayToMap(conf); this.i_conf = this.conf.inverse(); } BiMap arrayToMap(int[] arr){ BiMap m = HashBiMap.create(arr.length); for(int i=0;i> entrySet(){ return conf.entrySet(); } } static void moveCars(ParkingConfiguration from, int[] to){ for(int pos=0; pos e : p.entrySet()){ int pos = e.getKey(); int car = e.getValue(); System.out.format("%1$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } static void printCars(int[] p){ System.out.print("["); for(int pos=0; pos<p.length; pos++){ int car = p[pos]; System.out.format("%1$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } public static void main(String args[]){ ParkingConfiguration from = ParkingConfiguration.getInstance((new int[]{1,2,3,4,ParkingConfiguration.EMPTY,5,6,7,8,9})); int[] to = new int[]{2,3,4,5,6,7,8,9,1,ParkingConfiguration.EMPTY}; System.out.println("Initial Parking Configuration:"); printCars(from); System.out.println("Target Parking Configuration:"); printCars(to); moveCars(from, to); System.out.format("After moving %1$d Cars, the Original Parking Configuration: %2$n", from.moves); printCars(from); } } OUTPUT: Initial Parking Configuration: [1, 2, 3, 4, _, 5, 6, 7, 8, 9, ] Target Parking Configuration: [2, 3, 4, 5, 6, 7, 8, 9, 1, _, ] After moving 8 Cars, the Original Parking Configuration: [2, 3, 4, 5, 6, 7, 8, 9, 1, _, ] |

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

Given a list of integers, some of which may be negative, extract the pair that sums to the largest number. 8 AnswersThe naive solution is O(n^2). The trick is to sort the list in O(n lg n) then pick the two largest numbers from the front. you can get the largest two number in O(n), right? sum those two numbers up. Whoops, I wrote the wrong question. Here's what I meant to say: given a list of integers, find a pair that sums to a given value. Show More Responses Keep a list of integers, and set it to 1 if they are in within the list. for (int i = 0; i < n; ++i) dp[array[i]] = 1; for (int i = 0; i < n; ++i) if (dp[S - array[i]] && S - array[i] != array[i]) print S - array[i] and array[i] because they sum to S This is the subset problem. This is O( n ), but requires O( S ) space. @bleh: I guess the solution will work if all the elements are +ve, in this case however the elements are negative. So probably we can use hash instead of arrays. if both hashing and the subset solution aren't good enough - 1. Sort the array o(n) or o(nlogn) - pick the one you can sell 2. Have two pointers - one at the end and the other at the beginning 3.a. If the sum is less than S increment the one in the beginning 3.b. If the sum is greater than S decrement the one at the end 3.c If the sum is S - you are done 3.d If the two pointers have met or crossed over - you are done Amazon really loves dynamic programming eh? I've come across many interview questions with the knapsack and coin-change problems #define SIZE 3 int tab[SIZE]; int sum; int max=-MAXINT; int sovi, sovj; for(i=0; i max) { max=sum+tab[j]; sovi=i; sovj=j; } } } printf("\n i: %d j:%d", sovi, sovj); |

### Test Engineer at Qualcomm was asked...

Initialize a 5 by 5 array with this sequence. 1 2 3 4 5 6 4 8 9 10 11 12 9 14 15 16 17 18 16 20 21 22 23 24 25 7 AnswersThere's a pattern. The array is filled from 1-25, then the squares (Array[i][i]) are replaced with the square of the index+1. //C code answer... int arr[5][5]; int t=1; for(int i=0; i < 5; i++) for(int j=0; j < 5; j++) { if (i == j) arr[i][j] = (i+1)*(j+1); //square it! arr[i][j] = t; t++; } Either the question or answer doesnt make sense. Solution to question as posed: int arr[5][5] = { { 1, 2, 3, 4, 5 }, .... { 21, 22, 23, 24, 25 } }; Really don't see what you are trying to solve on that answer of yours... for instance, the arr value assigned on the //square it line is promptly overwritten on the following line. Also, multiplying and assigning isn't faster than just assigning. Is there any pattern? I don't see any. I think the one who posted this question missed something or there's something wrong with the question. What's 4 after 6, 9 after 12, 16 after 18, 25 after 24? What's the something in common among them? Show More Responses Perhaps it is easier to see the pattern in 5x5 grid: 1 2 3 4 5 6 4 8 9 10 11 12 9 14 15 16 17 18 16 20 21 22 23 24 25 Agreed, that this was a stupid interview question (I asked if I could just initialize it like the 2nd commenter, but he said he was looking for something else... it was a bit wierd... :/ ). Sorry I got the order of the lines wrong. 1 2 3 4 5 6 4 8 9 10 11 12 9 14 15 16 17 18 16 20 21 22 23 24 25 #define SIZE 5 int tab[SIZE][SIZE]; k=0; for(i=0; i<SIZE ; i++) { for(j=0; j<SIZE ; j++) { l=k; switch(l) { case 7: l=4; break; case 13: l=9 break; case 19: l=16 break; default : break; } tab[i][j]=l; } k++; } for (i=0; i<5; i++) { for (j=0; j<5; j++) { A(i,j) = 5*i+j+1; } } there is indeed a pattern! int ary[5][5]; for (int i=0;i<5;i++){ for(int j=0;j<5;j++){ if(i == j) ary[i][j] = (i+1)*(i+1); else ary[i][j] = 5 *i +j+1; } } |

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

Look for a string in a very long string - a needle in a haystack. Write the program in pseudo-code. 5 Answersfunction isSubstring (needle, haystack) { for(int i=0; i<length(haystack); i++) { if (needle[0] == haystack[i]) { for(int j=0; j<length(needle; j++) if(needle[j] != haystack[i+j]) break; if (j==length(needle)) return true; } } return false; } The Boyer–Moore string search algorithm can run, in < O(n) time, on average, particularly if the string being looked for is long. Note: the question specifically asks for a solution in *pseudo-code* ... Show More Responses For production code, I would look up Boyer-Moore and do that. But if I had to answer off the top of my head, based on my memoires of Boyer-Moore, the pseudo-code would look like: Construct table(char-diff, offset) {offset by which to move test string b4 next text} begin: Compare (needle, haystack): if comparison false, lookup in above table to compute next offset. Compare (needle, haystack[next-offset] if comparison still false AND we have not passed end of haystack, repeat. Test which case: did we pass end, or find needle return 0 if passed end, offset to needle in haystack otherwise. Small optimization : can store length(haystack) and length(needle) to make it faster :) |

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

I am playing a card game called 24. Cards ace to king are numbered 1 to 13. During a given round, I am provided four cards to play with from the shuffled pack. If the numbers from the four cards result in 24 then I win the round if I shout '24' first. How would you code a function for this? 4 AnswersFour numbers and three operators at a time. Consider permutations of such expressions in postfix notation. Evaluate these permutations till you get 24. It's a naturally recursive operation. Take the four cards, A, B, C, D. In the different steps you have (target = 24): (target) : using cards A, B, C, D (target - A): using cards B, C, D (target - A - B): using cards C, D (target - A - B - C): using card D Repeat for each of the other cards in the step's grouping if the target isn't met, ie. (target) : using cards B, C, D (target - B): using cards C, D (target - B - C): using card D And so on. Pass true up the stack when any of the target values reach zero. Once you have that down, it's trivial to write the function. If we know the rules won't change (always four cards, always summing to 24) and speed REALLY matters, then the correct answer is to ignore complexity and elegance and let the CPU burn through this. Just add the first two cards and check the sum. If sum == 24, shout (return). If sum < 24, add third card and check. If sum < 24, add fourth card and check. Sorting or structuring will take too much time even though it could be a big win in the general case - someone else will shout while we're moving our cards around. Show More Responses It's a naturally recursive operation. Take the four cards, A, B, C, D. In the different steps you have (target = 24): (target) : using cards A, B, C, D (target - A): using cards B, C, D (target - A - B): using cards C, D (target - A - B - C): using card D Repeat for each of the other cards in the step's grouping if the target isn't met, ie. (target) : using cards B, C, D (target - B): using cards C, D (target - B - C): using card D And so on. Pass true up the stack when any of the target values reach zero. Once you have that down, it's trivial to write the function. You only consider the + operator, which is not true in 24 points game. There are +,-,* and / 4 operators. |

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

Extract the N largest floating point numbers from a large file of floating point numbers. 4 AnswersTo do this efficiently you need to keep your largest number list sorted and you only need to make comparisons to the smallest number in the list. Remember that sorted list insertion is O(lg n). its about extracting from file of floating point numbers. so have to use scanner to extract floating point numbers and add it in to the list or array and sort it, using Collections.sort or Arrays.sort function of JAVA. maxheap will do the work Show More Responses #define N 2 #define SIZE 3 int tab[SIZE]; int max; int sovj; for(i=0; i<N ; i++) { max=-MAXINT; for(j=0; j<SIZE ; j++) { if(max<tab[j]) { max=tab[j]; sovj=j; } printf("\n j: %d", sovj); tab[sovj]=-MAXINT; } } |