Software Development Engineer Interview Questions | Glassdoor

# Software Development Engineer Interview Questions

4,124

Software development engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Jan 27, 2012
 Asked to implement a function that takes an integer and returns whether or not the number had an odd or even number of 1 bits. 6 AnswersIt started out with an ambiguous set-up so the first thing that needed to be figured out was what kind of number to be taken in. How many bits this value was. I was told to assume it was 32 bits. I mentioned that the number may be in 2's complement, I was told to only expect unsigned integers. The solution is pretty straight forward, it only requires a for loop that counts from 0 to 31 and checks whether the integer masked with 1 is equal to 1. If it is, add one to the accumulator and shift a bit to the right. Then I was told to extend this function to work for an n bit integer. With some hints I figured out that log base 2 of a number gave you the maximum number of bits it would take to store that number so simply replace the loop that went from 0 to 31 with a loop that goes from 0 to log_2(n).If the task is only for positive numbers, then my solution would be: bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; do { result |= ((n % 2) == 1); n /= 2; } while ((n / 2) != 0); return result; }Show More Responsesmod and div operators are good, but you could set yourself apart by using a more efficient algorithm. In terms of big O, it will be the same, but it will have a higher throughput since the operations are slightly faster. > bool is_odd_set_bits(unsigned number) { bool result = false; int n = number; while(n != 0) { result |= ((n & 0x01) == 1); n >> 1; } return result; } masking is faster than a mod operator, and bit shifting is faster than divisionsi was trying this in java and found kinda small bug... so we should return false if the number is 3 which is 0000000011. I guess changing the line to: result ^= ((n & 0x01) == 1); will do the job...PC, your solution is incorrect. It will always return true if the number has at least one set bit.

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

Dec 30, 2011
 Pancakes, size varies, and are put in a stack with random order. You have one operation called Flip(int[] pancakes, int k) to flip all pancakes from the top one to kth pancake, write a sort(int[] pancakes]) method6 AnswersYou can implement quicksort since swapping two items (i and j) can be done in three steps using the 1st item as a temporary position.Never mind the previous comment, misread the description of the Flip operationCould you make a more clear description the operation of Flip functon? Thanks!Show More ResponsesFor example, if pancakes are {1,2,4,3}, (number means pancake sizes), and if we flip(pancakes, 2), then the first two pancakes are flipped and result will be {2,1,4,3}Well, selection sort would work, but it's slow. Find position j of the minimum between [i,n-1], starting with i = 0. If j != i, then use Flip(pancakes,n-j) to get it to the top, then flip to its subsequent minimum position i, therefore Flip(pancakes,n-i). Keep repeating until increasing i reaches n.Hmm, if indirect sorting is allowed (via pointers in extra space), then one could use quicksort, and place into target positions by flipping. But if that flipping is the only operation available, then even finding the minimum value AND it's current position for the selection sort above gets nontrivial (but doable).

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

Jun 23, 2012
 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.8 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<Show More ResponsesThis 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; iCant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) spaceonly 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); }Use xor

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

Jan 29, 2012
 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 ResponsesAs 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.

Jan 6, 2011

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

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

Sep 26, 2012