# Testing Engineer Interview Questions

Testing engineer interview questions shared by candidates

## Top Interview Questions

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

Phone interview 1 : a) Simulate a Queue with stacks ? b)Find repeated occurrence of character in a string ? Phone interview 2 : a) Given a 2D matrix of numbers find the position of number . Constraints of matrix number always in increasing order left to right and top to bottom . b)When should version control be used . And a tricky discreet math problem ? 13 AnswersWow, a lot of questions: 1. a) Something like this: public class StackBasedQueue { private final Stack store; public StackBasedQueue() { this.store = new Stack(); } public void addToTail(final Integer v) { this.store.push(v); } public Integer popHead() { final Stack temp = new Stack(); while(!this.store.isEmpty()) { final Integer v = this.store.pop(); temp.push(v); } final Integer head = temp.pop(); while(!temp.isEmpty()) { final Integer v = temp.pop(); this.store.push(v); } return head; } public int size() { return this.store.size(); } } 1. b) Something like this: O(n) runtime. public void findRepeats(final String str) { this.map.clear(); final char[] array = str.toCharArray(); for(int i = 0; i < array.length; i++) { final Character c = array[i]; Integer count = this.map.get(c); if(count == null) { this.map.put(c, 1); continue; } count++; this.map.put(c, count); } } For a) further challenge was to simulate a double ended queue , but we ran out of time . you could maintain temp stack as permanent variable and get around doing that. b) Kind of sort of what I wrote I was asked to optimize even further , so I said XOR the array make a note of elements left , remove from original list and you have set of repeated elements . Show More Responses 2a. My idea is to first identify the column that might contain our element, then use binary search to see if our element is in that column. The column that might contain our element is the rightmost column where the first row's element is less than or equal to our target element. int[] matrixSearch(int[][] m, int numRows, int numCols, int target){ int[] firstRow = m[0][]; // not sure this works, can just use for loop to populate int targetCol = findWhichCol(firstRow, 0, numCols-1, target); int targetRow = findWhichRow(m[][targetCol], 0, numRows-1, target); if (targetRow == -1) { return null; // Element not found } return new int[] { targetRow, targetCol}; } int findWhichColumn(int[] a, int low, int hi, int target) { int midIndex = (hi+low)/2; int mid = a[midIndex]; if (mid > target) { return findColumn(a,low,midIndex-1,target); } while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } return midIndex--; } int findWhichRow(int[] a, int low, int hi, int target){ int midIndex = (low+hi)/2; if (midIndex == target) { return midIndex; } if (hi-low == 0) return -1; // Element is not in the matrix if (midIndex < target) { return findWhichRow(a,midIndex+1,hi,target); } return findWhichRow(a,low,midIndex-1,target); } Average: O(log n) Worst: O(n/2) = ~ O(n) This isn't very elegant. How would you do it? @above: I think the run time is log(n)*log(m) Sorry, Log m + log n for 2a you had to describe the properties of the matrix , the diagonal elements have some unique properties which you can recognize . So a good start is initialize the search from of the corners of the non leading diagonal . and yes iterative or divide and conquer from thereon after. @Anonymous That's correct, but this part: while (mid <= target && midIndex < a.length-1) { midIndex++; mid = a[midIndex]; } makes it O(n) in the worst case. Right? @Interviewee Thank you for the additional explanation. You seem quite qualified. Is there a particular reason you think you weren't given a offer? Did any one interview go poorly? It's a little worrying to look through these interview reports and see so many apparently intelligent people not receive offers. I recently passed my phone interview and am waiting to schedule my on-site. As much as I agree with hiring only the best, I'm finding it difficult to feel optimistic in light of the evidence on this site. Thank you for sharing your experience. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. Why I didn't get it ? don't know I am still in school , I applied for an internship and they said I am qualified enough for full time since I work along with school . I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this http://valleywag.gawker.com/5392947/googles-broken-hiring-process and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google . Do your best , and be calm and composed , being nervous won't help. For the program 2a you want to manipulate both indices at the same time to get a (logN) running time. @Interviewee: Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. I guess they evaluate that over questions in lunch . Answer to 1b in C++11: list findDupes(string s) { list ret; map m; for(char c : s) { m[c]++; if(m[c] == 2) { ret.push_back(c); } } return ret; } |

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

