Software Development Engineer Interview Questions | Glassdoor

# Software Development Engineer Interview Questions

3,615

Software development engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

Dec 17, 2009

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

Feb 21, 2010
 How could you represent days and month using 2 6 sided dice6 AnswersI don't anderstand the question. coul you elaborate please?google: calendar dice Dice 1: 0 1 2 3 4 5 Dice 2: 0 1 2 6 7 8 Combination of these two dices will show you 01 to 31 days of the month. Since he said "and month" in the question; you will have to use some creativity to show the month...How does: Dice 1: 0 1 2 3 4 5 Dice 2: 0 1 2 6 7 8 Represent 29?Show More ResponsesAlso, how do 0, 7, and 8 show up on a 6-sided die...?dice 1 label: 012678 dice 2 label: 123459The trick is to use the number 6 to represent 9. 6 upside down is 9. Otherwise it is impossible.

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

Jan 6, 2011
 Write a program to find the square root of a double.5 Answersuse binary search to narrow down the search space and keep multiplying the answer in each iteration by itself to check if it is equal to the double given. If it is lesser, move up the lower bound, else move down the upper bound.One easy to remember method that also has much better performance than binary searching for the result is the Babylonian Method. It is similar to Newton's method for finding derivatives. See the algorithm here: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method Also, combining this algorithm with the Rough Estimation also described on that page will compute the squareroot of most double numbers in less than 10 iterations.Is it too obvious to ask if you can do double^.5 ?Show More ResponsesI would respond by showing that I am thinking about the problem as it is defined, not by making assumtions about what is implied. This can result in product that does not meet the requirement specifications, which can be very costly: "What do you mean, a program or a function? A program would require input and output mechanisms to make it meaningful, but makes it pretty usesless as a job assessment question. A function makes more sense in this context. "There's a variation of the problem which says "find the square root of a double up to the third decimal digit". I'd just multiply the original number by 10^position (meaning, for 3 digit accuracy it'd be 10^3) and ran a simple loop to find the closest integer. As soon as i*i > 10^position * number, you can return (i-1)/10^position. It's hella slow and unimaginative, but it works and you won't sound like you knew this problem ahead of time (if you come up with a Babylonian solution).

Jan 6, 2011

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

Mar 20, 2009
 How would you implement a top 3 word count in a text editor application?7 AnswersWhat is the answer to this question? Would one just parse through the whole document and hash each word occurrence, with the key as the word itself, and the value as the number of occurrence?Can we use a BST to store word and length values? And then do a pre-order traversal?Another approach would be to sort in place in n log n. Then scan the sorted list of words and maintain a count of top three.Show More Responsesmax-HeapThis can be done using Linked Hash. Each element of Hash has two pointer. Min pointing to element which comes next in the seq with count. When we add new word, either it will be added to hash or updated its count. If count is updated then we need to correct the Min and Max pointer accordingly. Also we need to corecct obj.Min.Max pointer and obj.Max.Min pointer accordingly. Keep track of the Max and Min element of the heap elements. Other optimization can be done to improve the worst case scenario like storing head pointer of list of words which has same count.Using Heap and Hash will solve the problem optimally. Keep a hash of word as key and count as value. And keep a Min heap of 3 elements. Build the heap with first 3 elements. For every new element increase the count in HashMap. Check if the element is in the heap, then update the count and reheapify. Else check if the element count is greater than top element of Min heap, if yes then replace that element with our new element and reheapify. Else don''t touch our heap and keep counting. This will make sure the heap will always have top 3 elements. Complexity: O(n) as heapify is constant always.MaxHeap/priorityQueue whose key is the word itself and the priority is the word count. When you need the top three words, just pop the heap three times 3*O(logN).

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

Jan 21, 2010
 Given a set of N numbers, assume that you have the set of numbers from 1 to N+1, with the exception of one number. How do you determine what number that is? What is the complexity of your solution?5 AnswersTwo Step Process - 1) Sum of N Numbers Formula - (N*N+1)/2 [Complexity O(1)] 2) Iterate over the given N-1 numbers and calulate the sum [Complexity O(n)] Subtract result 1 - result 2; this gives the missing number!How about binary search on a sequence ???? This would take O(log n) to find ...Binary search on a sequence is O(log n), but you are assuming that you have been given an ordered set, which is not specified. The sort on the set will most likely be O(n log n).Show More Responsesbinary search in general meaning, not binary search on sorted listBinary search only works on a sorted list. It doesn't work anyways since you won't know what you are searching for. The correct answer is to iterate through the sorted list and look for the missing value, which takes n time.

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

Aug 17, 2011
 Implement a stack using two queues. 8 AnswersHave two stacks. Push only on to one stack. When popping, check if the second stack is empty. If it is, pop everything from the first stack and push into second stack. Then pop the stack and return the value. Else, just pop the stack and return the value.The question asks to implement a stack with 2 queues. Your solution has 2 stacks and is implementing a queue.it is pretty similar, on Queue check which queue is not empty and enqueue in that one, if both are empty pick one. On Deque, start dequeue from the queue that is not empty and queue the element to the other queue until you reach the last element.Show More ResponsesOne the blog below, there is a detailed solution about how to implement a queue with two stacks: http://codercareer.blogspot.com/2011/10/no-17-queue-implemented-with-two-stacks.html It is quite similar to simulate a stack with two queues.You only need 1 queue to implement a stack. queues are more powerful. If there are N elements in the queue and you need to pop the last element in order to simulate the stack LIFO behavior, just pop the first N-1 elements and immediately push them back into the queue. Then pop the Nth element and return it. Done. You are basically cycling through the queue to get the element you want without disrupting the rest of the elements. Note O(N) time for pop(). This is what valentino said above but you don't 2 queues, just 1, to accomplish it.totally Agree with bob, you only need one queue, I guess using the 2 queues answer is based on the question "2 queues" but once again this can be solve with just one queue.I think the answer the interview is looking for is something like this: You kept two queue's one of them is always empty. Push - Enqueue to the empty queue, and then sequentially dequeue everything on the other queue to this "empty" queue, complexity O(N) Pop - Dequeue the non-empty queue O(1) This solution is in favor of pop, it can be done in favor of push also.To add on to the previous answer, both can be done in O(1) if a special element (end-of-queue) is allowed to be introduced. Push - push to the queue that has the end-of-queue element as the first element. Pop - Dequeue both queue, one of them is end-of-queue element, so serve the result of the other queue.

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

