Global variable?

There is no such thing as a ‘global variable’ in Java.

In computer programming, a global variable is a variable that is accessible in every scope (the global environment). Some languages, like Java, don’t have global variables. reference

But static variable can be seen as one, although every static variable must belong to some class (like Math.MIN_VALUE).

Global variables are generally only used for declaring constants. In this case, declare it as ‘final static’. reference

Four types of variable in Java

Local variables

Created when the method, constructor or block is entered and will be destroyed once it exits the method, constructor or block.

Instance variables

Outside a method or constructor.

When a space is allocated for an object in the heap, a slot for each instance variable value is created. It is destroyed when the object is destroyed.

Class/static variables

Static variable is class variable.

Declared with ‘static’ keyword in a class.

Constants

Most common usage of static variable - constant.

Declared with ‘static final’ keyword in a class.

One more thing

About stack and heap in Java:

In Java, primitives are created on the stack.

Objects are created on the heap, and only references (which in turn are primitives) are passed around on the stack.

If you create an object, it is put on the heap, with all the variables that belong to it, so that it can persist after the function call returns.

Question

Given a BST, find the node that is larger/smaller than particular number

Or the question can be:

Given a binary search tree and a value k, please find a node in the binary search tree whose value is closest to k. link

Analysis

This post is based on the second question above.

1. Traverse the tree top-down.
2. While traversing, record values that are closer to target than previously-found value.
3. If found, the target, break and return. source

Code

From this post.

BinaryTreeNode* getClosestNode(BinaryTreeNode* pRoot, int value)
{
    BinaryTreeNode* pClosest = NULL;
    int minDistance = 0x7FFFFFFF;
    BinaryTreeNode* pNode = pRoot;
    while(pNode != NULL){
        int distance = abs(pNode->m_nValue - value);
        if(distance < minDistance){
            minDistance = distance;
            pClosest = pNode;
        }

        if(distance == 0)
            break;

        if(pNode->m_nValue > value)
            pNode = pNode->m_pLeft;
        else if(pNode->m_nValue < value)
            pNode = pNode->m_pRight;
    }

    return pClosest;
}

4 Types of Access Level

Private

Like you’d think, only the class in which it is declared can see it.

Package Private (default)

Can only be seen and used by the package in which it was declared.

This is the default in Java (which some see as a mistake).

Protected

Package Private, plus can be seen by subclasses.

Public

Everyone can see it.

Differences

Note: Java default access setting is ‘No modifier’, which is also called ‘Package Private’.

Another note: by saying ‘subclass’, it means subclass declared in another package.

Example

Class structure:

For the methods of ‘Alpha’ class, the visibility is listed below.

For example, Gamma can only access public methods in Alpha.

Additional question

Can we declare a top-level class as private?

Answer: No, Java does not allow top-level private class. Think about it, a top-level class as private would be useless because nothing could access it.

If you really want, you can use inner or nested classes. If you have a private inner or nested class, then access is restricted to the scope of that outer class.

link

Question

Implement a iterator for a binary search tree

Related question: Binary Tree Inorder Traversal

Analysis

First of all, what is an iterator in Java?

Java has a commonly used Iterator interface.

It is usually used like this:

Iterator e = container.iterator();  
while (e.hasNext()) {
    System.out.println(e.next());
}

The source code of Iterator interface:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

In this post, we will only implement next(), because Tree node deletion is covered in another post, and it’s not easy.

The most standard way is to do an inorder traversal (by storing a pointer to the next node). The only difference is iterator is 1 step at a time. If you cannot write inorder traversal without using recursion, learn it first. The solution of iterator is available from this blog, although he made some small syntax errors.

Code

public class BinaryTreeIterator {

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

