First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.

      boolean isBadVersion(int version); */

/*

time:O(logn), space:O(1)

*/

public class Solution extends VersionControl {

    public int firstBadVersion(int n) {

        if (n <= 0) {

            return 0;

        }

        int left = 1;

        int right = n;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {

                right = mid;

            } else {

                left = mid;

            }

        }

        if (isBadVersion(left)) {

            return left;

        }

        return right;

    }

}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = new BSTIterator(root);

 * while (i.hasNext()) v[f()] = i.next();

 */

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

/*

Every time, we call next(), we will traverse to find the left most TreeNode of the current node if existed. If the current node is null, then we pop out a node from the stack and return its value. The first time we call next(), it takes O(h) time, but the other TreeNode in the stack will take only O(1) time when call the next(). And there are h TreeNode in the stack. So the average time complexity will be O(1) and space complexity will be O(h).

hasNext() and next(): time:O(1), space:O(h)

*/

public class BSTIterator {

    public Stack<TreeNode> stack = new Stack<>();

    public TreeNode root;

    public BSTIterator(TreeNode root) {

        this.root = root;

    }

    /** @return whether we have a next smallest number */

    public boolean hasNext() {

        return root != null || !stack.isEmpty();

    }

    /** @return the next smallest number */

    public int next() {

        while (root != null) {

            stack.push(root);

            root = root.left;

        }

        root = stack.pop();

        TreeNode node = root;

        root = root.right;

        return node.val;

    }

}

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

/*
BFS traversal, 
time:O(n), space:O(n)
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

/*

Set an array to record the number of each character in string t. Use two pointers to iterate string s, when the substring in string s contains string t, if the length of the substring is smaller than the previous recorded length, update the minimum window substring. Then move forward the left pointer and continue to check if the new substring contains string t.

time:O(n), space:O(1)

*/

public class Solution {

    public String minWindow(String s, String t) {

        if (s == null || s.length() == 0 || t == null) {

            return "";

        }

        int[] map = new int[256];

        for (char ch : t.toCharArray()) {

            map[ch]++; 

        }

        int i = 0;

        int j = 0;

        int count = t.length();

        int length = Integer.MAX_VALUE;

        String res = "";

        for (i = 0; i < s.length() - t.length() + 1; i++) {

            while (j < s.length() && count > 0) {

                if (map[s.charAt(j)]-- > 0) {

                    count--;

                }

                j++;

            }

            if (count == 0 && j - i < length) {

                length = j - i;

                res = s.substring(i, j);

            }

            if (map[s.charAt(i)]++ == 0) {

                count++;

            }

        }

        return res;

    }

}

Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

/*

When find one land, increment the number of lands, then use DFS/BFS to find all the adjacent lands. In order to avoid duplicate, set each land just found to be water, like set '1' to '0'.

*/

//DFS, time:O(m*n), space:O(1)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                dfs(grid, i, j);

            }

        }

        return count;

    }

    public void dfs(char[][] grid, int i, int j) {

        if (i < 0 || i >= grid.length || 

            j < 0 || j >= grid[0].length) {

            return;

        }

        if (grid[i][j] == '1') {

            grid[i][j] = '0';

            dfs(grid, i + 1, j);

            dfs(grid, i, j + 1);

            dfs(grid, i - 1, j);

            dfs(grid, i, j - 1);

        }

    }

}

//BFS, time:O(m*n), space:O(m*n)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                bfs(grid, i, j);

            }

        }

        return count;

    }

    public void bfs(char[][] grid, int i, int j) {

        int m = grid.length;

        int n = grid[0].length;

        int[] dx = {1, 0, -1, 0};

        int[] dy = {0, 1, 0, -1};

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(i * n + j);

        grid[i][j] = '0';

        while (!queue.isEmpty()) {

            int index = queue.poll();

            for (int k = 0; k < 4; k++) {

                int nx = index / n + dx[k];

                int ny = index % n + dy[k];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {

                    continue;

                }

                if (grid[nx][ny] == '0') {

                    continue;

                }

                queue.offer(nx * n + ny);

                grid[nx][ny] = '0';

            }

        }

    }

}

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

/*

time:O(logn), space:O(1)

*/

public class Solution {

    public int mySqrt(int x) {

        if (x == 0) {

            return 0;

        }

        int left = 0;

        int right = x;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (mid < x / mid) {

                left = mid;

            } else {

                right = mid;

            }

        }

        if (right <= x / right) {

            return right;

        }

        return left;

    }

}

Four Integers

Given four integers, make F(S) = abs(S[0]-S[1])+abs(S[1]-S[2])+abs(S[2]-S[3]) to be largest.


import java.util.*;

public class Solution {
    public static int[] fourInteger(int A, int B, int C, int D) {
        int[] ans = {A, B, C, D};
        Arrays.sort(ans);
        swap(ans, 0, 1);
        swap(ans, 2, 3);
        swap(ans, 0, 3);
        return ans;
    }
    private static void swap(int[] array, int i, int j) {
        array[i] ^= array[j];
        array[j] ^= array[i];
        array[i] ^= array[j];
    }

    public static void main(String[] args) {
        int[] ans = fourInteger(1,2,3,4);
        for (Integer i : ans) {
            System.out.print(i + " ");
        }

    }
}