Interview Question

Software Engineer Interview Redmond, WA

Using the characters on a telephone dial, give all the

  permutation of strings for given digits.
Answer

Interview Answer

2 Answers

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

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up