    public BinaryTreeIterator(TreeNode root) {
        if (root == null) {
            throw new NoSuchElementException("Empty tree");
        }
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

    public TreeNode next() {
        TreeNode top = stack.pop();
        TreeNode right = top.right;
        while (right != null) {
            stack.push(right);
            right = right.left;
        }
        return top;
    }
}

Question

link

Write an efficient algorithm that searches for a value in an n x m table (two-dimensional array). This table is sorted along the rows and columns — that is,

Table[i][j] ≤ Table[i][j + 1],
Table[i][j] ≤ Table[i + 1][j]

Related questions

Search a 2D Matrix.

Searching a 2D Sorted Matrix.

Count negative in a 2D Sorted Matrix.

Analysis

This is a very similar question as prevous one. The solution is O(n) with a linear walk from top-right to bottom-left.

Code

int countNegatives(int array[][], int size) {
    int col = size - 1, row = 0;
    int count = 0;

    while(row < size && col >= 0) {
        if(array[row][col] < 0 ) {
            count = count + (col + 1);
            row = row + 1;
        }
        else {
            col = col - 1;
        }
    }
    return count;
}

Question

link

Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree.

Input:

With min value as 5 and max value as 13, the output is:

Analysis

There is a good analysis from geeksforgeeks:

1. If value of root’s key is greater than k1, then recursively call in left subtree.
2. If value of root’s key is in range, then print the root’s key.
3. If value of root’s key is smaller than k2, then recursively call in right subtree.

Another great solution is from Arden Dertat.

Code

First code, from geeksforgeeks - print the result instead of return.

void Print(struct node *root, int k1, int k2)
{
   if ( NULL == root )
      return;
   if ( k1 < root->data )
     Print(root->left, k1, k2);
   if ( k1 <= root->data && k2 >= root->data )
     printf("%d ", root->data );
   if ( k2 > root->data )
     Print(root->right, k1, k2);
}

Second code from Arden:

def trimBST(tree, minVal, maxVal): 
    if not tree: 
        return 
    tree.left=trimBST(tree.left, minVal, maxVal) 
    tree.right=trimBST(tree.right, minVal, maxVal) 
    if minVal<=tree.val<=maxVal: 
        return tree 
    if tree.val<minVal: 
        return tree.right 
    if tree.val>maxVal: 
        return tree.left

First Word

Permutation questions provide you with a list of items, and you build, validate and return a combination of these items. The standard solution is to sort the input first, and add items 1 by 1.

Do not try to solve the problems with anything other than the template given below, because otherwise the code is impossible to be bug-free.

Though the code is standard, many question are very difficult, and most of time duplication removal can be tough.

Template

public List<List<Integer>> subsets(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(num == null || num.length == 0) {
        return result;
    }
    Arrays.sort(num);  
    subsetsHelper(result, new ArrayList<Integer>(), num, 0);
    return result;
}

private void subsetsHelper(List<List<Integer>> result,
    List<Integer> list, int[] num, int pos) {
    result.add(new ArrayList<Integer>(list));
    for (int i = pos; i < num.length; i++) {
        list.add(num[i]);
        subsetsHelper(result, list, num, i + 1);
        list.remove(list.size() - 1);
    }
}

Note: 2nd last line “subsetsHelper(result, list, num, i + 1);”.

It’s easy to mistake it as “pos+1” instead of “i+1”, which will result in TLE.

Question list

1. Subsets

2. Permutations

3. Subsets II

4. Permutations II

Additional

1. Combination Sum

2. Combination Sum II

3. Palindrome Partitioning

4. Palindrome Partitioning II

5. Restore IP Addresses

6. Combinations

7. Letter Combinations of a Phone Number

Code

Subsets - good example for practise (by applying the model)

public List<List<Integer>> subsets(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(num == null || num.length == 0) {
        return result;
    }
    Arrays.sort(num);
    helper(result, new LinkedList<Integer>(), num, 0);
    return result;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int position) {
    ans.add(new LinkedList<Integer>(path));
    for (int i = position; i < num.length; i ++) {
        path.add(num[i]);
        helper(ans, path, num, i + 1);
        path.remove(path.size() - 1);
    }
}

Permutations

public List<List<Integer>> permute(int[] num) {
    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    if (num == null || num.length == 0) {
        return ans;
    }
    helper(ans, new LinkedList<Integer>(), num);
    return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num){
    if (path.size() == num.length) {
        ans.add(new LinkedList<Integer>(path));
        return;
    }
    for (int i = 0; i < num.length; i ++) {
        if (!path.contains(num[i])) {
            path.add(num[i]);
            helper(ans, path, num);
            path.remove(path.size() - 1);
        }
    }
}

Subsets II - good example for practise

We only care how many times we use the duplicate number, we care not the order. So, only 3 lines of code is added based on previous solution.

public List<List<Integer>> subsetsWithDup(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(num == null || num.length == 0) {
        return result;
    }
    Arrays.sort(num);
    helper(result, new LinkedList<Integer>(), num, 0);
    return result;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int position) {
    ans.add(new LinkedList<Integer>(path));
    for (int i = position; i < num.length; i ++) {
        if (i > position && num[i - 1] == num[i]) {
            // if duplicate, only append num[position]
            continue;
        }
        path.add(num[i]);
        helper(ans, path, num, i + 1);
        path.remove(path.size() - 1);
    }
}

Permutations II

public List<List<Integer>> permuteUnique(int[] num) {
    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    if (num == null || num.length == 0) {
        return ans;
    }
    Arrays.sort(num);
    helper(ans, new LinkedList<Integer>(), new int[num.length], num);
    return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] visited, int[] num){
    if (path.size() == num.length) {
        ans.add(new LinkedList<Integer>(path));
        return;
    }
    for (int i = 0; i < num.length; i ++) {
        if (visited[i] == 1) {
            continue;
        }
        if (i > 0 && visited[i-1] == 0 && num[i - 1] == num[i]) {
            continue;
        }
        visited[i] = 1;
        path.add(num[i]);
        helper(ans, path, visited, num);
        visited[i] = 0;
        path.remove(path.size() - 1);
    }
}

