Coding Interview Questions | Glassdoor

# Coding Interview Questions

70

interview questions shared by candidates

## Coding Interview Questions

Sort: RelevancePopular Date

Jan 21, 2010
 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 ResponsesAwesome!!The answer is already popular in computer vision fields!! It is called integral imaging. See this page http://en.wikipedia.org/wiki/Haar-like_featuresIt 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...

Feb 27, 2010

Jun 11, 2010

Aug 5, 2012
 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 endint 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); }

Jan 15, 2010
 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 ResponsesSo 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

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

May 12, 2010
 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 ResponsesKeep 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 doneAmazon 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...

Nov 19, 2010
 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 257 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 ResponsesPerhaps 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

May 5, 2009
 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