# Interview Questions

interview questions shared by candidates

## Interview Questions

To find and return the common node of two linked lists merged into a 'Y' shape. 13 Answershow did the two linked lists make their poses to merge into a 'Y' shape, one's head attached to the waist? please explain more to help understand the question The two linked lists were something like: 1->2->3->4->5 and 3->4->5->6->7->8. For a Y shaped like this: 1 -> 2 -> 3 -> 4 ->7 -> 8 -> 9 5 -> 6 -> 7 -> 8 -> 9 where the trunk portion is of constant length, it is easy. Get the length of the first list. In our case 7. Get the length of the second list: 5. Difference is 2. This has to come from the legs. So, walk the difference in the larger list. Now node1 points to 3. node 2 points to 5. Now, walk through the two lists until the next pointers are the same. Show More Responses @kvr what if the lists are 1-2-3-4-7-8-9 and 12-13-14-5-6-8-9 Can this be done using hash tables? Or is there anything more efficient? i think that kvr's answer is the best. @snv if the two lists are linked by the very last two nodes, then you would find out after you are checking the values of the second two last two nodes. you just got unlucky and basically have to check until the very end. so basically, as a diagram with your example, it would look like this 1 -2 -3 -4-7-8-9 x -x -x -x -x-o 12-13-14-5-6-8-9 (sorry about spacing) but because you know the difference in length is 0, you can start comparing the two lists of nodes one by one. from the very beginning. HASH TABLE seems the only efficient wt. 1. add each element's address (of the smallest list)and push it to the hash table. 2. start walking second list. 3. get element compar eits address with hash table if match is found in hash table, return 4. if list is not exhausted, go to step 2. 5. return NULL Hashtable is complete overkill. The point is to realize that the two linked lists have the same tail. That means if you traverse them with the same index but from the right you will eventually find the first similar node. It's almost as easy if the problem said the two linked lists had the same prefix, find the first node on which they split. Here you walk them with the same index from the left. First reverse both list and find point where both gets diverged For Y condition the list could be List 1: 1->2->3->4->5->6 List 2: 7->8->9->4->5->6 So reverse list would be 6->5->4->3->2->1 6->5->4->9->8->7 now compare two list and move forward the position where you find next node of both are different is the point of merging Some of the above will work for doubly linked list. If not, travel node by node simultaneously from each end. When one traversal ends and the postion of cursor at the traversal is the answer kvr's answer is good but I think it could be optimized better by using 2 stacks. Traverse both lists putting each value into 2 separate stacks. Then when both are fully traversed, the head of each stack will match. Pop one off each at a time till they don't match, return the last popped. But I suppose it comes down to where the first match is at. If its the beginning of the list, kvr's answer will be better, if its at the end or bottom half 2 stacks would be better. Let's say L1 is the list starting with the lower number, and L2 is the other Set X = Head of L1 Set Y = Head of L2 While X <= Y Set X = Next(L1) End While If (X==Y) Return X Else While Y<=X Set Y = Next(L2) End While If X==Y Return X End If End If Repeat until you reach the end of either list. |

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

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? ^^ 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 Show More Responses 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. 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). |

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

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

Given a list of integers, some of which may be negative, extract the pair that sums to the largest number. 8 AnswersThe naive solution is O(n^2). The trick is to sort the list in O(n lg n) then pick the two largest numbers from the front. you can get the largest two number in O(n), right? sum those two numbers up. Whoops, I wrote the wrong question. Here's what I meant to say: given a list of integers, find a pair that sums to a given value. Show More Responses Keep a list of integers, and set it to 1 if they are in within the list. for (int i = 0; i < n; ++i) dp[array[i]] = 1; for (int i = 0; i < n; ++i) if (dp[S - array[i]] && S - array[i] != array[i]) print S - array[i] and array[i] because they sum to S This is the subset problem. This is O( n ), but requires O( S ) space. @bleh: I guess the solution will work if all the elements are +ve, in this case however the elements are negative. So probably we can use hash instead of arrays. if both hashing and the subset solution aren't good enough - 1. Sort the array o(n) or o(nlogn) - pick the one you can sell 2. Have two pointers - one at the end and the other at the beginning 3.a. If the sum is less than S increment the one in the beginning 3.b. If the sum is greater than S decrement the one at the end 3.c If the sum is S - you are done 3.d If the two pointers have met or crossed over - you are done Amazon really loves dynamic programming eh? I've come across many interview questions with the knapsack and coin-change problems #define SIZE 3 int tab[SIZE]; int sum; int max=-MAXINT; int sovi, sovj; for(i=0; i max) { max=sum+tab[j]; sovi=i; sovj=j; } } } printf("\n i: %d j:%d", sovi, sovj); |

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 |

