# Testing Interview Questions

Testing interview questions shared by candidates

## Top Interview Questions

In a BST write a program to find 2 nodes x and y such that X+y=k 4 AnswersI think we need to do traversals and check for every node. For a given x traverse nodes upto x + y <= k. This problem requires the use of a map aka dictionary aka hashtable. Visit a node If the node data isn't in the map; add the data to the map. Solve for what the other number should be; check if it's in the map. if it is you're done... otherwise keep searching. Show More Responses You can solve the problem in O(n) time. First you find the smallest number in the tree then you find the highest number (worst-case linear time, logarithmic time if the BST is balanced). If their sum is larger than K, you find the largest number in the tree that is lower than y (you can do it in amortized constant time) If their sum is lower than K, you find the smallest number in the tree that is higher than x (amortized constant time). And you continue this algorithm until you reach the correct X and Y :) |

given two linked lists with a digit in each node, add the two linked lists together. the result must be a linked list with one digit in each node. use only one iteration of the two input lists. 5 AnswersIs this to remove duplicates from linked list or just combining both the linked lists blindly? assume the numbers you need to add are 560 and 890. the result should be 1450. so linked list A will have 5 -> 6 -> 0 and linked list B will have 8 -> 9 -> 0 so you must add them together to produce 1 -> 4 -> 5 -> 0. i believe the reason for an algorithm like this is to have a method of adding arbitrarily large numbers together. rather than storing an integer as int32 or int64, we can store the int as a linked list, which can be any size integer we want. Of course, the underlying 'int' we use for the data of the linked list only needs to be 4 bits to cover 0-9 in decimal. public static List AddTwoLists(List first, List second) { return first.Zip(second, (a, b) => a + b).ToList(); } Show More Responses i don't believe this answer is correct. you must account for cases where you will carry a 1. for example, if node A_i is 5 and node B_i is 7, then C_i = 2 and C_(i-1) = C_(i-1) + 1. In short, you must consider the carry value. I don't see that your solution considers this. Your solution would make C_i = 12, but 12 is two digits, not one. I think the answer should traverse both link lists and add each node data and make a new link list with digit on each node of the answer. In this way we can traverse in N time and at the end if any nodes are left in second link list we can attach them at the end of new link list |

### Test Engineer at Broadcom was asked...

Given Vcc and 2 capacitors A and B in series to ground, what is the voltage in between 4 AnswersSomewhere in between Vb=(Cb/Ca+Cb)V I mean Vb=(Cb/(Ca+Cb))V Show More Responses It depends on the initial condition.... if both capacitors were discharged to 0V at first, and then one side is charged to Vcc, then the answer would be Vb=(Ca/(Ca+Cb))Vcc Vcc---Ca----Cb----gnd However since there was no initial conditions given , the middle voltage could be anything if the capacitors are ideal |

Write a function to find the maximum sum of sub array where the array can have negative and positive numbers. 4 AnswersDon't jump to the answer. As some of you noticed, the question has ambiguties. Ask questions to clarify the question. They would like you to solve the problem after understanding all the details so that you won't miss any edge cases in your solution. Hint: The answer is recursive. answer in java: int array[] ={1,2,3,-6,5,6,9}; table = new int[7][7]; int i, j; int localMax = -999999999; for(i = 6 ; i >= 0 ; i--) for(j = i ; j < 7 ; j++) { if(i == j) table[i][j] = array[i]; else table[i][j] = array[i] + table[i+1][j]; localMax = Math.max(localMax, table[i][j]); } System.out.println(localMax); In Python: def largest_segment(s): y = 0 z = 0 for i in range(0, len(s)): y = max(y + s[i], 0) z = max(z, y) return z Algorithm is O(n). Only works if the max value for an array containing all negatives is 0. Show More Responses def maxSumSubArray(inputArray): currentSum = 0 grandSum = 0 for i in range(len(inputArray)): if (currentSum + inputArray[i]) < currentSum: currentSum = 0 continue else: currentSum = currentSum + inputArray[i] if (grandSum < currentSum): grandSum = currentSum return grandSum |

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

Coding question - given a binary tree, write code to count the sum off all siblings. 3 AnswersNot sure if this works... value == null) return $sum; $sum = $sum + $tree->value; countSiblings($tree->left,$sum); countSiblings($tree->right,$sum); } ?> int totalNumberOfNodes(Node root) { if(root == null) return 0; return 1 + totalNumberOfNodes(root.left) + totalNumberOfNodes(root.right); } private int siblingCounter = 0; public int countSiblings(BinaryNode node) { if(node.element == null) { return siblingCounter; } else { siblingCounter++; if(node.right() != null) { countSiblings(BinaryNode right); } if(node.left() != null) { countSiblings(BinaryNode left); } } return siblingCounter; } |

