Templates

Question 1

What is the binary search template?

Answer 1

boolean binarySearchIterative(int[] nums, int num) {

    if (nums.length == 0) {
      return false;
    }

    int low = 0;
    int high = nums.length - 1;

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

      if (num == nums[mid]) {
        return true;
      }

      if (num < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return false;
  }

Question 2

What is the in-order-traversal template?

Answer 2

void inOrderTraversal(Node<Integer> node) {
        if (node == null) {
            return;
        }
            inOrderTraversal(node.left);
            System.out.println(node.val);
            inOrderTraversal(node.right);
    }

Question 3

What is the pre-order-traversal template?

Answer 3

void preOrderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }

Question 4

What is the post-order-traversal template?

Answer 4

void postOrderTraversal(Node<Integer> root) {
        if (root != null) {
            postOrderTraversal(root.left);
            postOrderTraversal(root.right);
            System.out.println(root.val);
        }
    }

Question 5

What is the DFS on tree template?

Answer 5

Node dfsTree(Node node, int target) {
    if (node == null)
      return null;
    if (node.getElement() == target) 
      return node;

    Node left = dfsTree(node.getLeft(), target);

    if (left != null)
      return left;

    Node right = dfsTree(node.getRight(), target);

    return right;
  }

Question 6

What is the sliding window template?

Answer 6

function fn(arr):
    left = 0
    for (int right = 0; right < arr.length; right++):
        Do some logic to "add" element at arr[right] to window

        while WINDOW_IS_INVALID:
            Do some logic to "remove" element at arr[left] from window
            left++

        Do some logic to update the answer