# Interview Questions

interview questions shared by candidates

## Interview Questions

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

Find the deepest common ancestor of two nodes in a tree structure. 13 AnswersThis interview was frustrating because it felt like the woman couldn't write code in C++. I first asked whether I could assume a standard Tree node structure (as I've built several custom structures and they all have many of the same basic components) and she was pretty much dumbstruck and told me ti write the implementation for one. So i did. Then I started walking through my solution and practically had to spell the word iterator when I said I declared one. My solution was basically to just descend in the tree toward the first value until the two values are on different sides of the current node or you fall out the bottom of the tree. I had to repeat the conditional statements character by character for the interviewer. Isn't the root node always the "deepest" common ancestor? Either the question is worded wrong, or you answered it incorrectly, but I think it's most likely that it's worded wrong. @mliu the question is correct. u r thinking wrong. depth of a tree grows towards its leaves. root is the least deep node in a tree. Show More Responses @nunnu is right here what the question wanted was the common ancestor furthest from the root. Again, I'm pretty sure (by subsequent conversations with friends) that my answer was right but that the interviewer and I just couldn't communicate struct node { int value; struct node *right; struct node *left; }mynode; mynode *closestAncestor(mynode* root, mynode* p, mynode* q) { mynode *l, *r, *tmp; if(root == NULL) { return(NULL); } if(root->left==p || root->right==p || root->left==q || root->right==q) { return(root); } else { l = closestAncestor(root->left, p, q); r = closestAncestor(root->right, p, q); if(l!=NULL && r!=NULL) { return(root); } else { tmp = (l!=NULL) ? l : r; return(tmp); } } } Smiles, my ancestors don't sit in trees. - Do yours? We have grown used to sitting under them and have great picnics... Suppose we need to find common ancestor for the nodes with values A an B. start from the root and compare value of the root node with both A and B. If A an B are both below/above the node's value then go down to the next node. Repeat until we find a node where A and B "go" to different links. This node seems to be 'common ancestor'. Traverse up the tree for both the nodes and add them to the explored list. If there is a common element in the explored list of both the nodes, that's the common ancestor. Hari, if the answer was the root your approach would have n^2*lg(n) complexity where mine had lg(n) in the worst case solution with O(h) time and memory complexity (h - height of the tree) Node * dca(const Node * a, const Node * b) { stack qa, qb; while (a) { qa.push(a); a = a->p; } while (b) { qb.push(b); b = b->p; } Node * result = NULL; while (qa.top() == qb.top()) { result = qa.top(); qa.pop(); qb.pop(); } return result; } To find the common ancestor. O(lg N) public Node GetCommonParent(Node root, int key1, int key2) { while (root != null) { int key = root.iData; if (key key1 && key > key2) root = root.LeftChild; else return root; } return null; } @Joarder: your answer is both really bad coding practice and only works for very specifically-structured trees (binary search trees based in integer keys). The approach is a good one, but you should not override a parameter being passed in and you should use Node.isLeft(Node) and Node.isRight(Node) rather than comparing keys directly. Remember that a tree can be made from a collection of any comparable object, keys are not required. Why was the first answer down voted? I think thats the best answer.. There is no better way.. And its O(log n) complexity. |

Number of 1's in binary representation of integer? 12 AnswersRun a loop, in which you binary-AND the integer with 1, and increment a counter, if the result is 1. Then right-shift the input-integer by 1 bit, and start over in the loop unsigned int ones(unsigned int number) { unsigned int n; for (n = 0; number != 0; number >> 1) { if (number & 1) { n++; } } return n; } Show More Responses i dnt knw wheather it correct or not.....do correct me if im wrng a=0 q=n/2 r=n%2 n=q if(r=1)then a=a++ continue.... ct = 0; while (val) { ct++; val = val & (val - 1); } Several of the above work, but use preincrement public static int population(int x) { x = (x & 0x55555555) + ((x >> 1) & 0x55555555); x = (x & 0x33333333) + ((x >> 2) & 0x33333333); x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F); x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF); x = (x & 0x0000FFFF) + ((x >>16) & 0x0000FFFF); return x; } in C++, how about: do { sum += n&1; } while (n>>=1); int ones( ) { int n; int number = 1100110111; n = 0; while (number!=0) { int temp = number % 10; if(temp ==1 ) n++; number = number/10; } return n; } Lets consider 14(1110) is the number int CountOnes(int Number) { int n=0; while(number !=0) { if(number%2==1) n++; number >> 1; } return n; } The function takes an int and returns the number of Ones in binary representation public static int findOnes(int number) { if(number < 2) { if(number == 1) { count ++; } else { return 0; } } value = number % 2; if(number != 1 && value == 1) count ++; number /= 2; findOnes(number); return count; } All the answers above will not get you to amazon... try code the function with o(m), where m is the number of 1's in the binary representation of an integer. (hint: look up "Programming Interviews Exposed") |