Combination Sum

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    Arrays.sort(candidates);
    helper(ans, new ArrayList<Integer>(), candidates, 0, target);
    return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> path, 
                    int[] nums, int pos, int target) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        ans.add(new ArrayList<Integer>(path));
        return;
    }
    for (int i = pos; i < nums.length; i ++) {
        path.add(nums[i]);
        helper(ans, path, nums, i, target - nums[i]);
        path.remove(path.size() - 1);
    }
}

Combination Sum II

public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    Arrays.sort(candidates);
    helper(ans, new ArrayList<Integer>(), candidates, 0, target);
    return ans;
}

private void helper(ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> path, 
                    int[] nums, int pos, int target) {
    if (target < 0) {
        return;
    } else if (target == 0) {
        ans.add(new ArrayList<Integer>(path));
        return;
    }
    for (int i = pos; i < nums.length; i ++) {
        if (i > pos && nums[i-1] == nums[i]) {
            continue;
        }
        path.add(nums[i]);
        helper(ans, path, nums, i + 1, target - nums[i]);
        path.remove(path.size() - 1);
    }
}

Palindrome Partitioning

Naive approach can AC:

public ArrayList<ArrayList<String>> partition(String s) {
    ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
    if (s == null || s.length() == 0) {
        return ans;
    }
    helper(ans, new ArrayList<String>(), s, 0);
    return ans;
}

private void helper(ArrayList<ArrayList<String>> ans, ArrayList<String> path, String s, int pos) {
    if (pos == s.length()) {
        ans.add(new ArrayList<String>(path));
        return;
    }
    for (int i = pos + 1; i <= s.length(); i++) {
        String sub = s.substring(pos, i);
        if (!isPlm(sub)) {
            continue;
        }
        path.add(sub);
        helper(ans, path, s, i);
        path.remove(path.size() - 1);
    }
}

private boolean isPlm(String str) {
    int left = 0, right = str.length() - 1;
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) 
            return false;
        left++;
        right--;
    }
    return true;
}

Use DP to optimize the process of palindrome validation.

// palindrome validation optimized with DP
public ArrayList<ArrayList<String>> partition(String s) {
    ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
    if (s == null || s.length() == 0) {
        return ans;
    }
    helper(ans, new ArrayList<String>(), s, 0, palindromeMap(s));
    return ans;
}

private void helper(ArrayList<ArrayList<String>> ans, 
ArrayList<String> path, String s, int pos, boolean[][] palinMap) {
    if (pos == s.length()) {
        ans.add(new ArrayList<String>(path));
        return;
    }
    for (int i = pos; i < s.length(); i++) {
        if (!palinMap[i][pos]) {
            continue;
        }
        path.add(s.substring(pos, i + 1));
        helper(ans, path, s, i + 1, palinMap);
        path.remove(path.size() - 1);
    }
}

