Software Engineer Developer Interview Questions | Glassdoor

# Software Engineer Developer Interview Questions

3,547

Software engineer developer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Jan 14, 2010
 How would you find the pairs of numbers that added to some specific number in an array. 7 Answersi program in java..so i will talk from the arrayLists perspective. suppose we want to find out a+b = 123; for(int i=0; i2000 records.but below that, sorting and above operation is efficient. you must play with different possibilities.Your answer (using arrayList.indexOf(...)) is worse than sorting. Sorting is O(log n), finding an item in an unsorted array using ArrayList.indexOf is O(n). Given an unsorted array input (e.g. int[] input), sort it using Array.sort(input) ... this is O(log n). Start at input[0] of the sorted array and calculate it's complementary value. Go to the end of the array and iterate backwards until you find the complementary value or less. If it's less repeat for input[1] and iterate backwards from the previous last item ... keep going. This is at worst proportional to n/2, ie O(n).I realize I wasn't totally clear in my first paragraph ... searching for the complementary value of one item is O(n), but you have to the search for (at worst) every item, so your solution is O(n^2).Show More ResponsesDuh - sorting is O(nlog n) ...Using hashing, this can be done in O(N). store the n/2 mod i in the corresponding hash bucket. Now check the each hash bucket and you are done.sort the array (o(n(log(n)) and take two pointers at both the ends say p1 and p2 if p1+ p2 move the pointer p2 by 1 and add to check if (p1+p2) > n -> move the pointer p1 by 1 and add to check if (p1+p2) = n ->print the pair [traversal takes o(n)] finally thus can be done in o(n)I will not waste o(nlogn) in sorting the array. Instead assuming that the sum we looking for is k, i will divide the array into 2 arrays. First array will contain all values which are less than k/2 Second array will contain all values > k/2 This is bcoz in a sum if one number is less than k/2, the other has to be larger. I will iterate over the smaller array of the 2 since they would rarely be equal. For each x in array 1, i will find the k-x in array 2. Complexity will be O(n).

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

Jun 5, 2010
 Given an array of integer in which all numbers occur even times except for one number occurs odd times, find it.8 Answersi) sort array (n or nlogn at the max). go through array and count #occurrences for each num. (memory: null, just 1 var) ii) if lots of memory then use hashingxor all elementskeep on adding the elements,wherever the sum becomes odd that number is the odd one.Show More Responses"keep on adding the elements,wherever the sum becomes odd that number is the odd one." Fails on int array[] = {2, 2, 4, 3, 3}xor is the correct answerCan explain the XOR answer pl. thanksif you xor an number with it self you get 0 , if you xor a number with 0 you get the number it self, eg 2,2,4,3,3 2^2 = 0 0^4 = 4 4^3= 7 7^3 = 4 and the answer is 4,We can also use a Hashmap and the first time we get an element we put 1, the next time we get it we remove it from the map...In the end only the required answer will be in the map

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

May 9, 2012
 Given an integer set of numbers, print all the subsets. For some reason the interviewer asked to print the supersets, but what he means is subsets.9 AnswersI could not answer this one question (1st question of 2nd phone interview), he did not give any hints, just waited till I struggled for 15 minutes and ended the interview. Did not get next call.void print_subsets(int numbers[], int num_of_numbers) { int pow_of_num = pow(2, num_of_numbers); int i; }#include #include using namespace std; void print_subsets(int numbers[], int num_of_numbers) { int pow_of_num = pow(2.0, num_of_numbers); int i; for (i = 1; i < pow_of_num; ++i) { int j = i; int digit = 0; while (j != 0) { if (j % 2) { cout << numbers[digit] << endl; } ++digit; j /= 2; // This can also be done by bitwise operation } cout << "===============" << endl; } } void print_subsets_test_drive() { int numbers[] = {1, 2, 3, 4, 5}; print_subsets(numbers, 5); } int main() { print_subsets_test_drive(); return 0; } Output: 1 =============== 2 =============== 1 2 =============== 3 =============== 1 3 =============== 2 3 =============== 1 2 3 =============== 4 =============== 1 4 =============== 2 4 =============== 1 2 4 =============== 3 4 =============== 1 3 4 =============== 2 3 4 =============== 1 2 3 4 =============== 5 =============== 1 5 =============== 2 5 =============== 1 2 5 =============== 3 5 =============== 1 3 5 =============== 2 3 5 =============== 1 2 3 5 =============== 4 5 =============== 1 4 5 =============== 2 4 5 =============== 1 2 4 5 =============== 3 4 5 =============== 1 3 4 5 =============== 2 3 4 5 =============== 1 2 3 4 5 ===============Show More ResponsesHow about using recursive to solve the problem? There are two base cases: 1. if array.length = 1, then the subset is itself 2. if array.length = 2, then the subsets are 3, {element1}, {element2} and {element1, element2} For a array with length > 2, then the subsets are: {element1} subsets(subarray(element2, ..., elementN)) {element1, subsets(subarray(element2, ..., elementN ))}Thanks MGhost, trying to completely understand your solution took me some time but helped me clarify a bunch of stuff with sets and stuff. Thanks man.Can you please explain the logic?MGhost Nice Solutioni like the recursion solution because the smaller results can be cached and reusedUntested but I believe this will work: def printSubsets(narr): q = narr n = len(narr) for i = 0 to n: for j in q: print q[j], printSubsets(q[j:]) print front = q.popfront() q.pushback(front) narr = [ 7, 4, 11, 3, 2, 5 ] printSubsets(narr)

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

