Software Development Engineer II Interview Questions

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.

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

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

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

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?

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

findCombination(int[] array, int sum) { sort(array); // O(n*log n) int i = 0, j=array.length-1; while (i sum) j--; else { print(i,j); i++; } } }

You have to use the "skeeve" algorithrm for these questions. its what they're all looking for.

public class ReverseWordsInString { public static void main(String[] args) { System.out.println(">"); } private static String reverseWords(String original) { if (original == null || original.isEmpty()) { throw new IllegalArgumentException("IP cannot be null or empty"); } final Pattern p = Pattern.compile("[a-zA-Z]"); final StringBuilder returnString = new StringBuilder(); StringBuilder temp = new StringBuilder(); for (int i = 0; i 0) { returnString.append(reverse(temp.toString())); temp = new StringBuilder(); } returnString.append(original.charAt(i)); } } if (temp.length() > 0) { returnString.append(reverse(temp.toString())); } return returnString.toString(); } private static String reverse(String data) { StringBuilder ret = new StringBuilder(); for (int i = data.length() - 1; i >= 0; i--) { ret.append(data.charAt(i)); } return ret.toString(); }

/// /// Recieve a string of words and returns the words reversed without changing the order. /// Here's my C# method: public static string ReverseWordsInSentence(string sentence) { char[] whiteSpace = " \t\n".ToCharArray(); string[] words = sentence.Split(whiteSpace); int count = 0; foreach (string individualWord in words) { words[count] = new string(individualWord.ToCharArray().Reverse().ToArray()); count++; } return string.Join(" ", words); }

public class ReverseString { public String stringReverse(String str) { if (str == null || str.length() = 0; i--) { sentence.append(word.charAt(i)); } sentence.append(" "); } return sentence.toString(); } public static void main(String[] args) { ReverseString obj = new ReverseString(); String test = "this is a test"; System.out.println(obj.stringReverse(test)); } }

I'll say 365 there are 365 possible birthdays, there is 1/365 chance for a person's birthday falling on a specific day. You need (1/2 of 365)*2 to improve the chance to 50% for two peoples' birthday falling on the same date.

No. There is no N In your formula. That probability depends on N. http://en.wikipedia.org/wiki/Birthday_problem