1. Binary Tree DFS Traversal

1.1 Recursion

This method will cost O(n) time with no extra space. The space is assigned by system(which could be O(1) or O(h), h is the height of the tree).

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    helper(root, result);
    return result;
}

private void helper(TreeNode root, ArrayList<Integer> result) {
    if(root == null) {
        return;
    }
    result.add(root.val);
    helper(root.left, result);
    helper(root.right, result);
}

1.2 Iteration

Use a stack to store the nodes. Pay attention to the order of storing. We store the right subtree node before the left one, so that we can get the preorder nodes when pop from the stack.
This method will cost O(n) time with O(h) extra space for the stack.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

 */
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(root == null) {
            return result;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if(cur.right != null) {
                stack.push(cur.right);
            }
            if(cur.left != null) {
                stack.push(cur.left);
            }
        }
        
        return result;
    }
}

Read More

Binary Search

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.
If the target number does not exist in the array, return -1.
Example:
If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int binarySearch(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1;
        }

        int start = 0;
        int end = nums.length - 1;
        while(start < end) {
            int mid = start + (end - start) / 2;
            if(nums[mid] >= target) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        return nums[start] == target ? start : -1;
    }
}

Key Points:

1. while(start < end): when start and end are overlapped each other, break. At this moment, we can return start or end. But it is different when we need to return the index before or after the target(see point 3).
2. int mid = start + (end - start) / 2: in order to avoid overflow of start + end, we need to do a little trick here.
3. while loop: in the while loop, there are two different needs:

• return the index of the target: as the example above.
• return the one before(example below)/after the target:
  Search Insert Position

  1 2 3 4 5 6 7 8 9 10

  while(start <= end) { int mid = start + (end - start) / 2; if(A[mid] == target) { return mid; } else if(A[mid] < target) { start = mid + 1; } else { end = mid - 1; } }

  Here, we need to use while(start <= end) so that when we break the loop, two pointers are at two different(but neighbored) positions. Besides, if we want to return the one before the index, we return start, otherwise we return end.

Read More

Coding Style

1. Leave blank space around each operations
2. Give meaningful names to parameters
3. Add space line between two logic blocks

For example, Implement strStr():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public String strStr(String haystack, String needle) {
        if(haystack.length() < needle.length()) {
            return null;
        }
        if(haystack == null || needle == null || needle.length() == 0) {
            return haystack;
        }

        for(int i = 0; i <= haystack.length() - needle.length(); i++) {
            boolean find = true;
            for(int j = 0; j < needle.length(); j++) {
                if(haystack.charAt(i + j) != needle.charAt(j)) {
                    find = false;
                    break;
                }
            }
            if(find == true) {
                return haystack.substring(i);
            }
        }

        return null;
    }
}

Tips: A well-known algorithm to solve this problem is using KMP. This method can run in O(m+n) time. But usually, during a 45 minutes interview, complete this O(m*n) method is enough. So, understanding what the point the interviewer asks is very important.

Think it in this way. If I were the interview:
This guy may be my potential colleague. Is there any bug here? Because if there are many bugs, I will probably debug a lot for him when we are in a team.
Is he talktive? Well, I will give you limited conditions about the problem and I hope you can ask me for more details. Also, to every question, pay attention to the boundry condition.

When we solve a coding problem

1. Pay attention to the boundry condition
2. Do communication during the writing part
3. When finished coding, do a test case no matter the interviewer request or not

Permutations Problems

Subsets:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> subset = new ArrayList<Integer>();
        Arrays.sort(S);
        helper(result, subset, 0, S);
        return result;
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> subset, int len, int[] S) {
        result.add(new ArrayList<Integer>(subset));
        for(int i = len; i < S.length; i++) {
            subset.add(S[i]);
            helper(result, subset,i + 1, S);
            subset.remove(subset.size() - 1);
        }
    }
}

Similar Problems:
SubsetsII
Permutations
PermutationsII
CombinationSum
Letter Combination of a Phone Number
Palindrome Partitioning
Restore IP address

Read More

This template is used for later markdown reference.

Fonts:

1
2
3
4
5

*Italics*
**Bold**
***Italics and Bold***
~~Scratch~~
It also works if you change the star(*) into underline(_).

Italics, Bold, Italics and Bold, Scratch

Link:

1

[My Website](http://kidchen.github.io/)

My Website

Reference:

Add “>“ before a line to express reference (add more “>“ to do nest).

This is a reference.

This is a nested reference.

Quote:

Say something.

For more information, visit this page.

Different subtitles:

Add one to six sharps(#) and a space before the head.

Head1

Head2

Head3

Head4

Head5

Head6

Codes:

Use “`“ around the inline code or use “```“ to define coding area.

This is an inline code.

1

code snippet

1

$ hexo new "My New Post"

List:

Use “*“, “+“ or “-“ followed with a space to express unordered list.

• unordered list

• nested unordered list

• nested unordered list

• nested unordered list

• nested unordered list

Use numbers followed with a dot and a space to express ordered list.

1. ordered list
2. ordered list
3. ordered list

Insert img:

1

![text](/path/to/your/img.jpg "option-title")

Miscellaneous：

Use three or more “*“, “-“ or “_“ to add divide line.
Note: There is no other characters in the divide line except spaces

Use “\“ as the escape character.

Use <!-- more --> to add “more” button.

A very nice Cheat Sheet for Markdown syntax.

Read More