# 18K

Software Development Engineer interview questions shared by candidates

## Top Interview Questions

Sort: Relevance|Popular|Date
Software Development Engineer In Test (SDET) was asked...April 18, 2012

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

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&lt; strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } Less

public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index &lt; 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

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

### In a given sorted array of integers remove all the duplicates.

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

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 &lt;= 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; } Less

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

### Write a method to decide if the given binary tree is a binary search tree or not.

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

public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER) { if (root == null) // children of leaf nodes { return true; } return root.data &gt;= INTERGER_MIN &amp;&amp; root.data &lt;= INTEGER_MAX &amp;&amp; isValidBST(root.left, INTEGER_MIN, root.data) &amp;&amp; isValidBST(root.right, root.data, INTEGER_MAX) } Less

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 Less

### how can a particular application be tested apart from testing its functionality

Also include, performance, stress &amp; load testing

Accessibility, user experience, globalization, localization, integration, compatibility Less

Reliability Test, Stability Test, UI Test, Platform Test,

### Given a string (understood to be a sentence), reverse the order of the words. "Hello world" becomes "world Hello"

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

class Solution { public static void main(String[] args) { String input = "Hello World this is a string"; reversestring(input); } public static void reversestring(String input){ // Stack stack = new Stack(); String[] str = input.split(" "); for(int i = str.length-1;i&gt;=0;i--) { System.out.print(" "+str[i]); } } } Less

### Write code in your favorite programming language that will accept two strings and return true if they are anagrams.

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

This 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! Less

### Given a string "aaabbbcc", compress it, = "a3b3c2" . Given that output string's length is always smaller than input string, you have do it inplace. No extra space

#include #include #include #define STR_SIZE 26 int main() { /* Current char sequence tracker */ char *c = NULL; char *b = NULL; char *str = (char*)malloc(STR_SIZE * sizeof(char)); if(NULL == str) return -1; memcpy(str, "aaaabbbcceeeeefffffff", 26); b = c = str; printf("Input: %s\n", b); while(*str) { if(*(str+1) != *str) // Repeat sequence ends { // Add 48 so the count gets printed as a char *(c+1) = ((str-c+1)+48); // Updated count, copy rest of the string starting after the count position memcpy(c+2, str+1, strlen(str)); // Update c to point to the new char repeat sequence c = c+2; } str++; } /* b was initialized to point to str up top, proving it was done in place */ printf("Output:%s\n", b); free(b); b = NULL; return 0; } Less

Rohan: What if I give you the string "aaaaaaaaaa"? Your solution will print "a:", not "a10". Less

What about the input "abc"? I assume that should compress to "a1b1c1" which is NOT shorter than the input, so you cannot compress in place. Less

### how would you move mount fuji?

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

### non disclosure agreement

I don't actually know. I mean, that's what I would do if I were amazon, but I did not read anything about them webcamming me, and I also didn't happen to notice the webcam light being on. That didn't mean it didn't happen, though. Less

I took the test in c++. The function interfaces were in base c, though, so it would probably look more or less identical in c or java. Less

Hi, I just finished my second assessment test for Amazon and passed all their tests for the 2 coding questions. Was the second test really the final round? There isn't a final third round? Thanks! Less