Implement a Queue using 2 Stacks 3 AnswersUntil the first de-queue operation, keep pushing one of the stacks, say stack1, for every enqueue operation. When you encounter the first dequeue operation, then pop stack1 into stack2. Now, pop stack2, to get the dequeued element. Henceforth, on every dequeue operation, pop stack2, and on every enqueue operation, push stack1. At some point, stack2 might become empty, but this brings you back to the first stage ! Here is an idea: public class StacksQueue { private readonly Stack stack1 = new Stack(); private readonly Stack stack2 = new Stack(); private Stack dequeueStack; private Stack queueStack; private Stack secondaryStack { get { if (object.ReferenceEquals(queueStack, stack1)) { return stack2; } else { return stack1; } } } public StacksQueue() { queueStack = stack1; } public void Queue(T item) { int count = 0; while (queueStack.Count > 0) { secondaryStack.Push(queueStack.Pop()); count++; } queueStack.Push(item); for (int i = 0; i < count; i++) { queueStack.Push(secondaryStack.Pop()); } if (dequeueStack == null) { dequeueStack = queueStack; } queueStack = secondaryStack; } public T Dequeue() { if (dequeueStack == null) { throw new InvalidOperationException("Trying to dequeue from queue which is empty"); } T result = dequeueStack.Pop(); if (object.ReferenceEquals(dequeueStack, stack1)) { dequeueStack = stack2; } else { dequeueStack = stack1; } if (dequeueStack.Count == 0) { dequeueStack = null; } return result; } } Hi, here is a smart solution in java based on shan.phreak solution : class Queue { Stack stack1 = new Stack(); Stack stack2 = new Stack(); public void push(Integer value){ while (!stack2.isEmpty()){ stack1.push(stack2.pop()); } stack1.push(value); } public Integer dequeue(){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } return stack2.pop(); } } |

Given an integer write a function that converts the input into a linkedList where each node corresponds to a number of the integer. Eg: 25697 == 2 -> 5 -> 6 -> 9 -> 7 Then write a function that takes 2 linkedList, add the corresponding integers and return a third list with the result. 3 AnswersThe is a blog discussing how to add two numbers in two lists, with the following link: http://codercareer.blogspot.com/2013/02/no-40-add-on-lists.html Hi Harry, I used your website a lot when I was studying for interviews. Certainly helped me get the internship. Thanks for your time! /* Jun Zheng, Rice Univ C++, Xcode 4.5.2 Interview question of GS Convert a number to linked list. Need reverse. */ node* numToLinkedList(int num){ if(abs(num)* p=new node(); p->next=numToLinkedList(num/10); p->data=num%10; return p; } //Reverse the list void reverse(node* &phead){ if(phead==NULL ||length(phead)==1) return; node* p1=phead->next; node* p2=NULL; phead->next=NULL; while(p1->next != NULL){ p2=p1->next; p1->next=phead; phead=p1; p1=p2; } p1->next=phead; phead=p1; } |

Code a function in C to get the largest consecutive addition of integer numbers fron an array. 3 Answers/* Haven't done C in a while, so pardon me. * Essentially, you have to use dynamic * programming (see Wikipedia entry on the * subject if you are unfamiliar). Create * a table where one dimension represents * where we start summing ints, and the * other dimension represents where we end * summing ints. Because not all table * entries will be valid, we'll only be * filling half of the table. */ #define MAX(a,b) ((a) > (b) ? (a) : (b)) int largest_sum(int array[]) { /* Create our memoization table */ int max_sum = INT_MIN, i, row, col; int array_size = sizeof(array) / sizeof(int); int **mem_table = (int**)malloc(array_size * sizeof(int*)); for (i = 0; i = column are * nonsensical and are ignored. */ for (row = 1; row < array_size; ++row) { for (col = row; col < array_size; ++col) { mem_table[row][col] = mem_table[row][col-1] + array[col]; max_sum = MAX(max_sum, mem_table[row][col]); } } return max_sum; } Blech, that's what I get for posting code without testing it first. Sorry about the double-post; wish I could edit my entry. int largest_sum(int *array, int array_size) { /* Create our memoization table */ int max_sum = INT_MIN, i, row, col; int **mem_table = (int**)malloc(array_size * sizeof(int*)); for (i = 0; i = column are * nonsensical and are ignored. */ for (row = 0; row < array_size - 1; ++row) { for (col = row + 1; col < array_size; ++col) { mem_table[row][col] = mem_table[row][col-1] + array[col]; max_sum = MAX(max_sum, mem_table[row][col]); } } return max_sum; } best = 0; current = 0; for (int i=1 to n) { current = MAX(current + array[i], array[i]) best = MAX(current, best) } return best; Complexity O(n), additional memory used O(1) Proof: MaxSuffixSum(empty) =0 MaxSuffixSum(a[1..n]) = MAX(MaxSuffixSum(a[1..n-1]) + a[n], a[n]) where MaxSuffixSum is a largest sum of numbers from some i to n. The largest consecutive sum is some suffix, so it is enought to calculate best suffixes ending at all indexes in the array and pick the best one. |

You are in a room by yourself and someone walks into the room, asks you to find the temperature, and leaves. How would you find the temperature in the room without leaving the room? 3 AnswersCall a friend to bring a thermometer over. Cut a 5cm*5cm*5cm ice cube from the refrigerator, and test how long it take for it to melt completely. Find two equal size ice cubes, for the first one, wait till it melts completely(0 ℃) , heat it till it boils, record the time t1. For the second one, wait long enough till the water has the same temperature with the room, than heat it till it boils, record the time t2. The room temperature is 100*t2/t1. |

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