# Software Development Engineer Interview Questions

Software development engineer interview questions shared by candidates

## Top Interview Questions

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

Number of 1's in binary representation of integer? 13 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; } 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") int num = 31; int mask = 1; int counter = 0; while (num > mask ) { if ((num & mask) == mask) { counter++; } mask = mask << 1; } Console.Write(counter); Console.ReadKey(); |

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

Given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. What's the O notation for what you just wrote? Can you make it faster? Can you find an O(n) solution? Implement the O(n) solution 17 AnswersO(n^2) solution is just two double for loops. O(n log n) solution will use a binary tree O(n) solution will use a hash table O(n) solution possibility (no need for a data structure) void findpairs(int sum) { //given a set of numbers -50 to 50, find all pairs that add up to a certain sum that is passed in. if (sum == 0) { cout 0) { for(int i = 0; i((sum/2)-1) && i>-26; i--) { if( (i - sum+i) == sum) { cout << i << " " << sum+i << "\n"; } } } } @Mike "if( (i + sum-i) == sum)" will always give you "sum". Show More Responses @Mike: if (sum == 0) does not imply 0,0. It implies -50,50; -49,49; -48,48,... Has anyone found the O(n) solution??? I'm having trouble with this one... Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n). Now, foreach key 'k', with value 'v': if k == v: there is a match and that is your pair. this will take another O(n) pass totale O(2n) ~ O(n) Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like -50 + 50 -49 + 49 -48 + 48 etc.... etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2). Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time. def pairs(k, minimum, maximum): if k >= 0: x = maximum y = k - maximum else: x = k + maximum y = minimum while x >= k / 2 and y <= k / 2: print str(x) + " , " + str(y) + " = " + str(x + y) x = x - 1 y = y + 1 here is my solution using hash table that runs in O(2n) => O(n): public static String findNums(int[] array, int sum){ String nums = "test"; Hashtable lookup = new Hashtable(); for(int i = 0; i < array.length; i++){ try{ lookup.put(array[i], i); } catch (NullPointerException e) { System.out.println("Unable to input data in Hashtable: " + e.getMessage()); } } int num2; int num1; for (int i = 0; i < array.length; i++){ num2 = sum - array[i]; Integer index = (Integer)lookup.get(num2); if ((lookup.containsKey(num2)) && (index != i)){ num1 = array[i]; nums = array[i] + ", and " + num2; return nums; } } //System.out.println(lookup.get(-51)); return "No numbers exist"; } The number you're looking for is T. You can just create an array of size 101. Then you loop through the array, and drop each number i in cell of index i-50. Now you do a second pass, and for each number, you look at the number at index T-i-50. If there's something there, you have a pair. typedef pair Pair; list l; //create an empty list of tuples pairofsum(l,10); // an example of how to call the function which adds to your list of tuples the possible pairs of the sum void pairofsum(list& l,int sum) { if(sum==0) { Pair p; loadPair(p,0,0); l.push_back(p); for(int i=1;i<51;i++) { loadPair(p,i, -i); l.push_back(p); } } else if (sum<0) { Pair p; for(int i=0;i+-sum<51;i++) { loadPair(p,i,-(i+-sum)); l.push_back(p); } for(int i=1;i<=-sum/2;i++) { loadPair(p,-i,sum+i); l.push_back(p); } } else { Pair p; for(int i=1;sum+i<51;i++) { loadPair(p,-i,sum+i); l.push_back(p); } for(int i=0;i<=sum/2;i++) { loadPair(p,i,sum-i); l.push_back(p); } } } void loadPair(Pair& p, int f, int s) { p.first=f; p.second=s; } Here is my C# implementation. It runs O(N) and doesn't include duplicate pairs (e.g. including [50,-50] as well as [-50,50]). static void FindPairs(int sum) { for (int i=-50; i=-50) { Console.WriteLine(i + " " + otherNum); } } } Solution with no duplicates: @Test public void findPairsTest() { // TestCases // Alternately you can put this test cases in dataprovdier findPairs(50); findPairs(20); findPairs(-20); findPairs(-50); findPairs(0); } private void findPairs(Integer sum) { HashMap inputPair = new HashMap(); HashMap outputPair = new HashMap(); for(int i=-50; i<=50; i++) { inputPair.put(i, sum-i); } // print pairs for(Integer key : inputPair.keySet()) { Integer potentialOtherNum = inputPair.get(key); if(inputPair.containsKey(potentialOtherNum) && potentialOtherNum < key) { outputPair.put(key, potentialOtherNum); } } System.out.println(outputPair.entrySet().toString()); } Here is the solution in O(n) time complexity. http://www.knowsh.com/Notes/NotesSearch/NotesDetail/140226/Program-To-Find-All-The-Pairs-In-The-Given-Set-That-Add-Up-To-A-Certain-Sum Please let me know if there is any thing I missed. Show More Responses Use two pointers, one at the begin, one at the end, let us call the pointer begin and end, the array is named nums. If nums[begin]+nums[end]>target, end--;if end Half=sum/2; i=1; While (half+i -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); } half=sum/2; i=1; While (half+i \ -51) { first = half-i; second = half+i; System.out.println(“” + first + “, “ + second); } Weirdly the less than and greater than signs make the text between them invisible. The conditional statement is supposed to say Half=sum/2; i=1; While (half+i LESSTHAN 51 && half-i GREATERTHAN -51) |

### 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"< 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 Development Engineer at Amazon was asked...

How would you find the pairs of numbers that added to some specific number in an array. 7 Answersi program in java..so i will talk from the arrayLists perspective. suppose we want to find out a+b = 123; for(int i=0; i2000 records.but below that, sorting and above operation is efficient. you must play with different possibilities. Your answer (using arrayList.indexOf(...)) is worse than sorting. Sorting is O(log n), finding an item in an unsorted array using ArrayList.indexOf is O(n). Given an unsorted array input (e.g. int[] input), sort it using Array.sort(input) ... this is O(log n). Start at input[0] of the sorted array and calculate it's complementary value. Go to the end of the array and iterate backwards until you find the complementary value or less. If it's less repeat for input[1] and iterate backwards from the previous last item ... keep going. This is at worst proportional to n/2, ie O(n). I realize I wasn't totally clear in my first paragraph ... searching for the complementary value of one item is O(n), but you have to the search for (at worst) every item, so your solution is O(n^2). Show More Responses Duh - sorting is O(nlog n) ... Using hashing, this can be done in O(N). store the n/2 mod i in the corresponding hash bucket. Now check the each hash bucket and you are done. sort the array (o(n(log(n)) and take two pointers at both the ends say p1 and p2 if p1+ p2 move the pointer p2 by 1 and add to check if (p1+p2) > n -> move the pointer p1 by 1 and add to check if (p1+p2) = n ->print the pair [traversal takes o(n)] finally thus can be done in o(n) I will not waste o(nlogn) in sorting the array. Instead assuming that the sum we looking for is k, i will divide the array into 2 arrays. First array will contain all values which are less than k/2 Second array will contain all values > k/2 This is bcoz in a sum if one number is less than k/2, the other has to be larger. I will iterate over the smaller array of the 2 since they would rarely be equal. For each x in array 1, i will find the k-x in array 2. Complexity will be O(n). |

Given an array of integer in which all numbers occur even times except for one number occurs odd times, find it. 10 Answersi) sort array (n or nlogn at the max). go through array and count #occurrences for each num. (memory: null, just 1 var) ii) if lots of memory then use hashing xor all elements keep on adding the elements,wherever the sum becomes odd that number is the odd one. Show More Responses "keep on adding the elements,wherever the sum becomes odd that number is the odd one." Fails on int array[] = {2, 2, 4, 3, 3} xor is the correct answer Can explain the XOR answer pl. thanks if you xor an number with it self you get 0 , if you xor a number with 0 you get the number it self, eg 2,2,4,3,3 2^2 = 0 0^4 = 4 4^3= 7 7^3 = 4 and the answer is 4, We can also use a Hashmap and the first time we get an element we put 1, the next time we get it we remove it from the map...In the end only the required answer will be in the map operating all each element xor Time complexity On Space complexity O1 operating all each element xor Time complexity On Space complexity O1 |

Given an integer set of numbers, print all the subsets. For some reason the interviewer asked to print the supersets, but what he means is subsets. 9 AnswersI could not answer this one question (1st question of 2nd phone interview), he did not give any hints, just waited till I struggled for 15 minutes and ended the interview. Did not get next call. void print_subsets(int numbers[], int num_of_numbers) { int pow_of_num = pow(2, num_of_numbers); int i; } #include #include using namespace std; void print_subsets(int numbers[], int num_of_numbers) { int pow_of_num = pow(2.0, num_of_numbers); int i; for (i = 1; i < pow_of_num; ++i) { int j = i; int digit = 0; while (j != 0) { if (j % 2) { cout << numbers[digit] << endl; } ++digit; j /= 2; // This can also be done by bitwise operation } cout << "===============" << endl; } } void print_subsets_test_drive() { int numbers[] = {1, 2, 3, 4, 5}; print_subsets(numbers, 5); } int main() { print_subsets_test_drive(); return 0; } Output: 1 =============== 2 =============== 1 2 =============== 3 =============== 1 3 =============== 2 3 =============== 1 2 3 =============== 4 =============== 1 4 =============== 2 4 =============== 1 2 4 =============== 3 4 =============== 1 3 4 =============== 2 3 4 =============== 1 2 3 4 =============== 5 =============== 1 5 =============== 2 5 =============== 1 2 5 =============== 3 5 =============== 1 3 5 =============== 2 3 5 =============== 1 2 3 5 =============== 4 5 =============== 1 4 5 =============== 2 4 5 =============== 1 2 4 5 =============== 3 4 5 =============== 1 3 4 5 =============== 2 3 4 5 =============== 1 2 3 4 5 =============== Show More Responses How about using recursive to solve the problem? There are two base cases: 1. if array.length = 1, then the subset is itself 2. if array.length = 2, then the subsets are 3, {element1}, {element2} and {element1, element2} For a array with length > 2, then the subsets are: {element1} subsets(subarray(element2, ..., elementN)) {element1, subsets(subarray(element2, ..., elementN ))} Thanks MGhost, trying to completely understand your solution took me some time but helped me clarify a bunch of stuff with sets and stuff. Thanks man. Can you please explain the logic? MGhost Nice Solution i like the recursion solution because the smaller results can be cached and reused Untested but I believe this will work: def printSubsets(narr): q = narr n = len(narr) for i = 0 to n: for j in q: print q[j], printSubsets(q[j:]) print front = q.popfront() q.pushback(front) narr = [ 7, 4, 11, 3, 2, 5 ] printSubsets(narr) |

**11**–

**20**of

**4,103**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Software Development Engineer
- Senior Software Engineer
- Software Developer
- Software Development Engineer I
- Software Engineer In Test
- QA Engineer
- Intern
- Software Development Engineer In Test (SDET)
- Quality Assurance Engineer
- Software Test Engineer
- Test Engineer
- Software QA Engineer
- Software Engineer Intern
- Software Development Engineer II
- Senior Software Development Engineer
- Software Engineering
- Java Developer
- Business Analyst