## Related Job Search

# Software development engineer ii Interview Questions

# 1K

Software Development Engineer Ii interview questions shared by candidates### Determine whether the binary representation of a number if a palindrome or not, code it on a white board.

12 Answers↳

This was the first question I was asked and is considered a warm up.

↳

anon.. would this work for a number like 17 (10001)?

↳

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"< Less

### Write a code to reverse binary bit pattern for an integer without using any string or utility methods?

6 Answers↳

there is rol and ror operations which can be useful to shift places and also the left most digit can move to the end during the operation. Less

↳

unsigned int a=123; // Given number unsigned int b=0; /// temp variable int i; for(i=0; i>1; } Less

↳

unsigned int a=123; // Given number unsigned int b=0; /// temp variable int i; for(i=0; i> 1; } Less

### You are given an array of numbers. You need to print the length of the maximum continuous sequence that you encounter. For example if input is [3,8,10,1,9,6,5,7,2 ], the continuous sequences are{1,2,3} and {5,6,7,8,9,10} the latter is the longest one so the answer becomes 6. O(n) solution was asked for, assuming you have a hash map which supports O(1) insertion and fetching operations

5 Answers↳

Sorting makes the time complexity as O(nlogn). An O(n) solution was asked for

↳

package array; import java.util.Hashtable; /* * You are given an array of numbers. * You need to print the length of the maximum continuous sequence that you encounter. * For example if input is [3,8,10,1,9,6,5,7,2 ], * the continuous sequences are{1,2,3} and {5,6,7,8,9,10} * the latter is the longest one so the answer becomes 6. * O(n) solution was asked for, * assuming you have a hash map which supports O(1) insertion and fetching operations * src: http://www.glassdoor.com/Interview/Microsoft-India-Interview-Questions-EI_IE1651.0,9_IL.10,15_IN115_IP6.htm */ public class FindLengthOfLongestRandomlyDistContinousSequenceOfNumber { public static void main(String[] str){ int a[] = {3,6,8,1,5,7,0,9,2,4,10,14,13,12,11}; System.out.println(findLength(a)); int b[] = {5,2,3,1,6,7,10,8}; System.out.println(findLength(b)); } private static int findLength(int[] a) { int result = 0; Hashtable h = new Hashtable(); for(int i=0; i result){ result = curr.maxValue; } if(next != null){ next = h.get( curr.max); next.maxValue = curr.maxValue; h.put(a[i]+1, next); next.min = curr.min; } if(prev != null){ prev = h.get(curr.min); prev.maxValue = curr.maxValue; h.put(a[i]-1, prev); prev.max = curr.max; } h.put(a[i], curr); } } return result; } } class Node{ int maxValue; int max; int min; public Node(int v, int m, int n){ maxValue = v; max = m; min = n; } } Less

↳

static int findlongconsecutivesubseq(int[] arr) { HashSet s= new HashSet(); int ans=0; //put all entries in hashset for(int i=0;i ans) ans=j-arr[i]; } } return ans; } Less

### Find k largest/smallest number in a series of numbers. What data-structures will you use? Code it on white board.

5 Answers↳

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

↳

@Ajit: What're the initial values of the max heap? What happens to the first value that comes in? Less

↳

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

### 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 Answers↳

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

↳

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 Less

↳

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

### General Questions about leadership principle, 3 coding questions and 1 system design question

5 Answers↳

Leadership questions can be answered based on your past experience. I would suggest be honest about what you did and why you did that. The interviewers are highly skilled at what they do and can surely detect any lies. Keep the answers conversational. Less

↳

What types of coding questions did you get? Do you feel like the recruiters prepared you for all the technical portions of the interview? Less

↳

Hi! As an Amazon employee who interviewed and hired a lot of people here, I've created a guide that has all the questions and winning answers from an Amazonian recruiter perspective. Please check it out at interviewjoy.com/services/interview-process-details/amazon-senior-manager-interview-questions/ . Pls also check the positive feedback at the bottom of that page! Thanks. Less

### Given an array of items of three different colors red, green, blue. How would you sort the items in the array so that all the items with a certain color would be grouped together.

4 Answers↳

Use a hashmap, use the color as key and count as value. Iterate through array and put count of each color, get the keys from hashmap and iterate to fill the array again Less

↳

brute force method: O(n^2) 1st pass, count the number of occurrences for each of the 3 colours, x y and z 2nd pass: modify the original array: index 0 to x will be colour 1, x+1 to x+y is colour 2, and x+y+1 to x+y+z will be colour 3 Method 2, this can be sorted using a modified version of textbook sorting algorithm, if we treat the 3 colours as a primitive data type like an integer, for example: Red = 1, Blue = 2, Green = 3. Typical choices would be mergesort or quicksort for O(nlogn) public int[] colourSort(Colour[] array){ Colour[] helper = new Colour[array.length]; mergeSort(array, helper, 0, array.length); } mergeSort(Colour[] array, Colour[] helper, int start, int end){ int mid = start + (end - start)/2; while(start Less

↳

brute force method: O(n^2) 1st pass, count the number of occurrences for each of the 3 colours, x y and z 2nd pass: modify the original array: index 0 to x will be colour 1, x+1 to x+y is colour 2, and x+y+1 to x+y+z will be colour 3 Method 2, this can be sorted using a modified version of textbook sorting algorithm, if we treat the 3 colours as a primitive data type like an integer, for example: Red = 1, Blue = 2, Green = 3. Typical choices would be mergesort or quicksort for O(nlogn) public int[] colourSort(Colour[] array){ Colour[] helper = new Colour[array.length]; mergeSort(array, helper, 0, array.length); } mergeSort(Colour[] array, Colour[] helper, int start, int end){ int mid = start + (end - start)/2; while(start Less

### Two sorted arrays. you can start from any one them, and then at common element you may or may not jump to other array. Continue in this manner till you reach the end of an array. Find the path that results the maximum sum.

3 Answers↳

Greedy algorithm O(m+n); not really hard once you know it's greedy.

↳

DP can also be used... O(m+n) again...

↳

import java.util.*; class gAlg{ public static void main(String[] args){ int[] a = new int[5]; int[] b = new int[5]; int[] c = new int[5]; int sum= 0; a[0]=2;a[1]=8;a[2]=9;a[3]=7;a[4]=10; b[0]=3;b[1]=2;b[2]=10;b[3]=9;b[4]=9; System.out.println(Arrays.toString(a)); System.out.println(Arrays.toString(b)); int i; for(i=0;i<5;i++){ c[i]=Math.max(a[i],b[i]); sum = sum+c[i]; } System.out.println(Arrays.toString(c)); System.out.println(sum); } } Less

### How would you reverse a linked list in Java?

4 Answers↳

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

↳

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

↳

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

### 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 Answers↳

Creating 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? Less

↳

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); } } Less

↳

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); } } Less