# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

Using only putchar how would you print out the ascii values for each digit in an integer. For example if the integer was 123, then you would want to print the ascii values for 1, 2, and 3. 5 AnswersI used a recursive method involving modulus and division by 10. Not hard, just stressful writing it on paper in an interview. void printAscii( char *input) { while(input) { putchar(*input++); } } This should work as well....printing each char as an integer would give its ascii value Ah...the above code would just print the numbers itself not ascii values Could be fixed by adding ascii value of 0 char ie. putchar(*input + '0'); input++; Show More Responses void printASCII(int src) if (src > 9) { printASCII(src/10); } putchar('0' + (src % 10)); } void print_ascii(int n) { while(n) { int k = (n%10)+'0'; n/=10; putchar(k); printf("\n"); } } |

Write an algorithm to verify if a tree is a binary search tree. 5 AnswersBST(Node * p) { if (p==null) return false; if(p->left! null& p->dataleft) return false if(p->right&&p->data>=max(p->right)) return false if(!BST(p->left) && BST(p->right)) return true return false; } This solution is wrong. if (p==null) return false; - Why is this false? isBST(node n) if(n.left == null || n.right == null) return true; if(n.left.val < n.right.val) return isBST(n.left) && isBST(n.right) else return false; Show More Responses This solution is also false. It's going to return true if there is no right node and the left node is greater than the parent. It's basically right, and is a simple fix to change that, so I'll leave it to the reader as an exercise. :) Assume that we have a binary search tree like this: RootNode has value 6. RootNode->LeftChild has value 3. RootNode->LeftChild->LeftChild has value 2. RootNode->LeftChild->RightChild has value 7. We know that in a binary tree 1.all nodes' values which are at left side of a node must be less than Node's value. 2.all nodes' values which are at right side of a node must be greater than Node's value. In anonymous algorithm it does not check: 1. if node's left child's value is less than node's value && node's right child's value is greater than node's value 2. node's all left childrens' values must be less than node's value. |

Write a program that sees if two binary trees are equal. 6 AnswersI utilized a depth-first traversal method, comparing the data within each node and recursively checking the left, then right child. Don't know if this works or not... value = $value; $this->left = $left; $this->right = $right; } // O(n) times inorder traversal function testEsqual($tree1,$tree2) { if($tree1->value ==null || $tree2->value==null) return false; if($tree1->value ==null && $tree2->value==null) return true; while($tree1->value!=null) { if($tree1->value == $tree2->value) { equal($tree1->left,$tree2->left); equal($tree1->right,$tree2->right); } else { return false; } } } } ?> How if we use in-order traversal? If my understanding is correct, two binary trees are equal if they contain the same elements (although at different positions in the tree) Show More Responses bool AreEqual(Node* node1, Node* node2) { if( (node1 == NULL && node2 != NULL) || (node2 == NULL && node1 != NULL ) return false; if(node1 == NULL && node2 == NULL) return true; if(node1->data != node2->data) return false; return( AreEqual(node1->left, node2->left) && AreEqual( node1->right, node2->right) }; int main(); { AreEqual(root1, root); }; The solution by kvr doesn't cover a case when node1->data and node2->data are equal. An additional if is required. fb, If if(node1->data != node2->data) is not true, what does that tell you *Is* true? |

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

Given an array, return the nth largest. 4 AnswersCan be in any language. I did write the working code, but the interviewer pointed out that it won't work for some special cases. public static void sortArray(int n){ Integer[] arrayList = {12,2,5,1,7,8,3,4,9,10,13,11,6}; Arrays.sort(arrayList); System.out.println("for number : " + (n + 1) + " we get: " + arrayList[n]); } No sorting...it would take nlgn for sorting and it could be faster.. Show More Responses http://en.wikipedia.org/wiki/Selection_algorithm |

Given two (huge) sets, what is an efficient way to find their intersection? 4 Answershey can you please share the answer with us? I have 2 ans: 1. sort both the sets and iterate to find intersections. (nlogn) 2. use hash. (n) Please let me know if it could be done in a better way. Thanks! I think "huge" is an indication that using a hash set approach would be untenable, the idea being that you'd run out of RAM. The n log n approach seems correct to me. Dont u think nlogn is larger than n since in data structures, the base of the log is always 2 Show More Responses he meant untenable in space. in time of course you cannot beat the hash |

