# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

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

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

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 hashing xor all elements keep 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 answer Can explain the XOR answer pl. thanks if 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 operating all each element xor Time complexity On Space complexity O1 operating all each element xor Time complexity On Space complexity O1 |

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 Responses How 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 Solution i like the recursion solution because the smaller results can be cached and reused Untested 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) |

Determine if an array from 1..n has a duplicate in constant time and space. 12 AnswersCorrect answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate. ^^ Sorry, that's linear time *and* at best linear space, you fail. What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates. Show More Responses SUM(array) - (N(N+1)/2) = missing number. @Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4} I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap. I'm pretty sure OP posted something wrong there, and they were probably asking to do it in linear time and not constant. If it's constant, the way I would do it would be using a HashSet to check if the key (value in array) is contained, and if not add it to the set. If at any time I find an element that's already inside, return false; If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate. I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1. |

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 numbers Merge 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 number put 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. |

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

Find the last element of a linked list. 7 Answerspublic *Node LastElement(Node *Head) { while(Head->next != null) { Head = Head->next; } return Head; } Did they really ask you this question? Although Praveen's answer is correct, It seems that his answer would also be very time-consuming. Is there another way to find the last element on a linked list - assuming that it's singularly linked? Did they really ask you this question? Although Praveen's answer is correct, It seems that his answer would also be very time-consuming. Is there another way to find the last element on a linked list - assuming that it's singularly linked? Show More Responses praveen's answer is correct but not good enough, you would not want to modify the pointer you got it might be your only ptr to the head of the list. public *Node LastElement(Node *Head) { Node *iter = Head; while(iter->next != null) { iter = iter->next; } return iter; } would be more correct. Because the parameters are always passed by value. Even if you modify the input parameters, the original variable remains unchanged. I am talking about the case where you don't specifically pass the params as references in C++. In C, my statement holds. All the answers are partially correct. Anonymous: The function accepts a pointer not a reference to the pointer (pass by value). Hence if the pointer 'Head' is modified in the function, it doesn't affect the actualy pointer that was passed into the function. However, what's missing in Praveen's solution is the boundary condition of whether the Head node is NULL. If it is, then the starting statement of the while loop is going to access a NULL pointer. The correct solution should be something like: Node* GetLastNode(Node* head) { // Loops through till the end of the node for(; head != NULL && head->next; head = head->next); // Return the last node (This could be NULL if head was NULL). return head; } |

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 space Well, 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))/2 Show More Responses For 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 then O(1) meaning constant, which implies does not change due to input size change Generate 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 memory They may not be sorted..comparing won't work in linear time Best 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...

"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 My previous answer was an implementation and here brief description on the implementation. * 1) Read a maze from file and convert into a int[][] array. * 2) Declare starting point and end point * 3) declare Queue and add startingPoint in that queue. * 4) Deque the node from Queue and find all the possible path add it in the queue again. * 5) Each Node contains a reference to their parent Node. Starting point doesn't contains any reference to the parent node. * 6) While dequeing a node, if it matches with endpoint then traverse back to the starting point and that's the path of the maze. * 7) To avoid duplicate traversing, create a visited=true flag or use HashMap. * * queue.add(startingPoint); * hm.put(startingPoint, startingPoint); while(!queue.isEmpty()){ Node n = queue.poll(); if(n.equals(endPoint)){ printPathUsingParent(n); break; } addAdjacentVertices(n); } */ Show More Responses Here is a concept that may works, starting from the beginning point, each step could lead to possibly three path, we can draw a tree which each node has three children (max), then find the longest path would do it, each dead end will determine if the current node has any child or not. enter the maze into a graph data structure where adjacent 0's are connected to each other with an edge. Label the starting and ending points, and do a DFS from the starting location. This would be an internal solution, as there would be no visual representation of it, but you could easily enough attach coordinates to each node to allow for a visual solution A* Algorithm Wikipedia has a nice animated image to describe it import java.util.Scanner; public class MazeProblem { int x, y; int[][] problem; public void solve() { int[][] solution = new int[x][y]; if (solveMaze(solution, 0, 0)) { System.out.println("Yes "); for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { System.out.print(solution[i][j] + " "); } System.out.println(); } } else { System.out.println("No Solution"); for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { System.out.print(solution[i][j] + " "); } System.out.println(); } } } private boolean solveMaze(int[][] solution, int x, int y) { if (x == this.x - 1 && y == this.y - 1) { solution[x][y] = 1; return true; } if (isSafe(x, y)) { solution[x][y] = 1; if (solveMaze(solution, x, y + 1)) { return true; } if (solveMaze(solution, x + 1, y)) { return true; } solution[x][y] = 0; return false; } return false; } private boolean isSafe(int x, int y) { if (x < this.x && y < this.y && problem[x][y] == 1) { return true; } return false; } public static void main(String[] args) { Scanner input = new Scanner(System.in); MazeProblem mazeProblem = new MazeProblem(); mazeProblem.x = input.nextInt(); mazeProblem.y = input.nextInt(); mazeProblem.problem = new int[mazeProblem.x][mazeProblem.y]; for (int i = 0; i < mazeProblem.x; i++) { for (int j = 0; j < mazeProblem.y; j++) { mazeProblem.problem[i][j] = input.nextInt(); } } mazeProblem.solve(); } } |

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

To return the 'm' smallest numbers from a file of 'n' numbers 8 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 array Show More Responses Anuj, 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 partitioning Maintain 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 |

**11**–

**20**of

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