# Amazon.com Interview Questions

interview questions at Amazon.com shared by candidates

## Amazon.com Interview Questions

### Shipping Manifest Clerk at Amazon was asked...

If you saw someone steal a quarter. Would you report it? 10 Answersyes No. I'd talk them out of it. Pay them a quarter from my own pocket if I had to. Who's integrity is worth 25¢? Easy to steal quarters? Where can I get in on this action? Show More Responses It is all part of a yes/no integrity test. The answer is "YES" because they want to know that you think ANY theft is wrong. It depends, if I saw a customer at Walmart reach into the til when the cashier is not looking, I would turn the person in. If my best friend stole a quarter from me, I would not turn her in. What is this?......the plot of Office Space where the guys use a computer program to steal pennies off of each transaction the company makes and then end up getting really rich??? I say if it's just one quarter, it's not worth it. Most stores don't prosecute for petty theft of even $50 or $100. It's not worth your energy. Coming from retail management and knowing how LP is looking at this: It starts with a quarter and usually gets bigger from there. (Greed ) I believe the only right answer is YES its stealing If you are willing to may exception because of the amount it shows that you will bend rules and fail the question. I have worked before companies that fired people for consuming discarded merchandise(written out of inventory like an open package of such-and-such) because it was a policy. Most comanies want to know their policies will be followed to the letter because that helps product the company. Although some companies may bend their rules where they see fit that is not what the interview is about . steal a little steal big, there's only one word to it. thief. steal a little steal big, there's only one word to it. thief. I will report it. Short answer - Yes/No. Deal with it YES. Report it, depends on the circumstances and outcome of my attempt to deal with it. Consider: If I saw someone pocket a quarter from the cash register or steal a small product ($.25 worth) I would definitely report it, but I'd give them the chance to report themselves first. Kind of like my parents would handle it with me, and how I handle it with my children - you steal, you return the merchandise AND pay for it AND apologize. If that doesn't settle the matter we proceed from there. Compared to ... If I saw someone pocket a quarter left on the lunch table at work after a few people got up I would not 'report' that, but would certainly handle it the same as above i.e., make sure they gave the $ (any amount) to one of the people who was sitting there. In Florida this is embraced by a grocery chain called Publix. They call it the Publix Price Guarantee - if they accidentally error on your checkout and you point it out to them they give you a refund for the item AND the item (free). Sorry for the long-winded response, but some of these 'behavioral' questions simply taunt us to relinquish personal &/or social responsibility in the name of 'proper procedure'. If we don't take responsibility for seemingly 'little things' we are in no position to 'blame' anyone when big things go wrong. Kind of like if something bad was happening in the workplace. If I feel it's unsafe to the point I need to leave I will certainly let my manager (and certain other people) know before departing. I think this perspective was forged by a combination of personality and experience. I had the opportunity to visit the WTC on 2/26/1993 for my company after the bombing, so all my co-workers and friends know there comes a time when YOU MUST DECIDE if you stay or if you leave. Restating the point, there comes a time when YOU MUST DECIDE to speak up &/or take action about improper (or illegal) behavior - at the workplace or anywhere else. Happy Holidays all. |

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

