Software Test Engineer Interview Questions | Glassdoor

# Software Test Engineer Interview Questions

1,657

Software test engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Dec 6, 2012

### Software Development Engineer In Test (SDET) at Microsoft was asked...

Mar 16, 2011
 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) solution17 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 tableO(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 + 1here 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 ResponsesUse 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 endHalf=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)

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 Development Engineer In Test at Amazon was asked...

May 20, 2010
 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 numbersMerge 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 numberput 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.

### Software Development Engineer In Test at Amazon was asked...

Jan 27, 2012
 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 Responsesmod 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 divisionsi 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.

### Software Development Engineer In Test (SDET) at Microsoft was asked...

May 13, 2013
 Given a binary tree, how would you set the keys/values of all the nodes and their child pointers to null. No language restriction. Do it iteratively in O(N) time with O(1) space complexity where N is the number of nodes in the tree. Other Details: - Tree is just a regular Binary Tree and doesn't have the BST property. - It is not guaranteed to be balanced. - You may do whatever you want to the tree however, you must ensure that all the nodes in the tree and their left/right pointers are set to null. 5 AnswersI will leave the reader to think about the question. Suffice it to say, focus on the fact that you can alter the structure of the tree...Do a post-order traversal, set node to null as it recurse back? void setNodesToNull(Node root) { if (root == null) return; setNodesToNull(root.left); setNodesToNull(root.right); root = null; return; }Nevermind, it has to be done "iteratively".Show More ResponsesWith the assumption that you do not have to preserve the initial tree couldn't you just iteratively continue to remove the root of the initial tree, set to null, replace root with child and with the null root build a new tree?What if you have two child nodes? How do you ensure that you are not loosing a reference to a child node before you have the opportunity to 'free' it?

Nov 20, 2009
 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 Development Engineer In Test at Amazon was asked...

Jan 27, 2012
 First explain what a tree, then binary tree, then a binary search tree is. Now implement a function that verifies whether a binary tree is a valid binary search tree.5 AnswersSadly I ran out of time for this question. But I e-mailed the response after my time was up. First create a small implementation of a binary tree, I did it in java with the standard implementation Nodes with left and right children as data points. Check whether the left child and right child have valid values, which is to say make sure all children on the right of a node have values greater than parents that they came from. The key thing that I missed during the interview was the fact that if you traverse once to the right, then once to the left, you have to make sure the value is between the max and min that you've encountered up to that point.int validate_BST(struct tnode *tree){ int ret1, ret2; if (tree == NULL) return 1; else { if (tree->left != NULL){ if (tree->data > tree-left->data){ ret1 = validate_BSR(tree->left); } else return 0; } if (tree->right != NULL) { if (tree->data right->data){ ret2 = vaidate_BSD(tree->right); } else return 0; } return (ret1 == 1 && ret2 == 1)? 1: 0; } return 0; }To find whether a binary tree is valid Binary search tree, do inorder traversal and check if the nodes are sorted.Show More Responsesprivate boolean isBST(){ return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isBST(Node node, int min, int max){ if(node == null) return true; if(node.data max) return false; else return (isBST(node.left, min, node.data) && isBST(node.right, node.data+1, max)); }In order to verify the Binary Search Tree, Read the nodes in Inorder mode. Also at every step check if the current node value is less than the one previously found then exit the traversal as the items are not sorted.

### Software Development Engineer In Test at Amazon was asked...

Dec 6, 2012
 2. Find top 100 maximum number from a continuous input stream.6 AnswersUse a min heap to store the top 100 maximum numbers. If the incoming number is greater than the top element replace it and sort the heap.Use a sorted generic list. If the number of elements is < 100 Add the incoming number to the list. else if the incoming number is greater than the zero element of the list Add the incoming number to the list remove the zero element from the list to keep the number of elements at 100.The interview candidates solutions is the best, n insertion * log n for each heap insert - > nlogn Developer: n * n = n^2Show More ResponsesI think the key of the question would be 100, a fixed number. The sorting time of 100 numbers would always be O(1).There is a blog discussing a similar coding interview question at http://codercareer.blogspot.com/2011/09/no-05-least-k-numbers.html. The first solution is suitable for this problem."I think the key of the question would be 100, a fixed number. The sorting time of 100 numbers would always be O(1)." This is bad design given that if it was something other than 100, then this does not hold true. Even if it was always true, using a heap (or Priority Queue in java) will give you a better run time. Here's why: for each insertion you will sort, this will be 100*log(100) for each incmoming number, and you might have to remove a number, which will be logn (assuming you are using an array and using binary search to search the element), and finally, o(1) for each insertion... using a priority queue will give you log(100) for each removal, and log(100) for each insertion, and o(1) for a comparison with the head of the heap comparing solutions this is: 100*log(100) + log(100) + 1 V.S. log(100) + log(100) + 1, solution 2 is much better timewise, and spacewise it is the same.

### Software Development Engineer In Test Consultant at HCL Technologies was asked...

Aug 29, 2009
 What is a class?4 AnswersJust because you have years of programming experience, doesn't mean you won’t be asked entry-level question. Prepare for this.This is a reasonable question for a senior person - you should be able to explain basics to a client, manager or junior person. So a answer could be: A class is a group of objects with shared properties. Using classes reduces time needed for new coding and simplifies changes.Take responsibility for your actions. For someone with that much experience, you can't answer this stupid question? I do interviews and hires and if you gave me that lame excuse, I would terminate the interview on the spot. Every resume I look at looks the same (same experience, job titles, job responsibility). You need to make the difference in the interview, this is what distinguish you from the other 100 candidates. Hate to say it but, with the economy the way it is, it is easier to be choosy on who I hire.Show More ResponsesThis guy (interview candidate) is hilarious, those three questions are the most fundamental concept of OOP, and he consider OOP entry-level? LOL. What have you done at Microsoft? Non-programming related job? Go back to any college and take a CIS 200 level class. Experience at Microsoft is not a pass for interview questions.
1120 of 1,657 Interview Questions