Jan 25, 2011
 Write a function that takes in an array and repeats an integer that appears the most.5 Answersif: Array [2][2][3][3][3][2][1][2][1] it should print [3]Confusing. In your example, 2 appears the most. Do you mean the integer that repeats the most consecutively? Cause that would be 3. Anyways, in either case, you can go through the array adding all the key-value pairs (number and times) to a hashmap and then access the hashmap in constant time. O(n).class FindMostOccurences { public static DictionaryEntry MostOccurences(int[] Array) { Hashtable ht = new Hashtable(); for (int i = 0; i Int32.Parse(de.Value.ToString())) { { de.Key = item.Key; de.Value = item.Value; } } } return de; } }Show More ResponsesUsing map , i think one loop is sufficient. private static int mostReapeatingNumber(int[] is) { HashMap map = new HashMap(); int tempHighestCount = 0; int keyHighest = 0; for (int index=0; index tempHighestCount) { tempHighestCount = numCount; keyHighest = number; } } } return keyHighest; }I think there's no need to have a map. Just maintain variables prev_max_run, prev_max_num, prev_num, curr_num and curr_run. In the loop if the prev_num was equal to curr_num increment curr_run. When you find the num is different check curr_run with prev_run. If curr_run > prev_run, prev_max_num = curr_num.

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

Mar 31, 2012
 Given two binary trees T1 and T2. Find if T2 is a sub-tree of T1.6 AnswersThis is what I would do (pseudo code): bool isSubtree(BinaryTree* T1, BinaryTree* T2) { if(T1 == T2) { return true; } if (!T1.hasChildren()) { return false; } return isSubtree(T1.left, T2) || isSubtree(T1.right, T2); }int isSubTree(struct node *T1, struct node *T2){ if(T2 == NULL) return 1; // NULL tree is subtree of any tree else if(T1 == NULL) return 0; // if T2 is not NULL and T1 is NULL else if(T1 == T2) return 1; // if T1 and T2 both equal and not equal to NULL else return isSubTree(T1->left, T2) || isSubTree(T1->right, T2); }For either of these solutions, the recursion will blow up exponentially. You'll need to either find a solution which only recursively calls itself once or an iterative algorithm. Also, if the binary tree includes a pointer to the parent, then the fastest will be to start from T2 and search parents.Show More ResponsesThe first solution lacks T1==null checking. rkt's solution is perfect. The comments by the 'Anonymous April 8 2012' and the negative sign for the first answer is definitely posted by some ridiculous guy who is even confused with tree traversal. "the recursion will blow up exponentially" I have to say this is the best piece of his answer. Also the 2nd comment from this guys seems useful, but how many times you have encountered that we are given parent pointer? I beg this guy to take more CS class and do programming exercises before showing off his stupidityHere what we are essentially doing is comparing the pointer values - is that what is expected? Or is it that return true if T2 is a subtree of T1 according to its values? Which means that if T2 has completely different pointers, but still has the same values as some subtree of T1, then we should return true, else false.@Saranya: No we're looking at the node values. Otherwise it would be far too simple (since if the object is the same at the first level, it garantees that children are too, and so one...)

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

Jan 27, 2012
 First explain what a tree, then binary tree, then a binary search tree is. Now implement a function that verifies whether a binary tree is a valid binary search tree.5 AnswersSadly I ran out of time for this question. But I e-mailed the response after my time was up. First create a small implementation of a binary tree, I did it in java with the standard implementation Nodes with left and right children as data points. Check whether the left child and right child have valid values, which is to say make sure all children on the right of a node have values greater than parents that they came from. The key thing that I missed during the interview was the fact that if you traverse once to the right, then once to the left, you have to make sure the value is between the max and min that you've encountered up to that point.int validate_BST(struct tnode *tree){ int ret1, ret2; if (tree == NULL) return 1; else { if (tree->left != NULL){ if (tree->data > tree-left->data){ ret1 = validate_BSR(tree->left); } else return 0; } if (tree->right != NULL) { if (tree->data right->data){ ret2 = vaidate_BSD(tree->right); } else return 0; } return (ret1 == 1 && ret2 == 1)? 1: 0; } return 0; }To find whether a binary tree is valid Binary search tree, do inorder traversal and check if the nodes are sorted.Show More Responsesprivate boolean isBST(){ return isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isBST(Node node, int min, int max){ if(node == null) return true; if(node.data max) return false; else return (isBST(node.left, min, node.data) && isBST(node.right, node.data+1, max)); }In order to verify the Binary Search Tree, Read the nodes in Inorder mode. Also at every step check if the current node value is less than the one previously found then exit the traversal as the items are not sorted.
3140 of 3,615 Interview Questions