Most of them were expected. Almost all are problem solving questions. 1. Given a BST with following property find the LCA of two given nodes. Property : All children has information about their parents but the parents do not have information about their children nodes. Constraint - no additional space can be used 15 AnswersHint - detect the level at which the given nodes are present. Then travel upwards from that position. How about traversing from one node to root, adding each node to hashset, Then try do the same with second one, on collision return node. No, you cannot do that since you need extra space for hashset which is not allowed, I am going to post my solution in a min Show More Responses function findLCA(Node node1, Node node2) { int counter1 = 0; int counter2 = 0; Node temp; //Find the level for each node, use a temp node to //traverse so that we don't lose the info for node 1 and node 2 temp = node1; while( temp.parent ! = null) { temp = temp.parent; counter1++; } temp = node2; while( node2.parent ! = null) { node2 = node2.parent; counter2++; } /* * We wanna make them at the same level first */ if(counter1 > counter2) { while(counter1 != counter2) { node1 = node1.parent; counter1--; } } else { while(counter2 != counter1) { node2 = node2.parent; counter2--; } } while (node1.parent != node2.parent) { node1 = node1.parent; node2 = node2.parent; } System.out.println("Found the LCA: " + node1.parent.info); } //correction temp = node2; while( temp.parent ! = null) { temp = temp.parent; counter2++; } @chmielsen : your solution would work... but as said by Hamid, due to the constraint of space, you have to consider some other technique. I seems really like the question of finding intersection of two linked lists 1)consider node1 as p1. see if p1=p2 , p1->parent=p2, p2->parent=p1 2)now for a value p1 try to see recursively if p2->parent ever becomes equal to p1 or p2=root 3)set p1=p1->parent and continue till p1=p2 or p1= root temp1 = node1; temp2 = node2; while( temp1.parent != null && temp2.parent != null){ if(temp1.value == temp2.value){ return temp1; // temp1 and temp2 point to same node so pick one } temp1 = temp1.parent; temp2 = temp2.parent; } System.out.println("no such ancestor"); Consider this is a BST, where max node is always on the right of min node, we can traverse max upward one node at a time while comparing min nodes as it traverse upward toward root. BinaryNode findBSTLCA( BinaryNode min, BinaryNode max ) { BinaryNode tempMax = max; BinaryNode tempMin = min; while( tempMax != null ) { while( tempMin != null ) { if( tempMin.element == tempMax.element ) return tempMin; tempMin = tempMin.parent; } tempMin = min; // reset tempMin tempMax = tempMax.parent; // traverse tempMax upward 1 node } return null; // no LCA found } Consider that the lowest common ancestor in a binary search tree means the node value would be between the two values passed in. Because everything left is less than and everything right is greater than, we can traverse the tree using this knowledge. Here's the solution in PHP for something different: function findLowestCommonAncestor(Node $root, $value1, $value2) { while ($root != null) { $value = $root->getValue(); if ($value > $value1 && $value > $value2) { $root = $root->getLeft(); } else if ($value getRight(); } else { return $root; } } return null; //the tree is empty } howardkhl - your solution works, but this is O(n^2) complexity, making it too slow for large enough trees. Ja - your solution might work (haven't thoroughly checked it) but it violates the restriction that a parent node does not know about the child node. So this answer is invalid. The correct answer is the one given by Hamid Dadkhah, which, just like an anonymous responsder said, is the same problem as an intersecting list. you can use the following method *Node getLCA(Node *n1, Node* n2){ while(n1.parent!=null){ Node * p= n2; while(p.parent!=null){ if(n1.parent!=p.parent) p=p.parent; else return p.parent; } } } Show More Responses Pick one of the nodes in random. Keep traversing up until the property: new node is greater than one of the nodes and lesser than the other is satisfied. I was also interviewed with same question. They not only ask the solution they also ask for the time complexity of the solution. Make sure you to ask different questions and confirm the type of tree. They could give you binary search tree, binary tree, sorted binary tree. Solution will greatly depend on the type of the tree. |

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

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 |

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