# Software Engineer II Interview Questions

Software engineer ii interview questions shared by candidates

## Top Interview Questions

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 |

Find k largest/smallest number in a series of numbers. What data-structures will you use? Code it on white board. 6 AnswersFor K smallest number in series you can use a max heap of size k. When you find a new number and it is smaller than root of heap, swap it with root and heapify. @Ajit: What're the initial values of the max heap? What happens to the first value that comes in? Use selection sort for 'max' ( or for 'min') If K > series.length/2 then reverse the criteria- like in stead of looking for 15th highest out of 20 element array - look for (20 -15 =) 5th lowest and so on.... Show More Responses I think there's a cool solution which involves doing a pivot operation (like quicksort) until you have the top/bottom k numbers sorted. It's possible that you can get the top k numbers in a single pass of the array if you happen to choose a good pivot, and in general takes very few passes to find the top k numbers. I coded it up in C a while back: http://privatepaste.com/1f1df9d8f0 You just call select with your list, the min index, max index, and top k numbers, respectively. It can be easily changed to find the min (just reverse the swap condition) @Jordan, I can no longer get at your privatepaste link, so if you see this post I am interested in answers to the following: - since partition sizes are inherently not controllable by your choice of pivot, how do you land on an exactly k-sized partition (or even a k-sized total of the leftmost/rightmost N partitions)? - how do you choose pivots reliably to perform this (if it isn't reliable, then it isn't always a good answer just like pathological inputs for quicksort without randomizing the pivot selecting) - do you still just sort the partition(s) once you reach a k-sized set? I assume they want them in-order. I would just use a heapsort that short-circuits once K elements have been popped from the internal sifting loop, which does minimal processing and returns them in-order (C# example): public void FindKLargest(T[] A, int k) { . Heapify(A); . int end = A.Length - 1; . int k_offset = Math.Max(Math.Min(k, end), 1); . int stop = end - k_offset; . while (end > stop) . { . // Save the root heap item as done . Swap(ref A[0], ref A[end]); . // Separate heap from saved item . end--; . // Re-sift the new root item . SiftDown(A, 0, end); . } . // the K largest entries are now in ascending order at the end of A } For those of you who think building a max/min heap is O(nlogn) since heapify is O(logn) and heap build is O(n), but you are incorrect. Building a binary heap is actually O(n) because heapify depends on the height of the node, hence becoming O(h). Find more here: https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/ |

How can you solve n^m efficiently only using +, -, *, /. 4 AnswersThis is one solution that doesn't deal with negative exponents exp(n, m) { if (m == 0) return 1 if (m == 1) return n exp = exp(n, m / 2) if ( isOdd(m) ) exp = exp * n return exp } int f(int n, int m) { if(m==0) return 1; if(m==1) return n; n=n*f(n,(m-1)); return n; } There is no need to solve it recursively. it is pretty simple int calculateExp(int n, int m) { exp = n for (i = 1; i <= m; i++) { exp = exp*n } return exp; } Show More Responses Disadvantage of recursion is the large amount of space on the stack for a large m in this case. |

