Software Development Engineer Interview Questions | Glassdoor

# Software Development Engineer Interview Questions

3,575

Software development engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Aug 20, 2012
 Find the 20 longest strings in a text file.5 AnswersIf you don't have to worry about space, you could use a hash with each word being the "key" and its length being the "value". Then sort bu hash by value, and choose the top 20.Another way can be to just traverse the strings and keep a min b-tree to keep the minimum element on the top. When size of tree + 20, then only insert (replace) in tree, if the current string length > root of tree(min) . This will take O(log20) for each insertion and O(N) for traversal.In the hash map approach described in the first answer, instead of having the word as the key, we can have the length as the key and value as the list of words with the length pointed by the key. You can use LinkedHashSet if you want sorting. Or you can maintain the largest 20 lengths in a separate data structure. This obviously is not a really optimal solution in terms of space complexity. Instead of that we can maintain a min-heap. Add first 20 words as it is. And then, if the new word has a larger length than the word at the top of the heap (smallest word as it's a min-heap) you remove the word from the heap and insert the new word into the heap. The heap size is always going to be 20 so you don't take much space and don't take much time to insert the word in the heap as well.Show More ResponsesThe min-heap solutions looks nice..However, it would take O(n.logn) right? On worst case, we do have to insert/delete in min-heap (log n) for every n words. Any better solution exists?? Can we use dynamic programming to find the longest word and then remove the longest word and repeat the routine for 19 more times? That would be 20times O(N) , which is better than O(n.log n). Any comments?Correction: The min-heap version takes n.log(k) only which is O(n) only. -This looks the best solution so far.

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

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

Nov 22, 2011
 Find k largest/smallest number in a series of numbers. What data-structures will you use? Code it on white board.5 AnswersFor K smallest number in series you can use a max heap of size k. When you find a new number and it is smaller than root of heap, swap it with root and heapify.@Ajit: What're the initial values of the max heap? What happens to the first value that comes in?Use selection sort for 'max' ( or for 'min') If K > series.length/2 then reverse the criteria- like in stead of looking for 15th highest out of 20 element array - look for (20 -15 =) 5th lowest and so on....Show More ResponsesI think there's a cool solution which involves doing a pivot operation (like quicksort) until you have the top/bottom k numbers sorted. It's possible that you can get the top k numbers in a single pass of the array if you happen to choose a good pivot, and in general takes very few passes to find the top k numbers. I coded it up in C a while back: http://privatepaste.com/1f1df9d8f0 You just call select with your list, the min index, max index, and top k numbers, respectively. It can be easily changed to find the min (just reverse the swap condition)@Jordan, I can no longer get at your privatepaste link, so if you see this post I am interested in answers to the following: - since partition sizes are inherently not controllable by your choice of pivot, how do you land on an exactly k-sized partition (or even a k-sized total of the leftmost/rightmost N partitions)? - how do you choose pivots reliably to perform this (if it isn't reliable, then it isn't always a good answer just like pathological inputs for quicksort without randomizing the pivot selecting) - do you still just sort the partition(s) once you reach a k-sized set? I assume they want them in-order. I would just use a heapsort that short-circuits once K elements have been popped from the internal sifting loop, which does minimal processing and returns them in-order (C# example): public void FindKLargest(T[] A, int k) { . Heapify(A); . int end = A.Length - 1; . int k_offset = Math.Max(Math.Min(k, end), 1); . int stop = end - k_offset; . while (end > stop) . { . // Save the root heap item as done . Swap(ref A[0], ref A[end]); . // Separate heap from saved item . end--; . // Re-sift the new root item . SiftDown(A, 0, end); . } . // the K largest entries are now in ascending order at the end of A }

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

Jan 30, 2012
 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 Responsesbool 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...

Dec 5, 2011
 Given two very large binary trees T1, with millions of nodes, and T2, with hun- dreds of nodes, create an algorithm to decide if T2 is a subtree of T1.6 AnswersPerhaps I'm missing something here but I think this could be a trivial problem. You could simply do a binary search on T1 all the while looking for the root node of T2. If you find it, then T2 is a sub-tree of T1. As binary search is O(log n) this would be quite efficient too.Ja, you got the first part right, but the second part would be to verify that T2 is exactly the same as T1 -- so time would be O(log n + m) where m is the number of nodes in T2What Ja means is that you do not compare the node values, but the nodes themselves. In fact, the question needs to be refined, are we looking for identical trees (node values and the tree structures) or just references (addresses)?Show More ResponsesThis is a very hard problem. Look up subtree matching and you'll see what this is about.The first couple of posters seem to be confusing binary trees with BST.The first posters are indeed wrong. Binary trees are in no particular order (unlike binary SEARCH trees).

May 9, 2011

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

Sep 1, 2011
 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 valueAh...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 Responsesvoid 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"); } }

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

Sep 13, 2010
 Design a system for counting how many times an item is clicked on. You need to record clicks and be able to report how many clicks for a given item. Be able to report which items are the most popular. Keep in mind scalability, since this is Amazon we're talking about.5 AnswersHave a hashmap that takes name of the item as keyvalue and the stored data contains number of clicks. which is incremented every time. Initially a deque of size 'k' stores number of clicks for 'k' popular items i.e. the deque is sorted. Everytime we increment the number of clicks for an item we check the min/max values for the deque i.e. begin and end values if the value lies in between then we found a new popular item. We insert into the deque by traversing the deque. finding a location in the deque is log2(k) {k popular items}. we pop the one in the end.Uhm... how is that going to work when you've got a whole farm of servers trying to count clicks for those items?I'd rather using BST or STL map because you need to sort each item in less time.Show More ResponsesI assume the point is scalability. You may do this useing sharding technique in order to split table records on multiple nodesWhy not try min heap

### 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 at Microsoft was asked...

Jan 4, 2010
 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 ResponsesThis 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.
4150 of 3,575 Interview Questions