Software Development Engineer II was asked...March 20, 2009

↳

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

Software Development Engineer II was asked...February 12, 2010

↳

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

↳

http://www.intel.com/software/products/documentation/vlin/mergedprojects/analyzer_ec/mergedprojects/reference_olh/mergedProjects/instructions/instruct32_hh/vc270.htm this might be helpful Less

↳

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

Software Development Engineer II was asked...April 30, 2013

↳

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

Software Development Engineer II was asked...November 22, 2011

↳

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

Software Development Engineer II was asked...July 1, 2012

↳

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

Software Development Engineer II was asked...August 4, 2020

↳

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

Software Development Engineer (SDE) II was asked...October 22, 2015

↳

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

Software Development Engineer II was asked...October 4, 2012

↳

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

↳

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

Software Development Engineer In Test (SDET) II was asked...October 3, 2012

↳

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