Traverse nodes in a binary tree 11 AnswersWhat is taught in compsci, and even what's in Knuth, isn't entirely right on modern out-of-order execution core CPUs void traverse(Node node){ if(node == null) return null; System.out.println(node.data); traverse(node.left); traverse(node.right); } It can't be that this candidate really serves on a language committee. I find it difficult to believe that someone who serves on a language standards committee doesn't care about the difference between an O(N^2) and an O(logN) solution, for that would be horrifying indeed. And in defense of the employee conducting the interview, if I did see a candidate that didn't care about the difference between the two, I really wouldn't care what they have on their resume. They could be a Turing award winner for all I would care. There's a valid point about spatial locality, etc, but for something like N = 10^6 (for example), I'll take even O(logN) disk reads (*gasp*), over N^2 quick register operations any day.. Show More Responses Well, I do serve on language committees, two to be precise (though one is mostly in a feed forward role). And I do care about the difference between O(N^2) and O(log N)! I gave a complex answer to the interviewer because there is so much "it depends on the situation and circumstance". Other companies had interview processes which coped far better with the ambiguity, but from what I saw Amazon's are very "by the book" black and white. Look, I interviewed for four roles within Amazon and all four interview experiences ranged between bad and truly awful, which is why I chose neither the worst nor best experience and wrote up a review of it here as representative of *my* personal experience. Some of my experiences with other Fortune 500 companies were equally awful, and there are reviews for those on here too. However, I did also have many very good interview experiences, and I begin work with one Fortune 500 company in the Fall with whom my interview experience - over 20+ hours over twelve interviewers - couldn't have been better. Tip to interviewers: it *really* helps if you at least read the abstracts of the academic papers the interviewee has written. You could easily segment those companies which do this from those which don't, and Amazon from my four experiences with them don't or didn't. I hope you weren't offended too much by my earlier comment. Your explanation just now puts things into better context. I have to admit that upon initially reading your original review it wasn't very clear to me that you understood or cared about the difference between O(logN) and O(N^4). If the company was also unclear on that, you have to admit that one can see why they wouldn't extend an offer. Of course not everything is about big-O, but you should still be able to give answers in terms of it when needed. It's great if you know about data locality and caches, but you should still be able to show the basic analysis too. On another point, of course you should try to reuse code, but you also need to demonstrate (in an interview more than ever) that you have the skills to write new code when necessary, not by pointing them to some open source project you did, but by writing some nice, clean code for them right on the spot. A demonstration of your high skill level is more impressive than a description. It's a proof-by-demonstration sort of culture. You might ask why anyone should re-invent the wheel, but I'll leave you with this: if you can't prove to them that you *can* reinvent the wheel, why would they believe you have the creativity needed to invent a motorcycle? Wasn't offended at all - in fact, your comment is by far the best made on this thread (as you can tell from everything else being deleted by glassdoor). And besides, caustic opinions of your opinions are part of publishing an opinion, I'm well used to it. My issue with Amazon - and it's one shared by my buddies within Amazon too - is there is too much box ticking of standardized procedures in the recruitment process. That rewards rote pre-learning the answers to the live programming tasks you do over the telephone (search google, you'll find precompiled cheat sheets for Amazon and indeed many of the big tech companies). That's hardly "writing some nice, clean code for them right on the spot" as you suggest. A github repo with 40,000 lines of code stretching over a decade is much harder to fake. Amazon ought to hire on that in preference, but their recruitment process requires a standardized approach. The company I start with in the Fall used a completely unstructured process. They interview you on things that THEY don't know anything about let alone you, and topics which have absolutely nothing to do with compsci or technology, so for example one topic was on mining copper on the Mongolian steppes. I know very little about that, and neither did they. But as the elite of the elite team (within the company) said at the start of the interview, "we're not going to talk at all about anything to do with code during this interview. We'll know if you're a good hire by seeing how you think on topics both you and us know nothing about". That company offered the lowest compensation of any offers I received. But boy, what a great interview experience, so I had to accept. I hope working there is even 10% as good as they came across during the interviews. If so, I'm more than happy with lower pay. I'm no 10x programmer, maybe a 4x, so I'm not the perfect recruit. But I don't think Amazon should have failed me on stage 1 of each of the four roles I interviewed for. Hence the review. Mining copper on the Mongolian steppes, huh? That must be a very unique company. They're actually a multinational quite similar to Amazon - well known to consumers, occasionally known for moments of brilliance, otherwise fairly dull and dependable. Mining copper was one of many curve ball interview topics. Off the top of my head other topics included the technology policies of Kim Jung Il in North Korea, something about water and Tar Sands in Canada which I forget now, whether and how Russians are naturally good at science and math, how would you go about reconciling quantum physics with relativity, conflict resolution strategies between culturally disjunctive teams - and the list goes on much further (all this was many months ago now, so I'm forgetting). All this for a standard software engineering role, so I'm expected to be in a cubicle coding, not organizing world peace. Looking back on it now, it should have freaked me out much more than it did at the time. I suppose I was interviewing with so many companies at the same time it all just blurred. Anyway, we're getting off topic from Amazon's interview strategies. Amazon *are* a great company. They've soaked up the best and brightest from Microsoft particularly and it's a much less dysfunctional working environment than Microsoft where something went wrong a long time ago, but no one can agree exactly what, and even if they could agree, top management don't seriously think it's a problem. However Amazon is naturally silo-ized, where the consumer goods division is quite different to consumer services which is quite different to cloud provision and even cloud reliability provision. The problem, I think, is that Amazon's HR would prefer every engineer to be hired according to similar criteria, and that's where this box ticking standardized list of coding exercises comes from. As a comparison, Google's silo structure and hiring process is not dissimilar, though Google do run an elite expedited recruitment pathway which skips all the normal hoop jumping nonsense at the cost of fast tracking only those with the very best academic grades from the best US universities, or are famous. I have pretty terrible grades with a lot of bare scraping passes, none from Ivy League anything, and I'm not Dennis Richie or Rob Pike or Guido van Rossum famous. Still, it's interesting how companies start to struggle so hard with high skilled recruitment as they get bigger. It's not like there aren't very good HR books on the topic, yet no one in the HRs of these big famous tech multinationals seems to ever read them (or if they do, they sure don't implement them). I guess what I'm saying is that tech recruitment is hard, but it's not NP hard. Just be organized and constantly reflect on your hiring system. A very good start for Amazon would be to read these reviews on Glassdoor, and proactively enact changes so they're not failing candidates like me at stage 1 in the interview process (fail me later for lack of fit sure, but not on the initial programming exercise when I have 40k lines of open source contributions and I serve on ISO - that sort of indicates I'm not an incompetent programmer). Amazon also ought to knock some humility into some of their engineers, as a minority of them were rude and ignorant (I had one storm out during the telephone interview after giving a torrent of invective about me personally after I showed him up on a series of technical mistakes, and his colleague was clearly very embarrassed. As I said to him, "really, honestly don't worry about it, I've heard far worse said about me. But you can forget me ever working for Amazon after that"). I haven't posted a review of that interview on glassdoor because it was probably not representative of Amazon in general and the guy in question was probably just having a really bad day, though as I mentioned earlier, all four of my interviews did not go well. I just hope my review here has some effect within Amazon one day. As I said earlier, it *is* a great company. I agree with you. You have to focus on the person's ability to find answers not re-invent the wheel. If I were interviewing someone...as long as he can google a problem take me to an answer which perfectly fits the needs and then explain the solution (instead of blindly copying/pasting it) to me clearly, that would be the perfect candidate for the job. These kind of questions are only suitable for fresh out of college grads not people who have been in the industry for a long time. @NikB: Thanks for the comment. Certainly when I've been interviewing others, I'm generally fairly shocked at how awful the average candidate is - I mean, I catch an easy third who have lied on their resume and that's with five minutes of googling (depending on the lie, if they admit it in the interview, I actually give them a pass on it because I know what it's like to have poor grades from no name universities). About two thirds clearly have no integrity and will tell you whatever they think you want to hear, and I personally can't have that on my own teams (I won't veto hires for other teams on this though). About three quarters have no evidence that they seriously self-engage in continuing professional development e.g. teaching themselves new skills not directly needed for work. I would *far* prefer a poor programmer who continually self improves over a rock star programmer. I would *far* prefer a programmer who uploads even crappy non-reusable bits of personal script to github than someone who claims they have always been too busy to get round to it. It gives me extra information to evaluate that candidate. Less information = more uncertainty = much higher chance of me choosing elsewhere. A true coder codes all the time including people and social structures, and I want those on my team irrespective of skill. I agree only about half of those are willing to share their work with others, so lack of sharing does exclude a lot of worthwhile hires. But I guess we all have our personal preferences on what we think works best. Some colleagues of mine who I respect greatly think my hiring philosophy bananas! Do you mind if I ask what those 3 algorithms that you wrote are? |

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

Write an algorithm to determine whether a given number is of the form (2^n)+1, where n is an integer. 17 AnswersSubtract one and then keep dividing by two until you either get to 1 (true) or the number is not evenly divisible (false). return (n == 1) || ((n-1)&(n-2) == 0); bool if_power(int n) { n--; return n&(n-1) ? false : true ; } Show More Responses if(n%2==1) return TRUE else return FALSE boolean isapower(int pow, int num); int main(){ int num = 2; int pow = 2; if(isapower(pow, num-1)) { printf("%d is power of %d + 1", num, pow); } else { printf("%d is not power of %d + 1", num, pow); } return 0; } boolean isapower(int pow, int num) { while((num > pow) && (num % pow == 0)) { num /= pow; }; return num == pow; } if(n & (n-1))==(n-1) return true else return false The simplest answer would be: (number & 1) == 1. The last bit should be 1. Sorry. That answer is for checking odd or even. Not power of 2 + 1. The interview candidate's answer does not account for (2^0) + 1. It would return false for that. Another option. Assuming Int x contains the value: boolean correctForm(int x) { x--; String binString = Integer.toBinaryString(x); if (binString.charAt(0) == '0') { return false; } for (int i = 1; i < binString.length(); i++) { if (binString.charAt(i) != '0') { return false; } } return true; } (number - 2) in binary must be all 1s because 2^n-1 is its binary form must match regexp $0*10*1^ public class isPowerOf2 { public boolean isPower(int number){ if(number <=0){ return false; } number = number -1; if((number & -number) == number) return true; else return false; } boolean isPower(int num){ num--; Boolean foundOne = false; for(int i = 1; i < sizeof(int); i++){ if((1<<i)&num == (1<<i) if(foundOne) Return false; else foundOne = true; } return true; } A power of two should only have one 1 in it's bit string Show More Responses What about subtracting 1 from the number and doing a log base 2? If that is an I tiger, then return true, otherwise return false. n = log(N-1)/log2 if (n%1 ==0) return true Using log is the best way to go Actually every existing number is if the form 2 power n plus one right? Except zero and one that is |

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

Implement a function to validate whether a given binary tree is a BST (i.e. write an isBST() function). 9 AnswersI came up with a recursive solution something like this: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if (node != null) { if (node.left != null && node.left > max || node.right != null && node.right < min) { return false; } else { return (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)); } } else { return false; } } How come this function never returns true? And why would you need min and max? Ok, so I should have spent a little more time posting this (I was admittedly rushing through it so I could get access to more questions/answers). Here's a revised version that should hopefully make more sense: boolean isBST(TreeNode node, int min = INT_MIN, int max = INT_MAX) { if(node == null) { return true; } if(node.value > min && node.value < max && IsValidBST(node.left, min, node.value) && IsValidBST(node.right, node.value, max)) { return true; } else { return false; } } The main change is that I decided to avoid checking the children of the tree in the body, and leave it to recursion to take care of that. Thus, we just have to look at the current "node" and that's it... the constraints will be handled by passing min and max down. @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. Finally, the min and max values are required because a BST requires that each value in the left branch be smaller than ALL parent values on that branch (and similarly for those on the right branch being larger). Another way of saying this is that the entire left tree of any node must be smaller than the node's value, and the entire right tree must be larger than the node's value. Thus, in a recursive solution, you have to have a way to pass down the upper and lower bounds to the lower levels of the tree, otherwise the third level won't be able to check whether it's smaller/larger than the root two levels up. That's why we pass down the min and max values. Hope this helps. Show More Responses boolean isBST(TreeNode node) { if(node.isLeafNode( )) return true; else { if(node.value node.rightChild) return false; else return (isBST(node.leftChild) && isBST(node.rightChild)) } } traverse in order and see if they r same @Alexander - in response to your questions, the original function does in fact return true, if the condition (isBST(node.left, min, node.value) && isBST(node.right, node.value, max)) happens to evaluate to true. ============= Those are just two function calls and the function never returns true. Alexander is right - you are missing a terminating clause in your recursion. Forgot to add - your second solution is correct since it returns true. // For +ve number OR use INT_MIN instead of -1(s) bool BinarySearchTree::validate() { int minVal = -1; int maxVal = -1; return ValidateImpl(root, minVal, maxVal); } bool BinarySearchTree::ValidateImpl(Node *currRoot, int &minVal, int &maxVal) { int leftMin = -1; int leftMax = -1; int rightMin = -1; int rightMax = -1; if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value value) { if (!ValidateImpl(currRoot->left, leftMin, leftMax)) return false; if (leftMax != currRoot->left->value && currRoot->value value; } if (currRoot->right) { if (currRoot->right->value > currRoot->value) { if(!ValidateImpl(currRoot->right, rightMin, rightMax)) return false; if (rightMin != currRoot->right->value && currRoot->value > rightMin) return false; } else return false; } else { rightMin = rightMax = currRoot->value; } minVal = leftMin rightMax ? leftMax : rightMax; return true; } // using inorder traverse based Impl bool BinarySearchTree::validate() { int val = -1; return ValidateImpl(root, val); } // inorder traverse based Impl bool BinarySearchTree::ValidateImpl(Node *currRoot, int &val) { if (currRoot == NULL) return true; if (currRoot->left) { if (currRoot->left->value > currRoot->value) return false; if(!ValidateImpl(currRoot->left, val)) return false; } if (val > currRoot->value) return false; val = currRoot->value; if (currRoot->right) { if (currRoot->right->value value) return false; if(!ValidateImpl(currRoot->right, val)) return false; } return true; } |

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

Given a string find the first non-repeated character. 10 AnswersHint: use a hash table public static char getFirstNonRepeatedChar(String s) { List charList = null; char nonRepeatedChar ='?'; if (s != null) { s = s.trim(); charList = new ArrayList(); for (int i=0; i<s.length(); i++) { Character c = s.charAt(i); if (!charList.contains(c)) { charList.add(c); } else { charList.remove(c); } } } if (charList != null && !charList.isEmpty()) { nonRepeatedChar = charList.get(0); } return nonRepeatedChar; } @Rajiv : Your solution is completely wrong. It will fail for input of "aaa" Reason: on first check, you insert "a". On next check you remove it. On next check you again insert it and return that as your answer, even though it was repeated thrice. Show More Responses hash of non repeating characters tied to a double linked list, remove any repeating character from the hash and the list. at the end the head of the list is the answer. you can use the same hash to keep the counters. public static String findFirstNonRepeatedCharacter(String S) { int[] T = new int[256]; for (int i = 0; i < S.length(); i++) { char next = S.charAt(i); T[next] = T[next] + 1; } for (int i = 0; i < S.length(); i++) { if(T[S.charAt(i)] == 1) return String.valueOf(S.charAt(i)); } return null; } Three ways to find first non repeating character in a string c# find the code below - public char firstNonRepetitive(string inputString) { int nextOccurrence = 0; char firstDistinctChar = ' '; for (int i = 0; i < inputString.Length; i++) { nextOccurrence = 0; for (int j = (i + 1); j < inputString.Length; j++) { if (inputString[i] == inputString[j]) nextOccurrence++; } if (nextOccurrence == 0) { firstDistinctChar = inputString[i]; break; } } return firstDistinctChar; } Check out amazing two more way - program to find first non repeating character in a string c# - three ways http://www.dotnetbull.com/2013/08/find-first-non-repeating-character-string.html program to find first non repeating character in a string c# - three ways My python implementation: def firstNonRepeatingCharacter(inputString): hashmap = {} for x in inputString: if (x in hashmap): hashmap[x] = hashmap[x] + 1 else: hashmap[x] = 1 for x in inputString: if (hashmap[x] > 1): continue else: return x return "No nonrepeating character found" for (int index = 0; index < str.Length; index++) { if (str.LastIndexOf(str[index]) == str.IndexOf(str[index])) { return str[index].ToString(); } } I will have one variable x to store the first non repeating character, variable y as a backup And a set of characters already encountered. I will start from position n to position 0 where n is the lenght of the string. If char(n) is not present in the set, then check if x=char(n), if yes, x = y. If no, y=x and x=char(n). The idea is to keep updating the newest character that has not been repeated and also keeping the second newest character as a backup. In the end return x. |

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

given an array of numbers to remove the duplicates 11 AnswersI'm not sure. Maybe use merge sort and throw away duplicate values. Sort the array in place. Then iterate and you can easily find duplicates by comparing the current and previous values. Sort is n log n; iterate is n. Total is n log n. That is the answer that I gave. The interviewer than asked "how do you delete the duplicates from the array." I couldn't figure out that part. Show More Responses The simplest way is to use a set (no duplicate keys, and, if values are used as keys, no duplicate values). This way you simply need to iterate over the entire array and add each key/value into the set (it ignores adding it if it's a duplicate). Matt, Can't use more memory. 1) Sort this array by using quicksort, so the time will be O(nlogn), 2) Start p1 pointer at beginning, and p2 at last and start move p1++ 3) if found p1 == previous p1, sway p2 and previous p1, and move p2--, the idea is trying to move all duplication to the end of arrary, 4) keep doing 3) till p1 = p2, 5) so we have a clear array without dup, then use quicksort again from index 0 - p1 if you want to remove duplicate element in the array, try this algo: num = 0; for (i =0; i < arr.length()-1; i++) { if (arr[i] < arr[i+1]) { arr[num++] = arr[1]; } } arr[num] = arr[n-1]; http://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array in C# 3.5+ , you can use LINQ query //given array arr arr.Distinct().ToArray(); removes duplicates Convert array to a set. If thats not an option, consider, counting sort if range known else merge sort as mentioned by some one earlier How about using HashTable or Dictionary to store the array values as keys. We can use ContainsKey method to skip over duplicates. Once the array elements are copied into the dictionary, we can convert the dictionary keys into an array to get a non-duplicated version of the original array This is constant space, but linear time. However this method will not keep the original order of the elements. |

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

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

