eBay

www.ebayinc.com
Engaged Employer

## Interview Question

Interview Redmond, WA

# Using the characters on a telephone dial, give all the

permutation of strings for given digits.

0

Find the first zero based index of number > = given number in a sorted array static public int IndexOfFirstNumberEqualOrGreater(int[] input, int number_to_find) { int minIndex = 0; int maxIndex = input.Length - 1; int current_index; do { current_index = (minIndex + maxIndex) / 2; if (number_to_find == input[current_index]) { if (current_index > 0 && number_to_find == input[current_index - 1]) { maxIndex = current_index - 1; } else break; } else if (input[current_index] < number_to_find) minIndex = current_index + 1; else maxIndex = current_index - 1; } while (minIndex <= maxIndex); if (minIndex == input.Length ) return -1; else return current_index; }

Xavier on Aug 10, 2012
1

Tree in order traversal, return the next node.ie, if the search node is found, return the next in order traversal node public class BinarySearchTree { public class TreeNode { public int value; public TreeNode left; public TreeNode right; }; static public TreeNode FindNextNodeInOrderTraversal(TreeNode root, int value) { TreeNode prev_node = null; return FindNextNodeInOrderTraversal(root, value, ref prev_node); } static public TreeNode FindNextNodeInOrderTraversal(TreeNode root, int value, ref TreeNode prev_node) { if (root == null) return null; var return_value = FindNextNodeInOrderTraversal(root.left, value, ref prev_node); if (return_value != null) return return_value; if (prev_node != null && prev_node.value == value) return root; else prev_node = root; return FindNextNodeInOrderTraversal(root.right, value, ref prev_node); } static public ArrayList InOrderTraversal(TreeNode root, ArrayList array_list = null) { if (root == null) return null; if (array_list == null) array_list = new ArrayList(); InOrderTraversal(root.left, array_list); array_list.Add(root.value); InOrderTraversal(root.right, array_list); return array_list; } }

Xavier on Aug 10, 2012