Engineer II Interview Questions | Glassdoor

# Engineer II Interview Questions

1,619

Engineer ii interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

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

Mar 19, 2009
 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 Responsesbool 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); endpublic 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 truestring 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 II at Amazon was asked...

Nov 22, 2011
 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 ResponsesI 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, 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/

### Software Engineer II at Orbitz Worldwide was asked...

Dec 11, 2010
 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 ResponsesDisadvantage of recursion is the large amount of space on the stack for a large m in this case.

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

Apr 12, 2012
 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 duplicatesI 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)

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

May 6, 2009
 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 Responsespublic 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; }

### Software Development Engineer II at Microsoft was asked...

Jul 1, 2012
 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, 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) spaceShow More ResponsesStep 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

### Software Development Engineer In Test (SDET) II at Expedia Group was asked...

Oct 3, 2012
 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 function3 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; 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 a2z was asked...

Sep 12, 2011
 find the frequence of words in a given file3 AnswersUse hashmapHashmap works, but MapReduce could be a better answer. Hashmap is a safe answer if you're not familiar with MapReduceYou need a cluster/grid for MapReduce. That may not be available all the time.

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

Sep 26, 2013
 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 ResponsesOne of each jarThis question is too easy

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

Mar 28, 2011
 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 ResponsesThe 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.
110 of 1,619 Interview Questions