Jul 10, 2009
 Given an array with length n-1 which contains integers of the range 1 to n. Each element is distinct and appears only once. One integer is missing. Find the missing integer in linear time using O(1) memory. Now two integers are missing, find them out in linear time using O(1) memory. How about three? 11 Answerswe know that sum of n integer is n(n+1)/2 we calculate the sum, of the array, takes O(n) time sum - n(n+1)/2 gives us the missing number takes O(1) memory spaceWell, that doesn't answer the other question on two integers and three integers.for 2 missing numbers: we know what is the sum of n integers, and we know what is the sum of squares of n integers. We calculate a1+...+an, and subtract it from the sum - which gives us sum of 2 missing numbers: x+y = a We calculate a1^2+...+an^2 and subtract it from the sum of squares - that gives us x^2+y^2 = b 2b-a^2 = x^2+y^2-2xy = (x-y)^2. Having x+y and x-y we can calculate the missing numbers as: (a+/-sqrt(2b-a^2))/2Show More ResponsesFor 3 missing numbers: Calculate: x+y+z = a x^2+y^2+z^2 = b x^3+y^3+z^3 = c Now, try every possible number from 1 to n as z: assuming that x+y = a-z x^2+y^2 = b-z^2 calculate x and y using method from solution for 2 missing numbers. If x,y,z are unique integers from 1..n try if x^3+y^3+z^3 equals to c calculated before, then those are the missing numbers. In last step we do n iteration of loop, but each iteration takes O(1), so the total time is O(n)Lucita, your answers are impressive but how you are using O(1) space?you don't need to allocate memory to compute a sum...Yea? Where do you store the running sum thenO(1) meaning constant, which implies does not change due to input size changeGenerate values from 1 to n and loop through comparing the elements in the array with the value from generated values. If a number doesn't match up it means it's missing. Can yield the value and search for 2nd and 3rd with another call. Linear time and constant memoryThey may not be sorted..comparing won't work in linear timeBest way is do a bitwise xor of 1..n and the given array Then let's say we have x ^ y^ z = a Now based on the bits in 'a' we can derive x y and z Operations include bitwise shift Bitwise and This is more scalable and is in linear time and O(1) space

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

Jan 18, 2012
 "Solve a maze", you have a 2D matrix with 1's as blocked and 0's as path. Find a path from one corner to another, backtracking should be allowed. 7 AnswersMight be a little sloppy, but it works. public static int solveMaze(int[][] maze, int i, int j, int oldi, int oldj) { int solved = 0; if((i+1) == maze.length && (j+1) == maze[i].length) { return 1; } if((j-1) >= 0 && (j-1) != oldj && maze[i][j-1] == 0) { solved = solveMaze(maze, i, j-1, i, j); } if(solved != 1 && (i-1) >= 0 && (i-1) != oldi && maze[i-1][j] == 0) { solved = solveMaze(maze, i-1, j, i, j); } if(solved != 1 && (j+1) < maze[i].length && (j+1) != oldj && maze[i][j+1] == 0) { solved = solveMaze(maze, i, j+1, i, j); } if(solved != 1 && (i+1) < maze.length && (i+1) != oldi && maze[i+1][j] == 0) { solved = solveMaze(maze, i+1, j, i, j); } return solved; }Here is the maze. 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 0 1 F 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 public class MazePath { char[][] maze = new char[12][12]; Queue queue = new LinkedList(); // Define the starting point and endpoint in a node. Node startingPoint = new Node(1,1); Node endPoint = new Node(10,10); Map hm = new HashMap(); public void createArray() throws IOException{ // read maze from a file and create an array FileInputStream in = new FileInputStream("c:/Personal/Maze.txt"); BufferedReader br = new BufferedReader(new InputStreamReader(in)); String strLine; for(int j = 0; j

### 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 Engineer Intern at Amazon was asked...

Feb 15, 2012
 To return the 'm' smallest numbers from a file of 'n' numbers8 AnswersI would first create an array holding the first m values of the file, and sort. Then, each value I read from the file, I can compare the the last (largest) value in the array. If its smaller, do a binary search to find the correct spot in the array. Insert the number and shift everything behind it back by 1. Worst case runtime will be O(n lg m)Why cant we simply start with min=INT_MIN. Then, read first number from file, if lower, set min=that number. Seek next number and so on... We dont need to load the whole file. We will go to the disk often though.I will create a min heap with the given numbers and extract 'm' minimums from the heap which will get stored into the resultant arrayShow More ResponsesAnuj, Wont it take time of O((M+N)log N)@spammer, I think it's O(n+m*log n), since you can construct the min heap bottom-up and that only takes O(n)Why don't we just sort the array and return the first m numbers? Takes O(nlogn) for sorting and O(m) to return the first m numbers.Modified quick sort. Pick a pivot and test if one half is smaller than m. If it is, drag the rest from the other half; if it is not, keep partitioningMaintain a heap of m numbers and also track a variable which stores the current highest value. So as u go through the n numbers, if the number is higher than the current highest number, ignore it else insert it into the heap and set the current highest value to the newly inserted value

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

### 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.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<
2130 of 3,547 Interview Questions