# 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 binary tree with the usual left and right pointers on each node, and additionally a parent pointer, make an algorithm to discover the closest ancestor to 2 nodes on the tree. 7 AnswersTime complexity is : O(max height of binary tree) public void findCommonAncestor(Node current,int a,int b){ if(current.getKey() a && current.getKey()>b){ findCommonAncestor(current.getLeft(), a, b); }else{ System.out.println(" least common ancestor is "+current.getKey()); } } analog76, your solution is not complete. @clusterfudge, what do you mean by incomplete? Can you be more precise?. Common ancestor - first encounter of node value between a and b. Otherwise either you go left or right node. Show More Responses As far as I concern it is a binary tree not binary SEARCH tree. thanks @naipton. 1) Find matching node for the first value in the tree. If the node found create a set contains all its parents till the root. 2) Use postorder traversal for recording all the ancestor. 3) P1 is parent, P2 is grand parent and P3 is ggparent and continue till root. V1={P1,P2,P3,P4,....root} 4) Similary find all the parent of second value V2={P1,P2,P3,.root}. 5) traverse both set and first matching element in both sets is lowest common ancestor. Find height of node 1 as h1 and height of node 2 as h2 by travelling to the root. Time O(2 lg N). If h1 > h2, then move node1 by h1 - h2 and vice versa. THen, use two pointers to move one parent at a time until parent nodes are same. Complexity - O( 3 lg N) Assuming each node has a unique ID (its memory address, for example), you can solve this in O( 2 lg N ) where N is the number of nodes in the tree. findCommonAncestor(Node x, Node y): 1. Initialize a hashmap, call it `parentsMap`. 2. Starting from x, visit all its parents up to and including the tree root, and for each parent `p`, set parentsMap[p.id] = true 3. Starting from y, begin to visit its parents and for each parent `p`, check parentsMap[p.id]. If true, return p.id. Else, continue visiting parents until `p` is null, at which point we return null. |

You are given an array with n positive integers where all values in the array are repeated except for one. Return the one that is not repeated. 7 Answerspublic static int notRepeated(int[] given) { Map m = new HashMap(); for(i=0; i < given.length; i++) { if(m.get(given[i])) { m.put(given[i], 2); } else m.put(given[i], 1); for(x:m) { if(x == 1) return x; } } } If you have an array of positive integers with only ONE non repeated integer, the easiest thing is just xor them all. Whatever you return will be the answer. Perl answer below sub findNotRepeated{ my ($arr) = @_; if(@$arr==0) { return - 1; } my $val = 0; foreach(@$arr) { $val ^= $_; } return($val); } sub findMissingElement{ my ($arr,$arr2) = @_; if(@$arr==0 || @$arr2 == 0 ) { print " arr2=" .@$arr2 . "X\n";; return - 1; } my $val = 0; foreach((@$arr , @$arr2)) { $val ^= $_; } return($val); } first sort the array.n then 1)for i=1 to n { if ( element [i] !=element [i+1] ) { cout<<element[i] break } else { i=i+2 } } I dnt have any idea about its time complexity... Show More Responses This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer. public int returnNonRepeat(int[] input) { if(input.length < 3) return -1; else { int repeat = null; if(input[0] == input[1]) repeat = input[0]; else if(input[0] == input[2]) return input[1]; else return input[0]; for(int i = 2; i<input.length; i++) { if(input[i] != repeat) return input[i]; } } return -1; } Cant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) space only 2 possible solutions 1.) using sorting 2.) using additional space. which will be less than o(n) sub find_odd { my @a = @{$_[0]}; my ($i, $n); $n = $a[0]; for $i (1 .. $#a) { $n = $n ^ $a[$i]; } printf("number is %s\n", $n); } |

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

What are the first 2 integers that, when added together, equal 10 in a "very large" array of unsigned integers? 6 AnswersMy in-interview answer was bad!!! I came up with a better one using a 2d array with 11 rows and 2 columns. First column to hold the first occurrence of each integer 0-10 (conveniently, the indices of each row match a relevent integer) and second column to hold the second occurrence of 5. When you first encounter an integer that can be used to equal 10, add the index to the first column. When encounter 5 for the second time, add it to the second column. Each time you update a value, check to see if both sides of the equation are populated...if so, you have your answer, if not continue on with the original array. Note: Adding the index enables you to keep track of WHERE the integers were in the original array, however if that doesn't matter, you could update it with any value that works for your evaluation logic. It's a specific case of the problem of finding two integers that add up to a given number in a list of integers. In general case, you do need to sort first and use two pointers from start and end and use an elimination to search in O(n). In this case, since sum is already given (a constant) we just need to maintain last unique indices of integrers <= 10. Any time we find two that adds up to 10 is the answer. if it is a "very large" collection, avoid sorting; i think we are creating a time consuming cycle there. i have given a little piece of code for a similar question in this forum itself, which can be used as a starting point for bettering your answers. i got this question few years ago, when i went for an interview, with a bay area network security company.. as a UI developer !! Show More Responses should not sort it. Create an array or length 11 (index of 0-10), call it H, fill it with null (you can use -1 as null) Call original array A. Code is very simple: i = 0 while(i++) complement = 10 - A[i] if(H[complement] == null) H[complement] = i else break at this point A[H[complement]] + A[i] == 10 I'm essentially using H as a hash table where hash(n) = n this solves the problem in O(n) I believe. I think hashing is preferred in this case. @maxzed2k I'm not entirely sure if your solution will cover all cases. What if the complement (i.e. 10-A[i]) is negative? H[ ] will give you a segmentation fault. |

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

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 Responses I 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). |

Given the head pointers to two linked lists of unknown length, find the node of intersection if they do intersect. 5 AnswersSuppose that the pointers are head1 and head2. Move head1 and increment a count1 till head1 reaches null. Move head2 and increment count2 till head2 reaches null. If head1 > head2 or head2 > head1, move the respective pointer to such a position in the linked list so that the length of the linked lists from there are equal. Then, start checking if both pointers point to the same node and incrementing both until that condition is met. If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection. I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer. My solutions: Suppose length of List A is m, length of List B is n, If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop) If time is more of a concern, 1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n). 2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)). 3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)). the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n))) pblm can be solved by making a circular linked list. Start with head1 and traverse thru the list and modify the lastnode.nxtptr -> head2 Now start with head2 and traverse. If you reach the head2 again then the list do intersect. Show More Responses Vijay has the best solution with linear time. Vijay's solution works great for finding out whether they intersect, but the question asks for finding the node of intersection. I think William's solution will work best for finding the node of intersection. The obvious one is an O(n^2) solution by traversing the first list with the nodes of the second list and doing a comparison. |

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

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

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

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

**31**–

**40**of

**3,360**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