### Area Manager at Amazon was asked...

You have 25 laborers for a shift. Pickers pick 100 units an hour Small item packers pack 150 units an hour Large item packers pack 25 units an hour You must pack 7500 small units during a ten hour shift. How would you staff your shift? 9 Answers10 Pickers 10,000 units/shift 5 Small Item Packers 7500 units/shift 10 Large Item Packers 2500 units/shift This was the right answer, they have you explain it. I must be thick because I don't understand your answer. You picked 3 options. What is the correct answer? Ron, the goal is to balance out the shift while meeting the one demand (7500 small items packed). so you know you will need 5 small item packers. what to do with the other 20? The answer is correct. I just happen to have an area manager interview in Phoenix this thursday and now I know the question and answer Show More Responses You gave a single answer... Right answer? sure. Right response? no. 25 Workers (breaks up nicely with 5 laborer unit ratios): A) 3:2 Pickers to Small Item Packers B) 1:4 Pickers to Large Item Packers C) 2:1:2 Pickers to Small item Packers to Pickers 5 Small item packers are required. Any combination of A, B and C where the number of small item packers >= 5. Candidate's response: 5*C (A valid answer only meeting the minimum demand for small items) Why would the candidate's answer be better than 5*A? 15 Pickers 15,000 units/shift 10 Small item Packers 15,000 units/shift Why would the candidate's answer be better than 2*A + 3*C? 12 Pickers 12,000 units/shift 7 Small item Packers 10,500 units/shift 6 Large item Packers 1,500 units/shift Why would the candidate's answer be better than 3*A + 2*B? 11 Pickers 11,000 units/shift 6 Small item Packers 9,000 units/shift 8 Large item Packers 2,000 units/shift ^--If they asked for a single solution, I'd argue this one would be better since you buffered the small item output. Why wouldn't you use the following variation as it maximizes the potential for daily output 4*A +1*B result would be 13 Pickers 13,000 Units/shift 8 Small Item Packers 12,000 Units/Shift 4 Large Item Packers 1,000 Units/Shift Just a question.... Maximizing your daily output is not necessarily the way to go. You have customers waiting for orders and if you work on mostly smalls, the amount of large units in your backlog will be high. So while your numbers look good, you may not being getting orders out to customers timley. This question would make more sense if it said how many units have been ordered of small and large items so you can be sure to get through the orders in a FIFO basis. The question states that 75% of items go to the small packers and 25% to the large packers, that is the reason the interviewed candidates answer is correct. simple algebra. 8 picker 8x 100 =800 per hour 5 small packer 5 x150= 750 per hour. 25 laborers for shift. Picker are packing 125 units of large items. Small item are packing 175 units. Each laborer does 12 units each producing 300 units. The 300 units produce by the 25 laborers Will produce 7500. |

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

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

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

If you have a file containing millions of integers, how would you sort the data in the file using extremely limited resources, such a s 1GB of memory? 8 AnswersWhat was the answer? In my opinion, I would answer this way: Sort each x integers (x is the number of integers that the memory can hold) then save it to the a file (n files) . Then for each file maintain a current index initiated with 0. Loop through n file and take the max integer, put it into the result file, and increase the file's current index to one. Continue doing it till the end. An integer is only 4 bytes! I am just saying, a million integers should consume about 4 MB of memory, and easily fit in 1 GB! So "millions" had better be closer to a quarter billion if memory is an issue. OK, to answer the intended question, I would solve it with statistics. Compute bucket ranges by using a random subset of the file, with bucket size chosen such that the expected portion of the entire file will fit within the memory available. Divide the file into these buckets, and sort the buckets individually. Concatenate the sorted buckets to create a single sorted file. To Kurt: You missed one step. Concatenating buckets will not make a sorted list. You have to merge the buckets. However, for merging you do not necessarily have to load the whole bucket into memory. Show More Responses millions is not too much , you can build a int array which have millions of cells. The array take only several mega bytes . Initialize to zero for every cell, then traverse the file and keep track of every integer by array , eg . 4789 will make array[4789]++ , this could handle duplicate number . Finally scan the array ... the interviewer is looking for the word "divide and conquer". read the n number of integers and write them in a binary tree. hold the left and right value in a datastructure which keeps track of the file an integer is written to. something like this class NumHolder { int min; int max; String fileName; } Map partInfo = new HashMap() for (int i=0; i 100000 //100000 = sum number that determines how many part files will be created. writeToOtherFileToo writeToPartFile update partInfo with this write } its called 'external sorting'... read more on wiki... divide the file in chunks, sort individuals chunks using quicksort and store in files. Then use merging step of merge sort on those saved files. This would be external sort. use external sorting algorithm similar to merge sort which splits and merges files instead of arrays in memory |