How would you find a duplicate number in a very large unsorted array of ints. 4 AnswersfindDuplicates(int array[]) { int duplicates[] , index; for (int i=0; ii; j--) { if (array[i] == array[j]) { duplicates[index++] = array[i]; break; } } print duplicates; O(n^2) is the usual naive answer but there are properties that if true can reduce this to O(n) using bit ops: In general, if the given array range can also be generated where the duplicated number you are trying to find gets no special treatment and is included just like all the rest a single time, then you can get the answer this way: set total to 0 foreach (n in given array) xor all n into total foreach (n in generated range) xor all n into total total is your answer This works because all the non-duplicated single entries will cancel out via xor with their single entry from the generated set (since they are all paired) and the duplicated number will have an extra odd entry (since it will have 2 entries already from the given array + 1 from the generated set = 3 entries). And because of course xor is commutative; the order of the xor'ing doesn't matter: 6^6^5^5^4^4 = 0, as does 6^5^4^5^4^6 It is a variation of these problems: - find a missing number in an unsorted array - find an unduplicated number in an unsorted array of duplicates I should have added t the above: Ask the interviewer if the array of N has any special distribution. In particular, for the duplicate question here, ask if the array of N contains [0, N-2] or [1, N-1] values unsorted, in addition to one extra entry duplicated in that set duplicated. Show More Responses [Apologies for multiple posts, I don't see any way to edit a post once made ...] There is also a way to find 2 different numbers instead of just 1 resulting from any of the above variations. If you first do the above xor O(n), your answer is actually A^B since you cannot separate the 2 numbers ... yet. The trick here is to get A and B into different unsorted subarrays, with all the other pairings that self-cancel into either subarray with them (but still in pairs together). That is done by noticing that even though you have no idea what A and B are individually, you do know that since the total is A^B that any 1-bit in the total A^B means that bit is different between A and B. So divide up *all* the numbers based on each having a 0 or 1 in one of those different bits. pseudocode -get the A^B total via the xor O(n) algorithm previously posted -determine as pivot an Nth bit which is different between A and B (any 1-bit in the A^B total) -run through all the same numbers again, but this pass accumulate xor's into an even or odd total depending on the chosen bit - the final answer for A and B will be the 2 accumulated totals Complexity: 2 O(n) which is just O(n) |

How would you reverse a linked list in Java? 5 AnswersList.reverse() java.util.Collections.reverse(yourList); First answer is incorrect (no such method). 2nd answer is correct. I've seen this question before where the expected answer is to manipulate the list. Show More Responses public class LinkedListElement { private E _element; private LinkedListElement _next; public LinkedListElement(E element) { _element = element; _next = null; } public LinkedListElement(E element, LinkedListElement next) { _element = element; _next = next; } public E get() { return _element; } public LinkedListElement next() { return _next; } public void setNext(LinkedListElement next) { _next = next; } public static LinkedListElement reverse(LinkedListElement e) { if (e == null) { return null; } LinkedListElement current = e; LinkedListElement next = e.next(); e.setNext(null); while (next != null) { LinkedListElement forward = next.next(); next.setNext(e); e = next; next = forward; } return e; } } public void reverse(ReverseSinglyLinkedList singlyLinkedList){ if(singlyLinkedList.isEmpty()){ return; } Node currentNode = head; Node nextNode = head.nextNode; Node markNode; head.nextNode = null; while(nextNode!=null){ markNode = nextNode.nextNode; nextNode.nextNode = currentNode; currentNode = nextNode; nextNode = markNode; } head = currentNode; } |

You have two linked lists that merge at some node. The lists could be billions of nodes long. Find the node where the lists merge in the most optimal time while using a low amount of memory. 5 AnswersIf the lists have a length value, then you should be able to do this pretty simply. If two lists merge, then they have the same terminal node. That means that from the merge node to the end they have the same length. So if you subtract the smaller lists length from the larger you end up with a great starting point to begin searching. you then increment down the lists from that point on to find the node where both lists meet. Above answer is not correct. Its a list so you can only start from the begininning. If its a doubly linked list, yes, you can start at the end (and should), but you cannot start "mid-list". I can think of two ways: 1) traverse from both heads, get two length: long, short traverse again starting from Array1[long-short] and Array2[0], looking for the same pointer O(4n) time, O(1) space 2) use a hash table holds all seen pointers. traverse from both heads O(2n) time, O(n) space Show More Responses Step 1: if the linked lists are not empty, find the length of each linked list. Since they have a common end point, we will get length of common area of the linked lists too. Step 2: find the difference between the length of both list. Start traverse the biggest list till the difference in length between them, provided one of them is bigger than the other. Step 3: now they are at the same remaining length. Traverse both of the together till both are pointing to the same next node.That node is the common node which is the merging point. If there is no such point, then they are not merged. Suppose x nodes before merged node for List1, and y nodes before merged node for List 2, z shared nodes for two Lists. List1.Length = x + z List2.Length = y + z Traverse List1, List2 to get their lengths. List1.Length - List2.Length = x - y Starting traverse at same time from (x-y+1)th nodes of List1, and head of List2 (when x>=y) or Starting traverse at same time from (y-x+1)th nodes of List2, and head of List1 (when x<=y) till they point to the same node, that node is merged node. otherwise, no merged node |

