# Software Test Interview Questions

Software test interview questions shared by candidates

## Top Interview Questions

Describe and code an algorithm that returns the first duplicate character in a string? 7 AnswersSimple Python example. Not sure it's most efficient. def findDup(str): match=[] i=1 while (i<len(str) and len(match)==0): for j in range(i): if str[j]==str[i]: match=[j,i] i+=1 return match if __name__ == '__main__': print findDup('asdf') print findDup('asdfasdf') pass first clarify if it is ASCII or UNICODE string For ASCII, create BOOL checkArray [128] = {false}; walk the string and update the index of checkArray based of the character. for (int index=0;index< strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } public class FirstDupCharacter { public static void main(String[] args) { System.out.println(findDupCharacter("abcdefghiaklmno")); } private static Character findDupCharacter(final String input) { final Set set = new HashSet(); Character dup = null; for (int i = 0; i < input.length(); i++) { if (set.contains(input.charAt(i))) { dup = input.charAt(i); break; } else { set.add(input.charAt(i)); } } return dup; } } Show More Responses String samp = "Testing"; samp = samp.toLowerCase(); char chararr[] = samp.toCharArray(); int size = chararr.length; char repeat = ' '; for (int i=0;i<size && repeat==' ';i++) { for (int j=i+1;j<size && repeat==' '; j++) { if (chararr[i]==chararr[j]) { repeat = chararr[i]; } } } System.out.println("First Repeating character :: "+repeat); for (int i=0;i<size;i++) { if (samp.indexOf(chararr[i]) != samp.lastIndexOf(chararr[i])) { System.out.println("First repeating char ::"+chararr[i]); break; } } public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index < characters.length; index++ ) { // insert the character into the map. // returns null for a new entry // returns the index if it previously if it existed Integer initialOccurence = charsMap.put(characters[index], index); if ( initialOccurence != null) { return initialOccurance; } //there where no characters that where duplicates return -1; } } Another python solution: def findFirstNonRepeatedCharInOneIteration(str1): for i,j in enumerate(str1): if j in str1[:i] or j in str1[i+1:]: print "First non-repeated character is "+ j break str1 = "abcdefglhjkkjokylf" findFirstNonRepeatedCharInOneIteration(str1) |

Write a method to decide if the given binary tree is a binary search tree or not. 4 Answersfor binary search tree, inorder traversal should result in sorted array in the increasing order. Further, know that the difference between the two is that a binary search tree cannot contain duplicate entries. recur down the tree - check if element is already in hashtable - - if it is, return false - - if it isnt, insert element into the hashtable - - - recur to children I'm sorry but Anon's answer is not correct, at least according to "Introduction to Algorithms, 3d Edition" by Cormen. The binary search tree property says that there CAN be duplicates: "Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key = x.key." In other words, the value of a child node may be equal to the value of a parent node, which would yield the result that "Interview Candidate" posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes. Show More Responses public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER) { if (root == null) // children of leaf nodes { return true; } return root.data >= INTERGER_MIN && root.data <= INTEGER_MAX && isValidBST(root.left, INTEGER_MIN, root.data) && isValidBST(root.right, root.data, INTEGER_MAX) } |

In a given sorted array of integers remove all the duplicates. 6 AnswersIterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N The array is already sorted, no need for a set. example: 2,2,5,7,7,8,9 Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n) public RemoveDuplicates() { int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 }; int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ; for (i = 1; i <= ip.Length - 1; i++) { if (ip[i - 1] != ip[i]) { op[j] = ip[i - 1]; j++; } } if (ip[ip.Length - 1] != ip[ip.Length - 2]) op[j] = ip[ip.Length - 1]; int xxx = 0; } Show More Responses def removeDuplicatesSecondApproach(inputArray): prev = 0 noRepeatIndex = 0 counter = 0 for curr in range(1,len(inputArray)): if (inputArray[curr] == inputArray[prev]): counter = counter + 1 prev = curr else: inputArray[noRepeatIndex+1] = inputArray[curr] noRepeatIndex = noRepeatIndex + 1 prev = curr inputArray = inputArray[:-counter] return inputArray if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } Apologies for the previous incomplete answer int[] inpArr = {1,2,2,3,4,5,5,5,8,8,8,9,13,14,15,18,20,20}; int[] opArr = new int[inpArr.length]; int opPos = 0; for(int i= 0; i<=inpArr.length - 1; i++) { if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } |

how can a particular application be tested apart from testing its functionality 3 AnswersReliability Test, Stability Test, UI Test, Platform Test, Also include, performance, stress & load testing Accessibility, user experience, globalization, localization, integration, compatibility |

Write code in your favorite programming language that will accept two strings and return true if they are anagrams. 2 AnswersThis was not really that hard to write it, however the interviewer asked me to reduce the complexity. My initial version had n*log(n) complexity and he asked me to reduce it to no more than n complexity. If you have had some upper level Computer Science classes this is not too difficult, however what they are looking for is a way to stump you. If you adjust your code or thinking rapidly to their request they will change it again until they find something that you have trouble with. Do not be discouraged by this, it is the interviewers job to determine how much you know! Found this good link. Time complexity is O(n). http://www.dreamincode.net/code/snippet1481.htm The algorithm can still be improved but gives some basic idea on how to implement. |

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

Implement a binary tree and explain it's function 4 AnswersBinary Search tree is a storage data structure that allows log(n) insertion time, log(n) search, given a balanced binary search tree. The following implementation assumes an integer bst. There's a million implementations. Just look on wikipedia for search and insert algorithms. Hi Xin Li, A binary tree is not the same as binary search tree.. A binary tree is a tree in which every node has atmost two children nodes. It is a k-ary tree in which k=2. A complete binary tree is a tree in which all nodes have the same depth. The fact is ttttttt t t. T to t. To. A a aaAs Sdsassss. Show More Responses Hello, Thank you for sharing your interview experience. As a small team of ex-Google employees, we have recently launched a new website, interviewjoy.com, where you can earn money by sharing your interview experiences/insights with other job candidates. (It is a marketplace for sharing job interview insights). Posting an interview consultancy service is totally free & anonymous and we are giving 50 USD sign-up bonus for the first 500 users. You are kindly invited to interviewjoy.com to check it out. Users already started making money on the website! Best Regards.. (For more information: onboarding@interviewjoy.com) |

Given a string (understood to be a sentence), reverse the order of the words. "Hello world" becomes "world Hello" 1 Answer2 ways. At the low level: reverse the entire string. 'Hello World' becomes "dlroW olleH". Then reverse each word, becomes "World Hello". At a higher level: Tokenize the words and push them onto a stack, then pop them out. |

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

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

**1**–

**10**of

**1,354**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Software Development Engineer
- Senior Software Engineer
- Software Developer
- Software Development Engineer In Test
- Software Engineer In Test
- QA Engineer
- Intern
- Software Development Engineer II
- Software Test Engineer
- Software QA Engineer
- Program Manager
- Senior Software Development Engineer
- Test Engineer
- Software Development Engineer I
- Quality Assurance Engineer
- Software Engineer Intern
- Business Analyst