# Software development engineer in test Interview Questions

# 4K

Software Development Engineer In Test interview questions shared by candidates### how would you move mount fuji?

27 Answers↳

I would first answer with, "First, I would analyze the problem and determine if it didn't make better sense to come to the mountain rather than move the mountain. Assuming that's not feasible..." I think that's a key element they're looking for in an answer. That you can look at a major task and first identify if there isn't a better approach. The next element is to determine how you would go about completing a seemingly impossible or gargantuan task. The specifics of this part of the answer don't matter other than to show that you have an understanding that huge problems need to be broken down into smaller, more manageable tasks using the resources you have. Less

↳

When they ask a quesion like this at MS, they do want an answer. If you tell them that you want to consider alternatives up front, they will wave that off and tell you that, in this hypothetical situation, alternatives were already considered and that moving the mountain is the approach was chosen. They really want you to answer the question. The point of this question is - process. They want to see what process you use to solve problems. It is important to show that you solve the problem not by arranging and re-arranging a series of random thoughts but that you can approach it methodically and that this methodology can be applied to any problem. Do not to to some up with a clever answer that attempts to solve the problem - they will just keep insisting that you tackle the problem. If you don't, you won't pass the interview. So, brush up on your problem solving process before you interview at MS. Use these questions as an opportunity to impress them with how well you can solve difficult problems. Less

↳

This is a common dorky Computer Science joke. The answer I believe they are looking for is that you use the Tower of Hanoi algorithm to move the mountain (i.e. that the problem of moving Mt. Fuji is reducible to the already-solved Tower of Hanoi problem). This could be accomplished by having a large laser and a couple of really good cranes. Less

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

16 Answers↳

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

↳

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 Less

↳

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"; } Less

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

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); } Less

↳

//correction temp = node2; while( temp.parent ! = null) { temp = temp.parent; counter2++; } Less

↳

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 } Less

### I was asked a pretty straight forward brain teaser during my last phone interview, which they said they don't normally do, but because I put that I was a logical problem solver on my resume they couldn't resist the opportunity to. It was the following "There are 20 different socks of two types in a drawer in a completely dark room. What is the minimum number of socks you should grab to ensure you have a matching pair?"

13 Answers↳

All of the previous answers are somehow wrong or misleading. "Not-a-mathematician": the method you describe would ensure that you get 2 DIFFERENT socks instead of matching - and only in the situation that the ratio is exactly 50-50. "Anonymous on Oct 20 2012": No, you could also have 3 of the same sock after grabbing 3. "Anonymous on Oct 3": The probability has little to do here, while it is over 0%. THE REAL ANSWER: Given that there are 2 types, and you want to get a MATCHING PAIR (not 2 different socks) you must grab 3. When you have 3, you WILL have at least 2 of the same kind, since there are only 2 kinds available. Less

↳

1 black : 19 white. .. 3 socks 2 black : 18 white ... 3 socks 3 black : 18 white ... 3 socks 4 black : 16 white.. . 3 socks 5 black : 15 white .. . 3 socks 6 black : 14 white ... 3 socks . .. . .3 socks. why? The worst case scenario is always 2 of one color and one of the other. Less

↳

I'm not a mathematician, statistician or highly analytical but if you pick up 3 socks they could still be all the same type - even if the odds are 50%. Odds do not equal reality. So the only way to "ensure you have a matching pair"is to pick up 11 of the 20. This is the only fool proof guaranteed way to get a pair (in the real world and not the world of odds). Less

### Describe and code an algorithm that returns the first duplicate character in a string?

11 Answers↳

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

↳

for (int i=0;i

↳

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

### The Game of Nim worded diffently.

11 Answers↳

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

↳

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

↳

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

### Given a list of n numbers. All numbers except one are unique. Find the number with duplicate entry.

10 Answers↳

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

↳

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 Less

↳

^^ 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 Less

### Data structures and Algorithms related

2 Answers↳

plz tell me which type of question put up in interview

↳

Iam ready

### Find from alist of numbers where each number is repeating even number of times except one. Find that number ?

9 Answers↳

xor all the elements in the list. The value remaining is the only one that's not repeated an even number of times Less

↳

[x for x in set(a) if a.count(x)%2!=0]

↳

for (int n=0; n

### +-----------+ | 1 | 2 | 3 | +-----------+ | 4 | 5 | 6 | +-----------+ | 7 | 8 | 9 | +-----------+ | * | 0 | # | +-----------+ +---+ | U | +---+ +---+ +---+ +---+ | L | | S | | R | +---+ +---+ +---+ +---+ | D | +—+ Input String: "180*", output is the number of minimum operations needed to dial the input */ 2)How do you test login page?

9 Answers↳

it is positioned like key on keypad 123 456 789 *0# it is up to the solver to determine which data structure to use, L (left) R (right) U (up) D (down) S (select) are the operation Input String: "180*", output is the number of minimum operations needed to dial the input * Less

↳

9 operations: Assume cursor is always at 1 . S means Select , R Means Right , L means Left , D Means Down S-R-D-D-S-D-S-L-S Less

↳

8 Operations public class phoneline { public static void main(String[] args) { int a = 0; int b = 0; String[][] nums = new String[4][3]; for (int x = 0; x < nums.length; x++) { for (int y = 0; y < nums[x].length; y++) { if (a < 9) { nums[x][y] = String.valueOf( ++a ); } else if (a == 9) { nums[x][y] = "*"; a++; } else if (a == 10) { nums[x][y] = "0"; a++; } else { nums[x][y] = "#"; } } } System.out.println( Arrays.deepToString( nums ) ); ways(nums); } public static void ways(String [][] nums) { String str = ""; int counter=0; for (int x = 0; x < nums.length; x++) { for (int y = 0; y < nums[x].length; y++) { counter ++; if (nums[x][y] .equals( "1" )) { str = str +"" + nums[x][y] + "S" + "D" + "D" + "R"; //System.out.println(str); // x = 1; // y = 0; break; } else if (nums[x][y].equals( "8" ) ) { str = str +"" + nums[x][y] + "S" + "D"; // x = 2; // y = ; break; } else if (nums[x][y] .equals( "0")) { str = str + "" + nums[x][y] + "S"; x = nums.length; break; } else continue; } } System.out.println(str); System.out.println(counter); }} Less