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

If 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

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

Average cases: Heap sort O(n lg n) Insertion sort O(n^2) Quicksort O(n lg n) Merge sort O(n lg n) Bubble sort O(n lg n)

Bubble sort is O(n2)..

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