Software Development Engineer Interview Questions | Glassdoor

# Software Development Engineer Interview Questions

4,126

Software development engineer 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.10 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 mapoperating all each element xor Time complexity On Space complexity O1operating all each element xor Time complexity On Space complexity O1

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

Aug 13, 2013

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

May 20, 2010
 Given a list of n numbers. All numbers except one are unique. Find the number with duplicate entry.10 AnswersI gave an nlogn solution, where I said we will heap sort / quick sort the array, and then do a linear traversal to find out the duplicate entry. The interviewer was okay with the solution, and then she asked me code it, and then to write test cases for it.How about using hashtable?Use the function n(n+1)/2 = sum(0,n). Sum up all of the numbers in the array. Subtract the number from the function from the number in given by the sum. That will be your duplicate entry. public static int dupeNum ( int [] array ){ int arraySum = 0; int arraylength = array.length; int knownSum = (arrayLength * ( arrayLength + 1 ) ) / 2; for (int i : array ){ arraySum += array[i]; } return (arraySum - knownSum) ; } Should be O(n).Show More Responses^^ person who replied above: Your solution fails if the numbers aren't sequential - for all you know, 'a list of n numbers' could be 'n' random numbersMerge sort it and then it iterate through the list. This takes nlogn time. public in getDuplicate(List list) { List sortedList = Mergesort(list); for(int i = 0; i < sortedList.length-1; i++) if(sortedList[i] == sortedList[i+1]) return SortedList[i]; Throw exception; }take XOR of all the numbers.You will get the sum with out the duplicated number. (sum of all n - above sum) will give you the numberput the numbers into hashmap while traversing the list. Before placing the key into hashmap check whether it is null or not. if it isnot you've found it. worst case O(n). extra hashmap in the memory.i would sort them in n log and then traverse them. while traversing, chech two adjacent numbers are different. if not, that is the number.Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.

Dec 22, 2010

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

Jan 18, 2012