# Software Test Engineer Interview Questions in Mountain View, CA

Software test engineer interview questions shared by candidates

## Top Interview Questions

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

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

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 |

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

Onsite Interview 2 a): check whether a number is the power of 2 b) Skyline silhouette puzzle . c) Discussion on uses of hash-tables and trees ? d) Few general questions on Work and academic background . 5 Answers2a. Simple solution: boolean isPowerOfTwo(int n){ double d = (Math.log(n))/(Math.log(2)); // == log(base 2) n if (d == Math.floor(d)) return true; return false; } Without Java Math class: boolean isPowerOfTwo(int n){ int x = 1; while(true){ if (x == n) return true; if (x > n) return false; x = x * 2; } } or boolean isPowerOfTwo(int n){ if (n < 1) return false; while(n != 1){ if (n % 2 != 0) return false; n = n/2; } return true; } Are there any problems with these approaches? What might be a better approach? boolean isPowerOfTwo (int a) { return (a&(a-1)==0); } @ellemeno: You are expected to give the solution as Anonymous which by the way can be done in java as well , ( it's generally called bit wise operations) Show More Responses @ellemeno: You are expected to give the solution as Anonymous which by the way can be done in java as well , ( it's generally called bit wise operations) @ellemeno: You are expected to give the solution as Anonymous which by the way can be done in java as well , ( it's generally called bit wise operations) |

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

Design a function which returns the number of set bits in a given number, when expressed in binary 4 Answersint numBits(int num) { int numBits = 0; while(num > 0) { if(num % 2) numBits++; num /= 2; } return numBits; } The question stipulates "a number", but the code assumes "a positive integer". (It also assumes the number expressed in binary has a C compiler's default number of bits for type int (e.g. 32); that's probably acceptable since a real-world case would likely specify that type. ) Consider: /* return n of set bits in a signed int */ int numBits(int num) { int numBits = 0; while (num != 0) { if (num < 0) ++numBits; num <<= 1; } return numBits ; } You may get faster results with some precomputing... /* lookup table with number of bits set per byte */ const short lookupTable[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, ... }; int numBits(int num) { unsigned char *p = (unsigned char *)# // not necessarily required, but makes for easier reading return lookupTable[p[0]] + lookupTable[p[1]] + lookupTable[p[2]] + lookupTable[p[3]]; // assumes 32 bit integer } Show More Responses Use a logarithm, base-2. def num_bits(n): return int(math.log(n, 2) + 1) |

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

Given a list of integer e.g. (1,2,4,5,6,7,8...) Find a pair with a given sum. 5 Answersimport java.util.NoSuchElementException; import java.lang.IllegalStateException; class PairWithSum { //O(n^2) static int[] findPairWithSum(int[] n, int sum){ int index = indexLessThanSum(n, sum); for(int i = index; i>0; i--){ for(int j = i-1; j>=0; j--){ if(n[i] + n[j] == sum) return new int[] {n[i],n[j]}; if((n[i] + n[j]) 0 && n[i]>sum){ int s = i / 2; if(n[s] 0 && e java PairWithSum 13 8 + 5 = 13 > java PairWithSum 6 5 + 1 = 6 > java PairWithSum 20 Exception in thread "main" java.util.NoSuchElementException: No such pair exists that sums up to the number 20 >java PairWithSum 0 Exception in thread "main" java.util.NoSuchElementException: The smallest element in the given list of numbers is bigger than the given sum public class PairSum { int [] arr = {1,2,4,6,8,10,12}; //assume in sorted order else first sort int sum = 16; void findPair(){ int i=0, j=arr.length-1; while(j>i){ if(arr[i] + arr[j] == sum){ System.out.println(arr[i] + "," + arr[j]); i++; j--; } else if( arr[i] + arr[j] > sum){ j--; } else if (arr[i] + arr[j] < sum){ i++; } } } public static void main(String[] args) { new PairSum().findPair(); } } In C++11, using pair, list, and map class. I decided to use a map class so that the look up was faster than linear search and also gets rid of the duplicate entries. The function takes in the int sum value, list of int, and output parameter in the form of pair when the sum was found. It returns true when the two numbers are found and false if it failed to find any: bool findSum(int sum, list intList, pair& output) { map intBoolMap; for(int i : intList) { intBoolMap.insert(make_pair(i,true)); } for(auto i : intBoolMap) { int diff = sum - i.first; if(intBoolMap.find(diff) != intBoolMap.end()) { output.first = i.first; output.second = diff; return true; } } return false; } Show More Responses I'm assuming this is a list of unique numbers. If not we can just use a hashmap to also store its count, but i'll assume otherwise. Put all numbers in a hash set. Go through list of numbers. Subtract number from sum and if the set contains the result, return that pair. static void Main(string[] args) { // Given a list of integer e.g. (1,2,4,5,6,7,8...) Find a pair with a given sum. int[] num = { 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 1, 3, 4 }; int sum = 13; bool stop = false; Console.Write("Original numbers: "); for (int i = 0; i < num.Length; i++) { Console.Write(num[i] + " "); } Console.WriteLine("\n"); for (int i = 0; i < num.Length; i++) { int first = num[i]; for (int j = i+1; j < num.Length; j++) { //if (num[j] == first) { continue; } int second = num[j]; if (second + first == sum) { Console.WriteLine(first + "+" + second + "=" + sum); stop = true; break; } } if (stop == true) { break; } } Console.ReadLine(); } output: Original numbers: 1 1 2 3 4 5 6 7 8 9 9 1 3 4 4+9=13 |

How can you write a recursive function calculating the exponential of a number? 2 Answersf(n) = a if n=0. f(n) = a*f(n-1) otherwise. //Imports using System; //Test class class Test { //Constructor public Test() { //Nothing } public int RecursiveExp(int x, int n) { //First base case if (n == 0) { return 1; } //Second base case if (n == 1) { return x; } //Even values of (n) if (n % 2 == 0) { int y = RecursiveExp(x, n / 2); return y * y; } //Odd values of (n) else { int y = RecursiveExp(x, n - 1); return x * y; } } } //Main class class Program { //Main static void Main(string[] args) { //Create a test object Test tst = new Test(); //Examples Console.Out.WriteLine(tst.RecursiveExp(2, 0)); Console.Out.WriteLine(tst.RecursiveExp(2, 1)); Console.Out.WriteLine(tst.RecursiveExp(2, 3)); Console.Out.WriteLine(tst.RecursiveExp(2, 4)); } } |

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

What is http? 1 AnswerThe answer to the question, "What is HTTP?" is: HTTP is the application level Internet protocol for the exchange of hypertext between client and server. Hence the name, which is an acronym for "hypertext transfer protocol". |

### Software Engineer In Test at C3.ai was asked...

// Merge 2 2-dimensional arrays into one 2-dimensional array. // example input: // { 1, 2, 3; // 4, 5, 6} // { 7, 8, 9; // 10, 11, 12; // 13, 14, 15} // example output: // { 1, 2, 3; // 4, 5, 6; // 7, 8, 9; // 10, 11, 12; // 13, 14, 15} 1 Answer//this solution only does the loop through for the first 2-D array. Do it similarly for the second one as well. class Solution { public static void main (String[] args) { Solution interview = new Solution(); Integer[][] input1 = {{1,2,3},{4,5,6}}; Integer[][] input2 = {{7,8,9},{10,11,12},{13,14,15}}; Integer[][] result = interview.mergeArrays(input1,input2); for(int i=0;i |

### Software Engineer In Test at C3.ai was asked...

Write a function to decode roman numerals. Give test cases to test your code. M=1000 D=500 C=100 L=50 X=10 V=5 I=1 III=3 VI=6 VIII=8 III X = 7 VVVX = -5 MCMLXXII = 1972 MCMXXXCII = 1972 CCCXLV = 345 MDCLXVI = 1666 1 AnswerHashMap myReferenceHash = new HashMap(); //ADD ALL THE KEY VALUES HERE myReference.add(key, value); //... as many times as you want to add the key values. public int decodeRomanNumerals(String inputRoman){ // if(isRomanNumeral(inputRoman)){} int outputNumeral = 0; int i = 0; int temp = 0; while(i = myReferenceHash.get(inputRoman.charAt(i+1))) { temp = temp + myReferenceHash.get(inputRoman.charAt(i+1)); outputNumeral = outputNumeral + temp; } i++; } system.out.println(outputNumeral); return outputNumeral; } test cases : 1. integer input -> throw an exception / error -> must prompt the user to correct the input 2. code to check whether the hash keys point to integer values // this can be done while adding the values to the hashtable. If a non integer value is entered parseInt or some other efficient methodology can be used always to make sure any input is automatically parsed and only the integer value is taken 3. default return value (return 0 / return null ) or an error message which will be the first indicator that the function is not adding values as expected 4. have a pre defined list of valid roman numerals and check if the input string passes for a roman numeral -> can have a function that returns a boolean value for true / false |

**1**–

**10**of

**70**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Senior Software Engineer
- Test Engineer
- Software Developer
- QA Engineer
- Software Development Engineer
- Software Test Engineer
- Software Development Engineer In Test
- Software QA Engineer
- Intern
- Software Engineer Intern
- Senior Software Engineer In Test
- Software Development Engineer In Test (SDET)
- Staff Software Engineer
- Software Engineer II
- Software Engineer III
- Senior QA Engineer
- Engineering
- Product Manager
- Software Engineering