How would you determine if someone has won a game of tic-tac-toe on a board of any size? 14 AnswersCheck all rows, check all columns, check two diagonals. If there exists a diagonal, row or column of 'X' or 'O' someone has won the game. For a board of size N^2 runtime is N. There's a way to do this in constant time... I think maybe this question is worded a bit wrong, because given a tic-tac-toe board you would need to read in at least some of the values on the board to figure out if someone has won, and this would be impossible to do in constant time (the larger the board, the more values you would have to read). I think they must mean how can you determine if someone has won during a game in real time, as in checking after every move. This can be solved with a strategy in constant time. My solution would be: Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X's or O's horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won. I would bet there is a more elegant solution than creating a large array, but since this isn't my job interview I can't be bothered trying to figure one out. :) Show More Responses You would determine the winner by identifying the first player to string together three consecutive X's or O's. The size of the board is irrelevant. You are looking for the winner. The easy and obvious answer is to check the happier player, not the board. While this may ignore the "engineering" side of the question, it does demonstrate the logic of searching for the simplest answer becuase that solution will be the same regardless of the board configuration. Happier player doesn't always mean the winner. A father teaching his son how to play tic tac toe for instance could be happier if his son actually beat him at the game. Your "simplest answer" is wrong. Assume that you are handed a board with no prior knowledge of what has happened in the game. Assume that, to win on a board of size NxN, the player must have N 'X' characters or 'O' characters in the same row, column, or diagonal. Assume that, for our problem, we are only checking if the winner is 'X'. We have to make at least one pass through the game board, but we should be able to solve the problem in one pass without checking any cell twice. Target running time O(N^2) for a board of size NxN. boolean checkXWinner(int[][] a, int n){ int[] diagonalSums = new int[2]; int[] columnSums = new int[n]; initialize diagonalSums and columnSums with zeroes; int rowSum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] = 'X') rowSum++; columnSums[j]++; if (i == n-1 && columnSums[j] == n) return true else if (i == j) diagonalSums[0]++; if (i == n-1 && diagonalSums[0] == n) return true else if (i = n-1-j) diagonalSums[1]++; if (j == 0 && diagonalSums[i] == n) return true if (rowSum == n) return true (sorry - forgot last line, put this after if (rowSum == n)....) else rowSum = 0 // Need to reset the row counter Ask. Count the number of times X and O appear on the board. Whichever has the greater count is the winner. there can be more than one winner @count : The game can be tied even though one has greater count. iterate the board and every time you find a players symbol peek forward if the board contains other two symbols at correct indices (there are four feasible patterns). this is in constant time. Show More Responses I came across this question on a Google search for something else related to tic-tac-toe. I was just moments ago thinking of this exact problem (fastest way to determine if game is in "won" state) and I'm surprised I have not seen it here... Why check every square??? Assuming an NxN square board, ANY winning arrangement MUST include a square on the diagonal. Iterate over the diagonals, and recurse both vertically and horizontally for matches, breaking when a non-match is found. On the center square check both diagonals in addition to the vertical and horizontal. The only scenario that requires all squares to be checked is if one edge is a winning edge and even then there's a few constraints required to force it. |