private boolean[][] palindromeMap(String s) {
    int len = s.length();
    boolean[][] map = new boolean[len][len];
    char[] ss = s.toCharArray();
    for (int i = 0; i < len; i++) {
        for (int j = i; j >= 0; j--) {
            if (i == j) {
                map[i][j] = true;
            } else if (i - j == 1) {
                map[i][j] = ss[i] == ss[j];
            } else {
                map[i][j] = (ss[i] == ss[j]) & map[i - 1][j + 1];
            }
        }
    }
    return map;
}

Palindrome Partitioning II

Used above template and got TLE. Turns out, this is a pure DP question.

Skip for now.

Restore IP Addresses

public List<String> restoreIpAddresses(String s) {
    List<String> ans = new LinkedList<String>();
    if (s == null || s.length() == 0) {
        return ans;
    }
    helper(ans, s, "", 0, 0);
    return ans;
}

private void helper(List<String> ans, String s, String path, int pos, int count) {
    if (count == 4) {
        if (pos == s.length()) {
            ans.add(path.substring(1));
        }
        return;
    }
    for (int i = pos; i < s.length(); i++) {
        if (i - pos >= 3) {
            break;
        }
        if (!isValidNum(s.substring(pos, i + 1))) {
            continue;
        }
        String newPath = path + "." + s.substring(pos, i + 1);
        helper(ans, s, newPath, i + 1, count + 1);
    }
}

private boolean isValidNum(String str) {
    if (str.length() > 1 && str.charAt(0) == '0') {
        return false;
    }
    int num = Integer.parseInt(str);
    if (num < 0 || 255 < num) {
        return false;
    }
    return true;
}

Combinations

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ans = new LinkedList<List<Integer>>();
    if (n == 0 || k == 0 || n < k) {
        return ans;
    }
    helper(ans, new LinkedList<Integer>(), n, k, 1);
    return ans;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int n, int k, int pos) {
    if (path.size() == k) {
        ans.add(new LinkedList<Integer>(path));
        return;
    }
    for (int i = pos; i <= n; i++) {
        path.add(i);
        helper(ans, path, n, k, i + 1);
        path.remove(path.size() - 1);
    }
}

Letter Combinations of a Phone Number

public List<String> letterCombinations(String digits) {
    List<String> ans = new LinkedList<String>();
    if (digits == null) {
        return ans;
    }
    String[] pad = new String[]{
        " ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    helper(ans, "", pad, digits, 0);
    return ans;
}

private void helper(List<String> ans, String path, String[] pad, String digits, int pos) {
    if (path.length() == digits.length()) {
        ans.add(path);
        return;
    }
    String letters = pad[digits.charAt(pos) - '0'];
    for (int i = 0; i < letters.length(); i++) {
        path += letters.charAt(i) + "";
        helper(ans, path, pad, digits, pos + 1);
        path = path.substring(0, path.length() - 1);
    }
}

Conclusion

Remember the model! It applies to most search question.

Quicksort

Quicksort is faster because it’s in-place sort (with O(log n) stack space).

Typical in-place sort is not stable.

Mergesort

Mergesort uses O(n) space, thus slower.

It is stable sort.

Stability 稳定排序

When sorting, if only part of the data is examined, there’re possibility of multiple different correctly sorted versions of the original list. Stable sorting algorithms will preserve the original relative order.

One application for stable sorting algorithms is sorting a list using a primary and secondary key.

Example:

Stable sort: first sorting by rank/number (using any sort), and then a stable sort by suit.

Quicksort would not be able to do that.

Conclusion

Quicksort is faster.

strStr Question

Implement strStr

Before solving the problem, it’s very important to ask this questions:

Can we use system library (eg. str.substring() or indexOf())

The answer is ‘No’, but asking this question shows that you think deep into questions. Keep in mind the characteristics for a candidate is judged by 4 things:

1. Code readability - how long does it take to review your code?
2. Coding convention - do you have the habit to write efficient code?
3. Testing - it’s good habit to write test case before asked to.
4. Communication skills

Solution of this question is double for-loop. It’s not linear time complexity, but it’s OK. After getting the code correct, it’s best to tell the O(n) time KMP solution. However, it’s most probably not required to implement.

my code

public String strStr(String haystack, String needle) {
    if (haystack == null || needle == null) {
        return null;
    }
    int len1 = haystack.length();
    int len2 = needle.length();
    for (int i = 0; i <= len1 - len2; i ++) {
        // start from i, match chars
        boolean match = true;
        for (int j = 0; j < len2; j ++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                match = false;
                break;
            }
        }
        if (match) {
            return haystack.substring(i);
        }
    }
    return null;
}

