# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

Write a method to decide if the given binary tree is a binary search tree or not. 4 Answersfor binary search tree, inorder traversal should result in sorted array in the increasing order. Further, know that the difference between the two is that a binary search tree cannot contain duplicate entries. recur down the tree - check if element is already in hashtable - - if it is, return false - - if it isnt, insert element into the hashtable - - - recur to children I'm sorry but Anon's answer is not correct, at least according to "Introduction to Algorithms, 3d Edition" by Cormen. The binary search tree property says that there CAN be duplicates: "Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key = x.key." In other words, the value of a child node may be equal to the value of a parent node, which would yield the result that "Interview Candidate" posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes. Show More Responses public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER) { if (root == null) // children of leaf nodes { return true; } return root.data >= INTERGER_MIN && root.data <= INTEGER_MAX && isValidBST(root.left, INTEGER_MIN, root.data) && isValidBST(root.right, root.data, INTEGER_MAX) } |

In a given sorted array of integers remove all the duplicates. 8 AnswersIterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N The array is already sorted, no need for a set. example: 2,2,5,7,7,8,9 Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n) public RemoveDuplicates() { int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 }; int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ; for (i = 1; i <= ip.Length - 1; i++) { if (ip[i - 1] != ip[i]) { op[j] = ip[i - 1]; j++; } } if (ip[ip.Length - 1] != ip[ip.Length - 2]) op[j] = ip[ip.Length - 1]; int xxx = 0; } Show More Responses def removeDuplicatesSecondApproach(inputArray): prev = 0 noRepeatIndex = 0 counter = 0 for curr in range(1,len(inputArray)): if (inputArray[curr] == inputArray[prev]): counter = counter + 1 prev = curr else: inputArray[noRepeatIndex+1] = inputArray[curr] noRepeatIndex = noRepeatIndex + 1 prev = curr inputArray = inputArray[:-counter] return inputArray if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } Apologies for the previous incomplete answer int[] inpArr = {1,2,2,3,4,5,5,5,8,8,8,9,13,14,15,18,20,20}; int[] opArr = new int[inpArr.length]; int opPos = 0; for(int i= 0; i<=inpArr.length - 1; i++) { if(inpArr[i] == inpArr[i+1]) { int repeats = 1; opArr[opPos] = inpArr[i]; int j = i + 1; while(j+1 <= inpArr.length - 1 && inpArr[i] == inpArr[j+1]) { j++; repeats++; } opArr = Arrays.copyOf(opArr, opArr.length - repeats); i = i + repeats; } else { opArr[opPos] = inpArr[i]; } opPos++; } for(int i =0; i<=opArr.length-1;i++) { System.out.println(opArr[i] + ","); } public static void removedup(int[] input){ int count =1; int i=0; for( ;i public static void removedup(int[] input){ int count =1; int i=0; for( ;i |

how can a particular application be tested apart from testing its functionality 3 AnswersReliability Test, Stability Test, UI Test, Platform Test, Also include, performance, stress & load testing Accessibility, user experience, globalization, localization, integration, compatibility |

Write code in your favorite programming language that will accept two strings and return true if they are anagrams. 2 AnswersThis was not really that hard to write it, however the interviewer asked me to reduce the complexity. My initial version had n*log(n) complexity and he asked me to reduce it to no more than n complexity. If you have had some upper level Computer Science classes this is not too difficult, however what they are looking for is a way to stump you. If you adjust your code or thinking rapidly to their request they will change it again until they find something that you have trouble with. Do not be discouraged by this, it is the interviewers job to determine how much you know! Found this good link. Time complexity is O(n). http://www.dreamincode.net/code/snippet1481.htm The algorithm can still be improved but gives some basic idea on how to implement. |

Lots of questions about arrays, lists and hashmaps 1 AnswerFocus more on how hashmap works and its applications |

Given a string (understood to be a sentence), reverse the order of the words. "Hello world" becomes "world Hello" 2 Answers2 ways. At the low level: reverse the entire string. 'Hello World' becomes "dlroW olleH". Then reverse each word, becomes "World Hello". At a higher level: Tokenize the words and push them onto a stack, then pop them out. class Solution { public static void main(String[] args) { String input = "Hello World this is a string"; reversestring(input); } public static void reversestring(String input){ // Stack stack = new Stack(); String[] str = input.split(" "); for(int i = str.length-1;i>=0;i--) { System.out.print(" "+str[i]); } } } |

Write an algorithm to determine if 2 linked lists intersect 15 AnswersThe first answer is simply looping through every item in list one checking it against all items in list 2 until you find a match. This is O(n2) and you'll be asked to improve it. Think about other data structures with faster access to improve this algorithm. ^ Use a HashMap? We could traverse and put every node we see in a hashmap @PixelPerfect3 Yes, a hashtable would do the job. Just put every node from one of the lists into a hashtable then traverse the other list checking to see if each node exists in the hashmap. This would then be in O(n) time with the downside of using more memory for the hashtable. Show More Responses I don't understand why we would need extra space for this problem. If two linked list intersects, that means their end are the same. Traverse until the end of both list and check if the address of the last nodes are the same. @Anonymous - you are right. All we need to do is check if the ends are the same. My solution would be useful if we want to find the node they intersect at. @PixelPerfect3 & @Anon - Sorry guys, that's not correct. It's not that the end of the lists are the same - intersecting means if any nodes within the linked list are the same. For example: List 1 = 1 -> 3 -> 5 -> 6 -> 7 -> 9 List 2 = 2 -> 4 -> 6 -> 8 -> 10 In this case, the 4th element of list 1 and the 3rd element of list 2 are "intesecting". Notice how the ends are different yet still they intersect. The extra space used by the hashtable is made up for by the speed of lookup O(1) in the hashtable. If space is an issue and speed not, you'd go for the O(n2) solution which is to traverse through List 1 and for every node check it against all the nodes in List 2. @Ja, would it be more clear to describe this question as "Check two LinkedLists, to see if they have one node sharing the same value." ? @Ron Perhaps, yes. But take a look online for other people who have been asked this question from Amazon/Microsoft/Google. They tend to ask for "intersecting" linked lists, which means the lists share one or more of the same node. In my simple case above it might look as if it's just the value of each node in the list but I think technically intersecting means they share the same node, i.e. the object. My example was just for illustration but if you were writing this for real you'd want to check the node->next pointer to see if it's the same object in both lists. @Ja, Your example doesn't really make sense: how can the node with value 6 point to a node with value 7 AND a node with value 8? It can only point to one node: either 7 or 8. That's why I think Anonymous' answer is correct. @PixelPerfect3 - It's not the nodes value that's important but the actual node itself, i.e. the value of the next pointer will be the same for a node in both lists. Simply saying "the last node in the list will be the same" is incorrect! Linked lists can intersect at any point in the lists and not share the same last node. Actually, you know I think you guys are right after some thought! My only concern was to find the actual node they intersect at but PixelPerfect3 had a point - being that a singly linked list only points to one next node, if at any point they intersect then they must have the same node at the end of the list. Sorry for adding to the confusion. If you wish to know exactly where they intersect then my solution posted above will work but if you just need to know if they intersect, PixelPerfect3 and Anon solution of the same end element is correct. 1) len1=find length of linkedlist1 2) len2 =find length of linkedlist2. 3) move the bigger linked list to (len1-len2) position. 4) rightnow both linked lists are equal at distance from last node. that is they are n node away last node. 5) iterate both LL simulatenously and if they have same instance that is their intersection point. I think all of you guys missed one important problem. What if the linked lists have cycles? I believe this is one of the important points the interviewer want you to think about. Show More Responses Assumption that if one node intersects, all nodes from there till the end intersect is wrong. For example, my node definition is: typedef struct NODE { int value; NODE *ptr1; NODE *ptr2; } LISTNODE; If I use ptr1 only for first list and ptr2 only for second list; then I could have an intersection at the middle element but not in the end. Its a different question why one would want to design a node the way I mentioned above; but the assumption is wrong. Common answers: a) If lists aren't cyclic; use a visited flag in the NODE definition and traverse first list and mark all nodes visited. Then traverse second and read the flag. b) Use a hash-map with address as the key. Insert into hash-map while traversing first list. Check the hashmap while traversing second. c) If the list could have cycles, still b) and a) would work with any modifications. Thats a double linked list. Not a linked list. |

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

The Game of Nim worded diffently. 11 AnswersThe Name of the Game. The anwer is 'Take' from the german word nimm. There is a game called 'The Game of Nim' that has a specific mathematical equation that must be utilized in order to win the game. Nimm is the German word for Take, so you must figure out the best way to take the matches without your opponent beating you at it. Show More Responses The Game of Nim is a simple board game in which you and your opponent take turns removing a number of matches from one of the rows (normally about 5 rows) of matches on the board. The person to take the last match off the board is the winner. The reason why it is of interest to us as prospective software engineers (and why you probably asked this question) is that it has some interesting binary number properties making it fairly trivial to write computer code to ensure a win every time (every time there is a starting advantage, that is). Would you like me to go into more detail? Ok, well in brief then, basically the trick is to take the number of matches in each row and represent this as a binary number. Then, either by hand or with a program, do an Exclusive Or operation on the numbers. Then whenever you take some matches, just ensure that the remaining total is always zero after your turn and you will be sure to win by the end of the game. Maybe I should also add (and I'm thinking out the box here), that sometimes we as people are up against a challenge or opponent where succeeding or beating them is seemingly reliant on chance or luck. However, with careful analysis of the problem and good strategising, it turns out it is actually possible to ensure success just about every time. On the other hand, there are times when the odds are against us from the start. Then either we must stand up for what we believe is fair (i.e. be aware and vocalise that we cannot possibly win), or else acknowledge that our opponent is worthy and will ultimately get the better of us. Yet it should be noted that we can still stay strong and be competitive from the beginning allowing us to possibly take advantage of any mistakes or weaknesses our opponents or challenges might display. That is the Game of Nim worded differently. What does this question have to do with Quality? Nim's Game If I was interviewing you and asked you that question, I would be trying to determine if you could take a simple problem and provide a simple solution. If you went off into the weeds like Andrew_Bryce did, I would be wondering how effective you would be solving tons of simple issues. Also, if you answered the wrong question (what is the Game of Nim?) and not the question I asked (how would you word differently the phrase The Game of Nim?), I would be wondering how good your communication skills were. If I were being interviewed, I would wonder about the interviewer's communication skills. "The game of Nim worded differently" isn't a question. It isn't even a sentence. "Foaming Theme" 1) I cheated 2) I didn't even know what Nim was before I looked it up Here's how I would interpret some answers and the job I would recommend for them Anonymous: Huh? I think you're trying to be a smartass, but I don't get it - Cafeteria Worker Ryan: Knowledgeable - Content provider SelenityHyperion: Knowledgeable, informative and relatively succinct - Writer Andrew_Bryce: Detail oriented and a perfectionist - Software tester, some forms of coder Astrochimp: Focused - Project Manager OneEye: Thinks his answer is the only correct one - Clearly VP material Count Negroni: Nit Picker - Editor I don't think there's supposed to be one correct answer Ha ha, jokes on me. "The Game of Nim worded differently." is not the actual question, just a vague description. I would answer: "Are you talking to me?" Because it sure sounds like you're high. Then I'd get up and leave. Strategic domination |

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

**1**–

**10**of

**4,103**Interview Questions

## See Interview Questions for Similar Jobs

- Medical Assistant
- Cashier
- Hospitality
- Accountant
- Account Executive
- Truck Driver
- Receptionist
- Human Resource
- Sales Associate
- Healthcare
- Engineering
- Social Worker