The Game of Nim worded diffently. 11 AnswersThe Name of the Game. The anwer is 'Take' from the german word nimm. There is a game called 'The Game of Nim' that has a specific mathematical equation that must be utilized in order to win the game. Nimm is the German word for Take, so you must figure out the best way to take the matches without your opponent beating you at it. Show More Responses The Game of Nim is a simple board game in which you and your opponent take turns removing a number of matches from one of the rows (normally about 5 rows) of matches on the board. The person to take the last match off the board is the winner. The reason why it is of interest to us as prospective software engineers (and why you probably asked this question) is that it has some interesting binary number properties making it fairly trivial to write computer code to ensure a win every time (every time there is a starting advantage, that is). Would you like me to go into more detail? Ok, well in brief then, basically the trick is to take the number of matches in each row and represent this as a binary number. Then, either by hand or with a program, do an Exclusive Or operation on the numbers. Then whenever you take some matches, just ensure that the remaining total is always zero after your turn and you will be sure to win by the end of the game. Maybe I should also add (and I'm thinking out the box here), that sometimes we as people are up against a challenge or opponent where succeeding or beating them is seemingly reliant on chance or luck. However, with careful analysis of the problem and good strategising, it turns out it is actually possible to ensure success just about every time. On the other hand, there are times when the odds are against us from the start. Then either we must stand up for what we believe is fair (i.e. be aware and vocalise that we cannot possibly win), or else acknowledge that our opponent is worthy and will ultimately get the better of us. Yet it should be noted that we can still stay strong and be competitive from the beginning allowing us to possibly take advantage of any mistakes or weaknesses our opponents or challenges might display. That is the Game of Nim worded differently. What does this question have to do with Quality? Nim's Game If I was interviewing you and asked you that question, I would be trying to determine if you could take a simple problem and provide a simple solution. If you went off into the weeds like Andrew_Bryce did, I would be wondering how effective you would be solving tons of simple issues. Also, if you answered the wrong question (what is the Game of Nim?) and not the question I asked (how would you word differently the phrase The Game of Nim?), I would be wondering how good your communication skills were. If I were being interviewed, I would wonder about the interviewer's communication skills. "The game of Nim worded differently" isn't a question. It isn't even a sentence. "Foaming Theme" 1) I cheated 2) I didn't even know what Nim was before I looked it up Here's how I would interpret some answers and the job I would recommend for them Anonymous: Huh? I think you're trying to be a smartass, but I don't get it - Cafeteria Worker Ryan: Knowledgeable - Content provider SelenityHyperion: Knowledgeable, informative and relatively succinct - Writer Andrew_Bryce: Detail oriented and a perfectionist - Software tester, some forms of coder Astrochimp: Focused - Project Manager OneEye: Thinks his answer is the only correct one - Clearly VP material Count Negroni: Nit Picker - Editor I don't think there's supposed to be one correct answer Ha ha, jokes on me. "The Game of Nim worded differently." is not the actual question, just a vague description. I would answer: "Are you talking to me?" Because it sure sounds like you're high. Then I'd get up and leave. Strategic domination |

Most of them were expected. Almost all are problem solving questions. 1. Given a BST with following property find the LCA of two given nodes. Property : All children has information about their parents but the parents do not have information about their children nodes. Constraint - no additional space can be used 15 AnswersHint - detect the level at which the given nodes are present. Then travel upwards from that position. How about traversing from one node to root, adding each node to hashset, Then try do the same with second one, on collision return node. No, you cannot do that since you need extra space for hashset which is not allowed, I am going to post my solution in a min Show More Responses function findLCA(Node node1, Node node2) { int counter1 = 0; int counter2 = 0; Node temp; //Find the level for each node, use a temp node to //traverse so that we don't lose the info for node 1 and node 2 temp = node1; while( temp.parent ! = null) { temp = temp.parent; counter1++; } temp = node2; while( node2.parent ! = null) { node2 = node2.parent; counter2++; } /* * We wanna make them at the same level first */ if(counter1 > counter2) { while(counter1 != counter2) { node1 = node1.parent; counter1--; } } else { while(counter2 != counter1) { node2 = node2.parent; counter2--; } } while (node1.parent != node2.parent) { node1 = node1.parent; node2 = node2.parent; } System.out.println("Found the LCA: " + node1.parent.info); } //correction temp = node2; while( temp.parent ! = null) { temp = temp.parent; counter2++; } @chmielsen : your solution would work... but as said by Hamid, due to the constraint of space, you have to consider some other technique. I seems really like the question of finding intersection of two linked lists 1)consider node1 as p1. see if p1=p2 , p1->parent=p2, p2->parent=p1 2)now for a value p1 try to see recursively if p2->parent ever becomes equal to p1 or p2=root 3)set p1=p1->parent and continue till p1=p2 or p1= root temp1 = node1; temp2 = node2; while( temp1.parent != null && temp2.parent != null){ if(temp1.value == temp2.value){ return temp1; // temp1 and temp2 point to same node so pick one } temp1 = temp1.parent; temp2 = temp2.parent; } System.out.println("no such ancestor"); Consider this is a BST, where max node is always on the right of min node, we can traverse max upward one node at a time while comparing min nodes as it traverse upward toward root. BinaryNode findBSTLCA( BinaryNode min, BinaryNode max ) { BinaryNode tempMax = max; BinaryNode tempMin = min; while( tempMax != null ) { while( tempMin != null ) { if( tempMin.element == tempMax.element ) return tempMin; tempMin = tempMin.parent; } tempMin = min; // reset tempMin tempMax = tempMax.parent; // traverse tempMax upward 1 node } return null; // no LCA found } Consider that the lowest common ancestor in a binary search tree means the node value would be between the two values passed in. Because everything left is less than and everything right is greater than, we can traverse the tree using this knowledge. Here's the solution in PHP for something different: function findLowestCommonAncestor(Node $root, $value1, $value2) { while ($root != null) { $value = $root->getValue(); if ($value > $value1 && $value > $value2) { $root = $root->getLeft(); } else if ($value getRight(); } else { return $root; } } return null; //the tree is empty } howardkhl - your solution works, but this is O(n^2) complexity, making it too slow for large enough trees. Ja - your solution might work (haven't thoroughly checked it) but it violates the restriction that a parent node does not know about the child node. So this answer is invalid. The correct answer is the one given by Hamid Dadkhah, which, just like an anonymous responsder said, is the same problem as an intersecting list. you can use the following method *Node getLCA(Node *n1, Node* n2){ while(n1.parent!=null){ Node * p= n2; while(p.parent!=null){ if(n1.parent!=p.parent) p=p.parent; else return p.parent; } } } Show More Responses Pick one of the nodes in random. Keep traversing up until the property: new node is greater than one of the nodes and lesser than the other is satisfied. I was also interviewed with same question. They not only ask the solution they also ask for the time complexity of the solution. Make sure you to ask different questions and confirm the type of tree. They could give you binary search tree, binary tree, sorted binary tree. Solution will greatly depend on the type of the tree. |

Given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. What's the O notation for what you just wrote? Can you make it faster? Can you find an O(n) solution? Implement the O(n) solution 17 AnswersO(n^2) solution is just two double for loops. O(n log n) solution will use a binary tree O(n) solution will use a hash table O(n) solution possibility (no need for a data structure) void findpairs(int sum) { //given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. if (sum == 0) { cout 0) { for(int i = 0; i((sum/2)-1) && i>-26; i--) { if( (i - sum+i) == sum) { cout << i << " " << sum+i << "\n"; } } } } @Mike "if( (i + sum-i) == sum)" will always give you "sum". Show More Responses @Mike: if (sum == 0) does not imply 0,0. It implies -50,50; -49,49; -48,48,... Has anyone found the O(n) solution??? I'm having trouble with this one... Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n). Now, foreach key 'k', with value 'v': if k == v: there is a match and that is your pair. this will take another O(n) pass totale O(2n) ~ O(n) Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like -50 + 50 -49 + 49 -48 + 48 etc.... etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2). Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time. def pairs(k, minimum, maximum): if k >= 0: x = maximum y = k - maximum else: x = k + maximum y = minimum while x >= k / 2 and y <= k / 2: print str(x) + " , " + str(y) + " = " + str(x + y) x = x - 1 y = y + 1 here is my solution using hash table that runs in O(2n) => O(n): public static String findNums(int[] array, int sum){ String nums = "test"; Hashtable lookup = new Hashtable(); for(int i = 0; i < array.length; i++){ try{ lookup.put(array[i], i); } catch (NullPointerException e) { System.out.println("Unable to input data in Hashtable: " + e.getMessage()); } } int num2; int num1; for (int i = 0; i < array.length; i++){ num2 = sum - array[i]; Integer index = (Integer)lookup.get(num2); if ((lookup.containsKey(num2)) && (index != i)){ num1 = array[i]; nums = array[i] + ", and " + num2; return nums; } } //System.out.println(lookup.get(-51)); return "No numbers exist"; } The number you're looking for is T. You can just create an array of size 101. Then you loop through the array, and drop each number i in cell of index i-50. Now you do a second pass, and for each number, you look at the number at index T-i-50. If there's something there, you have a pair. typedef pair Pair; list l; //create an empty list of tuples pairofsum(l,10); // an example of how to call the function which adds to your list of tuples the possible pairs of the sum void pairofsum(list& l,int sum) { if(sum==0) { Pair p; loadPair(p,0,0); l.push_back(p); for(int i=1;i<51;i++) { loadPair(p,i, -i); l.push_back(p); } } else if (sum<0) { Pair p; for(int i=0;i+-sum<51;i++) { loadPair(p,i,-(i+-sum)); l.push_back(p); } for(int i=1;i<=-sum/2;i++) { loadPair(p,-i,sum+i); l.push_back(p); } } else { Pair p; for(int i=1;sum+i<51;i++) { loadPair(p,-i,sum+i); l.push_back(p); } for(int i=0;i<=sum/2;i++) { loadPair(p,i,sum-i); l.push_back(p); } } } void loadPair(Pair& p, int f, int s) { p.first=f; p.second=s; } Here is my C# implementation. It runs O(N) and doesn't include duplicate pairs (e.g. including [50,-50] as well as [-50,50]). static void FindPairs(int sum) { for (int i=-50; i=-50) { Console.WriteLine(i + " " + otherNum); } } } Solution with no duplicates: @Test public void findPairsTest() { // TestCases // Alternately you can put this test cases in dataprovdier findPairs(50); findPairs(20); findPairs(-20); findPairs(-50); findPairs(0); } private void findPairs(Integer sum) { HashMap inputPair = new HashMap(); HashMap outputPair = new HashMap(); for(int i=-50; i<=50; i++) { inputPair.put(i, sum-i); } // print pairs for(Integer key : inputPair.keySet()) { Integer potentialOtherNum = inputPair.get(key); if(inputPair.containsKey(potentialOtherNum) && potentialOtherNum < key) { outputPair.put(key, potentialOtherNum); } } System.out.println(outputPair.entrySet().toString()); } Here is the solution in O(n) time complexity. http://www.knowsh.com/Notes/NotesSearch/NotesDetail/140226/Program-To-Find-All-The-Pairs-In-The-Given-Set-That-Add-Up-To-A-Certain-Sum Please let me know if there is any thing I missed. Show More Responses Use two pointers, one at the begin, one at the end, let us call the pointer begin and end, the array is named nums. If nums[begin]+nums[end]>target, end--;if end Half=sum/2; i=1; While (half+i -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); } half=sum/2; i=1; While (half+i \ -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); } Weirdly the less than and greater than signs make the text between them invisible. The conditional statement is supposed to say Half=sum/2; i=1; While (half+i LESSTHAN 51 && half-i GREATERTHAN -51) |

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

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

Given a list of n numbers. All numbers except one are unique. Find the number with duplicate entry. 10 AnswersI gave an nlogn solution, where I said we will heap sort / quick sort the array, and then do a linear traversal to find out the duplicate entry. The interviewer was okay with the solution, and then she asked me code it, and then to write test cases for it. How about using hashtable? Use the function n(n+1)/2 = sum(0,n). Sum up all of the numbers in the array. Subtract the number from the function from the number in given by the sum. That will be your duplicate entry. public static int dupeNum ( int [] array ){ int arraySum = 0; int arraylength = array.length; int knownSum = (arrayLength * ( arrayLength + 1 ) ) / 2; for (int i : array ){ arraySum += array[i]; } return (arraySum - knownSum) ; } Should be O(n). Show More Responses ^^ person who replied above: Your solution fails if the numbers aren't sequential - for all you know, 'a list of n numbers' could be 'n' random numbers Merge sort it and then it iterate through the list. This takes nlogn time. public in getDuplicate(List list) { List sortedList = Mergesort(list); for(int i = 0; i < sortedList.length-1; i++) if(sortedList[i] == sortedList[i+1]) return SortedList[i]; Throw exception; } take XOR of all the numbers.You will get the sum with out the duplicated number. (sum of all n - above sum) will give you the number put the numbers into hashmap while traversing the list. Before placing the key into hashmap check whether it is null or not. if it isnot you've found it. worst case O(n). extra hashmap in the memory. i would sort them in n log and then traverse them. while traversing, chech two adjacent numbers are different. if not, that is the number. Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right. Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right. |

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

You have 2 buckets in a room and one bucket has 17 Red balls, 19 Green Balls, 21 Blue Balls, 23 Yellow Balls. You are blindfolded and you need to pick one ball at a time and put in the bucket#2. You should stop at a point where you are confident that the color of the ball you are putting in already exists in the bucket#2. When would you stop? 9 AnswersWorst case - you stop at the 5th chance because after 4 different colored balls the 5th ball color has to repeat. Best case - you stop at the 2nd chance because you get the same color ball after 1st. But it asks when will you be confident about that. So I guess it is after the 5th ? But what if all of the first 4 you pick are of the same color? Then the 5th may not be already in bucket 2. Going by that logic, I feel you'll have to pick (23+21+19+1) = 64 balls in the worst case, where the first 23 you pick are all yellow, the next 21 are blue, next 19 are green and the last one is red. What do you guys think? Show More Responses Gautam, your answer would have been correct if the question would have been - "You should stop at a point where you are confident that 'all four' color balls you are putting in already exists in the bucket#2 I think 24 balls...The highest ones + 1 I think 3 is the answer. 64, by worst case After the 2nd ball 65th chance. In worst case, you may pick all all balls of same color one after another. And so you cannot confidently stop till 23+21+19+1 balls are picked. The ball you pick need not be essentially red, it may be any color and you can confidently stop picking balls. |

Asked to implement a function that takes an integer and returns whether or not the number had an odd or even number of 1 bits. 6 AnswersIt started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n). If the task is only for positive numbers, then my solution would be: bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; do { result |= ((n % 2) == 1); n /= 2; } while ((n / 2) != 0); return result; } Show More Responses mod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster. > bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; while(n != 0) { result |= ((n & 0x01) == 1); n >> 1; } return result; } masking is faster than a mod operator, and bit shifting is faster than divisions i was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011. I guess changing the line to: result ^= ((n & 0x01) == 1); will do the job... PC, your solution is incorrect. It will always return true if the number has at least one set bit. |

**1**–

**10**of

**3,230**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Test Engineer
- Software Engineer In Test
- Software Test Engineer
- Senior Software Engineer
- QA Engineer
- Software Development Engineer In Test
- Software Developer
- Software Development Engineer
- Software Development Engineer In Test (SDET)
- Intern
- Software QA Engineer
- Quality Assurance Engineer
- Hardware Engineer
- Associate Software Engineer
- Engineering
- Software Engineer Intern
- Senior QA Engineer
- Software Development Engineer in Test
- Senior Software Engineer In Test