alternative code from ninechap

public String strStr(String haystack, String needle) {
    if(haystack == null || needle == null) {
        return null;
    }
    int i, j;
    for(i = 0; i < haystack.length() - needle.length() + 1; i++) {
        for(j = 0; j < needle.length(); j++) {
            if(haystack.charAt(i + j) != needle.charAt(j)) {
                break;
            }
        }
        if(j == needle.length()) {
            return haystack.substring(i);
        }
    }
    return null;
}

Google Coding Style

if … else …

if (condition) {
    statements;
} else if (condition) {
    statements;
} else {
    statements;
}

自增/自减

while （d++ = s++） {
    n++;
}

To be continued.

First Word

For BST it’s very important to do insert and delete (balancing not required).

Insertion is easy, but deletion is very difficult. However, it’s a good idea to at least know the principles.

Insert a node

Steps:

1. check whether new value = current node value. If not, proceed.

2. if new value is less, than:

   1. if current node has no left child, set left to new value, and return

   2. otherwise, go to left child and start over

3. if new value is greater, than:

   1. if current node has no right child, set right to new value

   2. otherwise, go to right child and start over

Note:

The BST may not be balanced after the insertion.

Code

Code snippet from this article

public boolean add(TreeNode node, int value) {
    if (value == node.val)
        return false;
    if (value < node.val) {
        if (node.left == null) {
            node.left = new TreeNode(value);
            return true;
        } else {
            return add(node.left, value);
        }
    } else if (value > node.val) {
        if (node.right == null) {
            node.right = new TreeNode(value);
            return true;
        } else {
            return add(node.right, value);
        }
    }
    return false;
}

Delete a node

Steps:

1. Find the node
2. Find the maximum node in the left subtree
3. Replace the node with the maximum node in the left subtree.

Special Cases:

1. The node doest have a left child.
2. The maximum node in the left subtree has a left child.
3. The node is the root of the tree

Code

The source code given by ninechap

private void myDeleteNode(TreeNode parent, TreeNode node) {
    if (node.left == null) {
        if (parent.right == node) {
            parent.right = node.right;
        } else {
            parent.left = node.right;
        }
    } else {
        TreeNode maxNodeParent = node;
        TreeNode maxNode = node.left;

        // find the maximum node in the left sub tree
        while (maxNode.right != null) {
            maxNodeParent = maxNode;
            maxNode = maxNode.right;
        }

        if (maxNodeParent.left == maxNode) {
            maxNodeParent.left = maxNode.left;
        } else {
            maxNodeParent.right = maxNode.left;
        }

        // move replacedNode to node
        maxNode.left = node.left;
        maxNode.right = node.right;
        if (parent.left == node) {
            parent.left = maxNode;
        } else {
            parent.right = maxNode;
        }
    }
}

private void findAndDelete(TreeNode parent, TreeNode node, int val) {
    if (node == null) {
        return;
    }
    if (node.val == val) {
        myDeleteNode(parent, node);
    } else if (node.val < val) {
        findAndDelete(node, node.right, val);
    } else {
        findAndDelete(node, node.left, val);
    }
}

public TreeNode deleteNode(TreeNode root, int val) {
    TreeNode dummyNode = new TreeNode(0);
    dummyNode.left = root;
    findAndDelete(dummyNode, root, val);
    return dummyNode.left;
}

A little bit on balancing

There are 2 ways to balance a tree. Most common method is tree rotation:

An AVL Trees means a self-balancing search trees. If balance gets out of range −1…+1, the subtree is rotated to bring into balance.

Second way is to convert tree into a linkedlist, then build the tree again (we have discussed this algorithm before, pick the middle element).

This method is slow if we insert and re-balance on each step, but we can do bulk insert/delete forgetting about the re-balancing for a while. This will make the data structure faster! more details