How would you find a duplicate number in a very large unsorted array of ints. 4 AnswersfindDuplicates(int array[]) { int duplicates[] , index; for (int i=0; ii; j--) { if (array[i] == array[j]) { duplicates[index++] = array[i]; break; } } print duplicates; O(n^2) is the usual naive answer but there are properties that if true can reduce this to O(n) using bit ops: In general, if the given array range can also be generated where the duplicated number you are trying to find gets no special treatment and is included just like all the rest a single time, then you can get the answer this way: set total to 0 foreach (n in given array) xor all n into total foreach (n in generated range) xor all n into total total is your answer This works because all the non-duplicated single entries will cancel out via xor with their single entry from the generated set (since they are all paired) and the duplicated number will have an extra odd entry (since it will have 2 entries already from the given array + 1 from the generated set = 3 entries). And because of course xor is commutative; the order of the xor'ing doesn't matter: 6^6^5^5^4^4 = 0, as does 6^5^4^5^4^6 It is a variation of these problems: - find a missing number in an unsorted array - find an unduplicated number in an unsorted array of duplicates I should have added t the above: Ask the interviewer if the array of N has any special distribution. In particular, for the duplicate question here, ask if the array of N contains [0, N-2] or [1, N-1] values unsorted, in addition to one extra entry duplicated in that set duplicated. Show More Responses [Apologies for multiple posts, I don't see any way to edit a post once made ...] There is also a way to find 2 different numbers instead of just 1 resulting from any of the above variations. If you first do the above xor O(n), your answer is actually A^B since you cannot separate the 2 numbers ... yet. The trick here is to get A and B into different unsorted subarrays, with all the other pairings that self-cancel into either subarray with them (but still in pairs together). That is done by noticing that even though you have no idea what A and B are individually, you do know that since the total is A^B that any 1-bit in the total A^B means that bit is different between A and B. So divide up *all* the numbers based on each having a 0 or 1 in one of those different bits. pseudocode -get the A^B total via the xor O(n) algorithm previously posted -determine as pivot an Nth bit which is different between A and B (any 1-bit in the A^B total) -run through all the same numbers again, but this pass accumulate xor's into an even or odd total depending on the chosen bit - the final answer for A and B will be the 2 accumulated totals Complexity: 2 O(n) which is just O(n) |

Find the longest subsequence in a given array of numbers in O(n) 4 Answers//Given an array of numbers find the longest subsequence //Using hash_maps :: complexity O(n) #include #include #include #include #include #include using namespace __gnu_cxx; using namespace std; void itoa(int i,string *s){ std::stringstream out; out , eqstr> myHash; int main() { myHash array; int inputArr[20] = {1,43,4,5,6,17,12,163,15,16,7,18,19,20,122,124,125,126,128,100}; int seqSize = 0; vector longSeq; vector tempLongSeq; for(int i=0;ifirst);seqSize=1; ++it; int data; //Iterate through each element and check if it is the next in sequence for (; it != array.end(); ++it) { data = it->first; if(data==(tempLongSeq[tempLongSeq.size()-1]+1)){ tempLongSeq.push_back(data); seqSize++; }else{ //sequence ended if(seqSize>longSeq.size()){ //if the current sequence is longest then store it else longSeq.clear(); longSeq = tempLongSeq; } tempLongSeq.clear(); tempLongSeq.push_back(data); seqSize=1; } } cout< Hey guys... the above code needs changes. if values are greater than 193 than it should fail because of hash_map's bucket_count.. anyways.. use map instead of hash_map. which is sorted. but this gives a complexity of O(nlogn) How about: Traverse the array, have an initial index of start of sequence, and update the end index each time the next element is in sequence. If the sequence ends, check the difference between start/end, and if it is greatest so far than save those two indices and length of sequence. Show More Responses Question - Should only the successive sequence of numbers be taken into account or sequence of numbers formed from the numbers in any position? |

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?" 9 Answers3 is the answer when the probability is 50% for either color. "20 DIFFERENT socks of two type" In my opinion It's a brain teaser not a probability question. The answer is none. There is no sock alike, so you can't get a pair. 3 is the answer no matter what... there are only 2 types, if you grab 3, you must have 1 of one type and 2 of the other Show More Responses 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). 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. Easy. I do this every morning when I get up. The answer is ONE PAIR. If you are like most people and have rolled the socks together in pairs when you put them away, there is no guessing and you just grab a pair of socks. I think it's more of a question about habits and prep. ;) It says "ensure" you have a pair. So all the probability answers are dead wrong. The person who said "The answer is none. There is no sock alike, so you can't get a pair" is probably correct. However if the question is to get two of the same type (of which there are two), then the only correct answer is 11. That is the MINIMUM number to ENSURE you have a pair--all probability aside. It says "ensure" you have a pair. So all the probability answers are dead wrong. The person who said "The answer is none. There is no sock alike, so you can't get a pair" is probably correct. However if the question is to get two of the same type (of which there are two), then the only correct answer is 11. That is the MINIMUM number to ENSURE you have a pair--all probability aside. It doesn't tell you that there are 10 and 10. There could be 19 and 1. But regardless: There IS a way to grab 2 socks and not have 2 that match. (one of each) But there is NO WAY to grab three socks and not have 2 of them match. |

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

Print all permutations of a given string. 4 Answers# include # include /* Function to swap values at two pointers */ void swap (char *x, char *y) { char temp; temp = *x; *x = *y; *y = temp; } /* Function to print permutations of string This function takes three parameters: 1. String 2. Starting index of the string 3. Ending index of the string. */ void permute(char *a, int i, int n) { int j; if (i == n) printf("%s\n", a); else { for (j = i; j <= n; j++) { swap((a+i), (a+j)); permute(a, i+1, n); swap((a+i), (a+j)); //backtrack } } } /* Driver program to test above functions */ int main() { char a[] = "ABC"; permute(a, 0, 2); getchar(); return 0; } a string of N characaters will have following number of string combination Np1 + Np2 + Np2+...NpN Using recursion we can solve this. I am giving the pesudo code with a small example. let the string be "abc". I am showing the recursive call within the bracket itself. Just to understand. Don't confuse that this is a code inside permute function. permute(abc) { ----level 1----- letter saved at this level is = a; all combination List obtained at this level = permute(bc); after the call returns put the saved letter {a} at each position in each entry and do the same for all entry in the list List obtained here is only bc and cb; that means put a every position of the return bc and cb ----> for bc {abc,back,bcd} and for cb {cab,cab,cba} return all the entries. At the highest level you will get all the permutation of the string. --------------level 2----------- letter saved = b ; all combination List obtained at this level = permute(c); after the call returns put the saved letter at each position in each entry and do the same for all entry in the list List obtained here is only c; that means put b every position of the return c --> bc{putting b before c} and cb{putting b after c} return bc and cb. --------------level 3----------- letter saved = c ; all combination List obtained at this level = 1; //Here it only c is returned Last letter is returned as this is only 1 combination exist -- base condition of recursion. } Show More Responses C# code. I'm a tester, so my code is a bit rusty, but the algorithm works. public static void Permutations(string orgStr) { List permutations = new List(); _perm(orgStr.ToCharArray(), String.Empty, ref permutations); foreach (string str in permutations) { Console.WriteLine(str); } } private static void _perm(char[] sample, string filled, ref List permutations) { if (sample.Length == 1) { string perm = String.Format("{0}{1}", filled, new string(sample)); permutations.Add(perm); } else { for (int i = 0; i i) { newSample[j-1] = sample[j]; } else { newSample[j] = sample[j]; } } _perm(newSample, newFilled, ref permutations); } } } |

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

I got questions like "Given a dictionary of words, how do you calculate the anagrams for a new word". 4 AnswersOne answer was to precalculate a 26 element array for each dictionary word where an array element represented how many occurences of the corresponding letter of the alphabet occured in that word. You wouldn't. A new word would not appear in the dictionary. One way to do this would be to take each word in a dictionary and sort it and store it as a key in a hash. the values will be all the words that map to this one, stored as a list. Show More Responses Store all anagrams for the new word in a 2-dimensional array (column 1 = anagram, column 2 = flag). Compare each element in column 1 with words in the dictionary until found. If found, flag = good anagram, else flag = bad anagram! Just a guess. Suggestions please. |

**41**–

**50**of

**4,121**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Software Developer
- Senior Software Engineer
- Software Development Engineer II
- Software Development Engineer I
- Intern
- Software Engineer Intern
- Senior Software Development Engineer
- Software Development Engineer In Test
- Software Engineering
- Data Scientist
- Java Developer
- Senior Software Developer
- Program Manager
- Analyst
- Product Manager
- Associate Software Engineer
- Engineer