Coding Questions

Question 1

An array of boolean values is divided into two sections; the left section consists of all false and the right section consists of all true. Find the First True in a Sorted Boolean Array of the right section, i.e. the index of the first true element. If there is no true element, return -1.

Input: arr = [false, false, true, true, true]

Output: 2

Explanation: first true’s index is 2.

Answer 1

    public static int firstBoundry(boolean[] arr) {
        int low = 0;
        int high = arr.length - 1;
        int boundryIndex = -1;

        while (low <= high) {
            int mid = (low + high) >>> 1;

            if (arr[mid]) {
                high = mid - 1;
                boundryIndex = mid;
            } else {
                low = mid + 1;
            }
        }
        return boundryIndex;
    }

Question 2

Given an array of integers sorted in increasing order and a target, find the index of the first element in the array that is larger than or equal to the target. Assume that it is guaranteed to find a satisfying number.

Input:

arr = [1, 3, 3, 5, 8, 8, 10]
target = 2
Output: 1

Explanation: the first element larger than 2 is 3 which has index 1.

Question 3

Given a sorted array of integers and a target integer, find the first occurrence of the target and return its index. Return -1 if the target is not in the array.

Input:

arr = [1, 3, 3, 3, 3, 6, 10, 10, 10, 100]
target = 3
Output: 1

Explanation: The first occurrence of 3 is at index 1.

Question 4

Given an integer, find its square root without using the built-in square root function. Only return the integer part (truncate the decimals).

Input: 16

Output: 4

Input: 8

Output: 2

Explanation: square root of 8 is 2.83…, return the integer part, 2

Question 5

A sorted array of unique integers was rotated at an unknown pivot. For example, [10, 20, 30, 40, 50] becomes [30, 40, 50, 10, 20]. Find the index of the minimum element in this array.

Input: [30, 40, 50, 10, 20]

Output: 3

Explanation: the smallest element is 10 and its index is 3.

Input: [3, 5, 7, 11, 13, 17, 19, 2]

Output: 7

Explanation: the smallest element is 2 and its index is 7.

Question 6

Max depth of a binary tree is the longest root-to-leaf path. Given a binary tree, find its max depth

Answer 6

int treeMaxDepth0(TreeNode node) {
        if (node == null) {
            return 0;
        }

        if (node.left == null && node.right == null) {
            return 0;
        }

        int leftDepth = treeMaxDepth0(node.left) + 1;
        int rightDepth = treeMaxDepth0(node.right) + 1;

        return Math.max(leftDepth, rightDepth);
    }