# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

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

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? 6 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 Responses binary search in general meaning, not binary search on sorted list Binary 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. Load initial set into a hashmap, check the n+1 set against data in hashmap..if not in hashmap, that’s our missing number |

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

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 Responses I assume the point is scalability. You may do this useing sharding technique in order to split table records on multiple nodes Why not try min heap |

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 Responses One 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. |

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 Responses Using 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. |

How could you represent days and month using 2 6 sided dice 6 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 Responses Also, how do 0, 7, and 8 show up on a 6-sided die...? dice 1 label: 012678 dice 2 label: 123459 The trick is to use the number 6 to represent 9. 6 upside down is 9. Otherwise it is impossible. |

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^2 Show More Responses I 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. |

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 Responses The 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 stupidity Here 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...) |

Assume that you are given the head and tail pointers of a doubly linked list where each node can also have a single child pointer to another similar doubly linked list. There are no cycles in this structure outside of the traditional double links. Write a procedure in C++ that flattens this structure into a single list. 7 AnswersI found out later that this problem is one of several classic programming questions taken from an interview book. Such a list has an obvious recursive structure, but it is large and so recursion is not practical. Consequently, an iterative approach is necessary. The invariant for such an approach maintains the flat list to the "left" and the possibly fat list to the "right." Do you know the name of the book? I don't know the particular book it was taken from. However, a colleague recommends the book: _Programming Interviews Exposed_ by John Mongan The second edition is available, but a third edition (with two additional authors) is on its way and available for pre-order on Amazon. There are several other similar books. For example, _Cracking the Coding Interview: 150 Programming Questions and Solutions_ by Gayle Laakmann McDowell _Programming Pearls_ by Jon Bently _Puzzles for Programmers and Pros_ by Dennis Shasha _How Would You Move Mount Fuji?: Microsoft's Cult of the Puzzle -- How the World's Smartest Companies Select the Most Creative Thinkers_ by William Poundstone and many others you can probably find by looking at Amazon's recommendations when viewing the descriptions of those books. Show More Responses Didn't get any notification that you had replied to this, and just found it again when reviewing my studies. Thanks! Glad to help! And many of those coding-specific books include lots of questions about operations on linked lists. I have a feeling that the questions asked to me probably come from that set of books (or a book that shares a source with one of those). There might be some variation, but the basic principles should be the same. PseudoCode Solution: class ListNode(prev, next, sub_list) def flatten_list(node): if node == None: return [] elif is_tailI(node): return [node.value] + flatten_list(node.sub_list) else: return [node.value] + flatten_list(node.sub_list) + flatten_list(node.next) The PseudoCode solution mentioned above is *NOT* the desired answer because it involves recursion. As mentioned in the first comment, recursion is not allowed due to the very large structure of this list. The correct solution makes use of loop invariants. |

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 Responses With 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? |

Find the 20 longest strings in a text file. 6 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 Responses The 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. Use selection rank algorithm. Expected time complexity o(n) |

**31**–

**40**of

**4,130**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