eBay Interview Question: Using the characters on a tel... | Glassdoor

## Interview Question

Software Engineer 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);