post order traversal of a Binary Search Tree Follow up Create a BST from this post order traversed array and write test cases for this function 3 AnswersCreating a BST from the post order traversal output would involve adding the nodes in reverse order of the post order traversal output. For example, if the post order traversal output was 2,4,3,20. I would insert in the following order: 20, 3, 4, 2. Can anyone confirm if this is correct? package test; import java.util.ArrayList; import java.util.List; public class TreeTraversal { static List preOrder = new ArrayList(); static List inOrder = new ArrayList(); static List postOrder = new ArrayList(); static void traverseTree(Node root) { Node left = root.getLeftNode(); Node right = root.getRightNode(); if (null == left.getLeftNode() && null == left.getRightNode() && null == right.getLeftNode() && null == right.getRightNode()) { preOrder.add(root.getValue()); preOrder.add(left.getValue()); preOrder.add(right.getValue()); inOrder.add(left.getValue()); inOrder.add(root.getValue()); inOrder.add(right.getValue()); postOrder.add(left.getValue()); postOrder.add(right.getValue()); postOrder.add(root.getValue()); } else { preOrder.add(root.getValue()); traverseTree(left); inOrder.add(root.getValue()); traverseTree(right); postOrder.add(root.getValue()); } } public static void main(String[] args) { Node left = new Node(2, new Node(1), new Node(3)); Node right = new Node(6, new Node(5), new Node(7)); Node root = new Node(4, left, right, true); traverseTree(root); System.out.print("Pre Order Traversal ::"); System.out.println(preOrder); System.out.print("In Order Traversal ::"); System.out.println(inOrder); System.out.print("Post Order Traversal ::"); System.out.println(postOrder); } } package test; import java.util.ArrayList; import java.util.Arrays; import java.util.Iterator; import java.util.List; enum TraversalType { PREORDER, INORDER, POSTORDER; } public class ConstructTreeBack { static Node root = new Node(); static TraversalType traversalType; static void formSubTrees(List treeList) { List leftSubTree = new ArrayList(); List rightSubTree = new ArrayList(); Iterator it = treeList.iterator(); int rootNodeVal = root.getValue(); while (it.hasNext()) { int nodeVal = it.next(); if (rootNodeVal > nodeVal) { leftSubTree.add(nodeVal); } else if (rootNodeVal treeList) { Node node = new Node(); if (traversalType.equals(TraversalType.PREORDER)) { if (null != treeList.get(0)) { node.setValue(treeList.get(0)); } if (null != treeList.get(1)) { node.setLeftNode(new Node(treeList.get(1))); } if (null != treeList.get(2)) { node.setRightNode(new Node(treeList.get(2))); } } else if (traversalType.equals(TraversalType.INORDER)) { if (null != treeList.get(1)) { node.setValue(treeList.get(1)); } if (null != treeList.get(0)) { node.setLeftNode(new Node(treeList.get(0))); } if (null != treeList.get(2)) { node.setRightNode(new Node(treeList.get(2))); } } else if (traversalType.equals(TraversalType.POSTORDER)) { if (null != treeList.get(2)) { node.setValue(treeList.get(2)); } if (null != treeList.get(0)) { node.setLeftNode(new Node(treeList.get(0))); } if (null != treeList.get(1)) { node.setRightNode(new Node(treeList.get(1))); } } return node; } public static void main(String[] args) { int rootNodeVal = 0; List treeList; /*PRE ORDER TRAVERSAL*/ Integer treeArrPreOrder[] = { 4, 2, 1, 3, 6, 5, 7 }; rootNodeVal = treeArrPreOrder[0]; root.setValue(rootNodeVal); root.setRoot(true); treeList = Arrays.asList(treeArrPreOrder); traversalType = TraversalType.PREORDER; formSubTrees(treeList); /*IN ORDER TRAVERSAL*/ Integer treeArrInOrder[] = { 1, 2, 3, 4, 5, 6, 7 }; int rootIndex = 3; root.setValue(treeArrInOrder[rootIndex]); root.setRoot(true); treeList = Arrays.asList(treeArrInOrder); traversalType = TraversalType.INORDER; formSubTrees(treeList); /*POST ORDER TRAVERSAL*/ Integer treeArrPostOrder[] = { 1, 3, 2, 5, 7, 6, 4 }; rootNodeVal = treeArrPostOrder[treeArrPostOrder.length - 1]; root.setValue(rootNodeVal); root.setRoot(true); treeList = Arrays.asList(treeArrPostOrder); traversalType = TraversalType.POSTORDER; formSubTrees(treeList); } } |

### Software Engineer II at Blackbaud was asked...

You have 2 jars and 50 black beads and 50 white beads. How many would you put of each color in each jar so that if a bead was randomly selected from both jars, you had the greatest chance they would match? You have to put all of the beads in the jars. 5 Answers1 of either color in the first jar (100% chance to get that color), the rest in the 2nd jar (very close to a 50% chance to get a matching color). If you fill each jar with half black and half white then you will have a 50/50 chance of drawing a match. If you put any more than half of a color in jar number 1, then you will increase your odds of drawing that color from jar 1, but since there will be a smaller number of those beads in jar 2, you will decrease the odds of drawing that color from jar 2. Therefore any configuration other than half of each color in each jar will result in less than 50/50 odds of drawing a match (like in the answer above). As long as the ratio of black beads to white beads is 1:1 in both jars, it doesn't matter. Show More Responses One of each jar This question is too easy |

### Software Engineer II at eBay was asked...

You are given a predefined function which generates random number from 1 to 5. You need to use this function and create another function which will generate random number from 1 to 7. Now most important thing is to remember that new random function should be even (i.e. the number generated should be unpredictable, and evenly spaced out). 4 AnswersRepresent 7 in binary (111). For each place, set either 0 or 1 depending on your random number generator -- roll between 1-5, reroll if you get 5, otherwise set the bit to 0 if the roll is 1 or 2, and 1 if the roll is 3 or 4. Full function: int random7() { for (int i=0; i < 3; i++) { int answer = 0; int roll = 5; while (roll == 5) { roll = drand48()*5+1; } if (roll < 3) answer |= 1 << i; } return roll; } If the function returns float or double: - Simply multiply the answer by 7/5. If the function returns integers: - Call the rand5 function 7 times, sum the results, calculate mod7 of the sum and finally add 1. Let f() be the random function that returns a number between (1,5). Let g() = f() -1; then g is a function that returns a number between (0,4). Let h() = g()/4; then h is a function that returns a number between (0,1). Let i() = h()*6; then i is a function that returns a number between (0,6) Let j() = i() + 1; then j is a function that returns a number between (1,7). important to note that simply multiplying by 7/5 is NOT correct. If you do that you can never get 1 out of your random number . the numbers you will obtain in that case will be uniformly distributed between (7/5 and 7) not between (1,7) Show More Responses The answers where great but still not evenly distributed. There are chances to get even number more number of times then odd numbers and in some solution few numbers are never generated in random. I think the solution would be to the following steps 1) Combine the two possible number generated by random function with all possible combinations(i.e. 11,12,13,14,15,21,22.... 52,53,54,55). 2) With this we have total of 25 possible numbers. Now group all numbers in 7 groups, i.e. three numbers in one group and last group with 4 numbers {11,12,13} - group 1 ....... {44,45,51} group 7 {total numbers grouped till now is 21} and {52,53,54,55} - group 8. 3) call the random1to5() twice. 4) join two randomly generated number (e.g would be 11, 15, 55 etc) 5) Check in which group number lies, the group number will be the final random number. If the number lies in group 8 then ignore the number and re-run from step 3. I think this is evenly distributed and no chance of any number been superseded or more number of occurrence as compared to other number. |

How to calculate the depth of binary tree. 3 AnswersDFS Coud you please tell after how long from the interview day they sent you the offer ? MAX（depth(root->left), depth(root->right))+1; |

**1**–

**10**of

**770**Interview Questions

## See Interview Questions for Similar Jobs

- Software Engineer
- Software Development Engineer
- Senior Software Engineer
- Software Development Engineer I
- Software Developer
- Senior Software Development Engineer
- Software Development Engineer III
- Software Engineer III
- Director
- Staff Software Engineer
- Senior Software Developer
- Product Manager
- Software Development Manager
- Principal Software Engineer
- Data Scientist
- Senior Product Manager
- Program Manager
- Senior Manager