Determine whether the binary representation of a number if a palindrome or not, code it on a white board. 13 AnswersThis was the first question I was asked and is considered a warm up. public static boolean isPalindrome(int someInt) { final int WIDTH = 8; boolean isPalindrome = true; for (int i = 0; i < WIDTH && isPalindrome == true; i++) { int maskLower = (int) Math.pow(2, i); int maskUpper = (int) Math.pow(2, WIDTH - (i+1)); boolean bitLowerOn = ((maskLower & someInt) == maskLower) ? true : false; boolean bitUpperOn = ((maskUpper & someInt) == maskUpper) ? true : false; isPalindrome = bitLowerOn && bitUpperOn && isPalindrome || !bitLowerOn && !bitUpperOn; } return isPalindrome; } anon.. would this work for a number like 17 (10001)? Show More Responses bool checkPalindrome(unsigned int n) { int m = n, k =0; bool ret = false; while(m!=0) { int i = 1; i = i & m; k = k > 1; } if((k^n)==0) { cout<<"Palindrome"<<endl; ret = true; } else { cout<<"Not Palindrome"<<endl; } return ret; } I have a simple solution. Reverse the bits one by one and test equality of the two resulting numbers. (Matlab code) function [r] = isPalindrome(a) n = a; m = 0; while(n>0) m = bitshift(m, 1); m = m + mod(n, 2); n = bitshift(n, -1); end r = (m==a); end public static boolean isPalindrome(int n) { int nb = 0, nl=n; while(nl>0) { nb=(nb>1; } return nb==n; } @john/catalin4ever, i think it'll fail because it doesn't concat the 0s. For example: if the input is 0110, then after execution "nb" becomes to 0011. this is because of the condition: while(nl>0) Ask interviewer if they want the MSB that is a 1 to dictate the bit range to check, have it given as a parameter, or assume sizeof(T)*8 perhaps. Little details and extras like this can make a difference to them. public static bool CheckPalindrome(uint n) { return CheckPalindrome(n, 0); } unsafe public static bool CheckPalindrome(uint n, int bits) { if (bits == 0) { // Determine bits to check as the MSB having a 1 uint temp = n; while (temp != 0) { ++bits; temp >>= 1; } } uint m1 = (uint)1 > 1; i > 0; --i) { if (((n & m1) != 0) ^ ((n & m2) != 0)) { return false; } m1 >>= 1; m2 <<= 1; } return true; } Examples: BitOps.CheckPalindrome(17, 0) is true BitOps.CheckPalindrome(17, 8) is false BitOps.CheckPalindrome(0xABD5, 0) is true BitOps.CheckPalindrome(0xABD5, 16) is true BitOps.CheckPalindrome(0x5BDA, 0) is false BitOps.CheckPalindrome(0x5BDA, 16) is true string binary; int start=0, int end= binary.length -1; while(start < end) { if (binary[start] == binary[end]) { start ++; end- -; } else return false; } return true; int isPalindrome( int num ) { int x = num & num; return ( x == num ) ? 1 : 0; } /* function declaration goes here.*/ int isPalin(int orig); int main() { int x = 9; int i = isPalin(x); printf("i = %d \n", i); } int isPalin(int orig) { int copy = orig; static int reversed = 0; while(copy!=0) { reversed >= 1; } return (reversed == orig); We can compare the leftmost and rightmost bits by left shifting and right shifting the bits and also by getting rid of those bits . If the binary number is a palindrome, the left and right bits should be equal. Here is a C# implementation of the above logic static bool IsBinaryPalindrome(byte num) { int i = 0; while (true) { i++; bool right = false, left = false; byte origNo = num; if (((num > i) != origNo) { left = true; //left most bit contains one } num >>= i; //putting the right bit back in its original position origNo = num; if (((num >>= i) << i) != origNo) { right = true; // right most bit contains one } num <<= i; //putting the left bit back in its original position if (left != right) { return false; } if (num == 0 || num == 1) break; } return true; } python one-line need to replace the the 0b >>> str(bin(255).replace('0b',''))==str(bin(255).replace('0b',''))[::-1] True |

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

**21**–

**30**of

**7,513**Interview Questions