# Development Engineer Interview Questions

Development engineer interview questions shared by candidates

## Top Interview Questions

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

List all anagrams in a file. Assumptions: case-insensitive, a-z characters only, one word per line. For example, if the file contains dog, cat, ddd, goo, act, god -- output dog, god, act, cat 10 AnswersThankfully I was taking a theory course and one trick used in the course was "encoding" programs as a large natural number using product of primes. 1. Adapt the encoding as follows -- generate the first 26 primes and assign a prime to each letter 2a. For each word, take the product of each letter's prime. So #(act) = 2*5*prime(t) 2b. As you can see, #(cat) = 5*2*prime(t) = #(act) 3. Insert a handwavey argument about inserting the number/word pairing into a HashMap> Sort the words. Anagrams appear next to each other in the sorted list. Sorry, sort the letters in each word, then sort the words. Anagrams appear next to each other in the list. For example the sorted list for the input would be: act act ddd dgo dgo goo Show More Responses Thanks for sharing Bill For this set of input, the expected output should contain only [cat, act, god, dog]. I'm curious to see what "next steps" your algorithm will perform to provide this expected output You keep track of the mapping from the sorted word to the actual word in a pair, for example: [act, cat] [act, act] [ddd, ddd] [dgo, god] [dgo, dog] [goo, goo] Then you go through this list and count if you have a duplicate entry or not. If you do, like for act, you print out those duplicate entries: cat, act. Bill, your algorithm is O(n*log(n)) while the candidates would be O(n) - provided he uses a decent hash function donutello, bills algo is not n log n it is n*log(k) where as candidates algo is n * k again (multiplications for each word) where k = length of the longest word on top of that calculating primes is expensive anyway I would go with bills answer Bills algo is nlogk + nlgn. After sorting the k letters for n times you also have to sort the n words. #Get inputs a = [] f = open('input.txt','r') for line in f: line = line.strip() a.append(line) #Sort letters in a word def sort_letter(s): r = [] for i in s: r.append(i) t = sorted(r) v = ''.join(t) return v #Find anagrams d = {} for v in a: sv = sort_letter(v) if sv in d: d[sv].append(v) else: d[sv] = [v] #Print results for k,v in d.items(): if len(v) > 1: for s in v: print s think of each line as a set of characters, not a word, then create set of sets of characters which you fill from the input. then print the set (order does not matter as its not specified) |

### 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? 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 a list of n numbers. All numbers except one are unique. Find the number with duplicate entry. 8 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. |

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

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

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

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<maze.length; j++) { maze[j] = br.readLine().replaceAll(" ", "").toCharArray(); } System.out.println(maze[2][0]); } public void findPathBreadthFirt(){ queue.add(startingPoint); hm.put(startingPoint, startingPoint); while(!queue.isEmpty()){ Node n = queue.poll(); if(n.equals(endPoint)){ printPathUsingParent(n); break; } addAdjacentVertices(n); } } public void printPathUsingParent(Node destination){ Node current = destination; while(current.parentNode!=null){ System.out.println(current.toString()); current = current.parentNode; } System.out.println(current.toString()); } public void addAdjacentVertices(Node v){ Node v1 =v; int row = v1.row; int column=v1.column; boolean added =false; //check if any point exist in the top side and add it in the Queue if(v1.row!=0 ){ if(convertCharToInt(maze[row-1][column])==0 ){ Node top = new Node(row-1,column); if(!hm.containsKey(top)){ addIntoMapAndStack(top,v); added=true; } } } // check point in the bottom and add it int he queue if(v1.row!=maze.length){ if(convertCharToInt(maze[row+1][column])==0){ Node bottom = new Node(row+1,column); if(!hm.containsKey(bottom)){ addIntoMapAndStack(bottom,v); added=true; } } } // check point in the right and add if(v1.column!=maze[1].length){ if(convertCharToInt(maze[row][column+1])==0){ Node right = new Node(row,column+1); if(!hm.containsKey(right)){ addIntoMapAndStack(right,v); added=true; } } } // check point in the left and add. if(v1.column!=0){ if(convertCharToInt(maze[row][column-1])==0){ Node left = new Node(row,column-1); if(!hm.containsKey(left)){ addIntoMapAndStack(left,v); added=true; } } } } public int convertCharToInt(char c){ return Character.getNumericValue(c); } public void addIntoMapAndStack(Node v,Node parentNode){ v.setParentNode(parentNode); stack.add(v); queue.add(v); hm.put(v, v); } public static void main(String [] args) throws IOException { MazePath mp = new MazePath(); mp.createArray(); // mp.findPathDepthFirt(); mp.findPathBreadthFirt(); } } 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(); } } |

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]) method 6 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 operation Could you make a more clear description the operation of Flip functon? Thanks! Show More Responses For 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). |

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 |

**21**–

**30**of

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