algorithm

1. tree traversal

• depth-first-search, use stack

1. pre-order: root, left, right
2. in-order: left, root, right
3. post-order: left, right, root

• breadth-first-search, use queue

1. level-order: 1st level, 2nd level

2. pre-order

• check if root is empty or null
• display(root->data)
• preorder(root->left)
• preorder(root->right)

3. inorder

• check if root is empty or null
• inorder(root->left)
• display(root->data)
• inorder(root->right)

4. post-order

• check if root is empty or null
• postorder(root->left)
• postorder(root->right)
• display(root->data)

5. coding interview

• 'null' check
• use 'sorting'
• use 'map'
• use 'two index pointer'

6. two sum

    problem:
        find indices of two numbers such that they add to specific target value
        e.g. given nums = [2, 7, 11, 15], target = 9

    solution:
         1. use hashmap, while iterate array, store (9's complement of a[i], i)  to map, search map

         2. 双指针，一头一尾，sum小移头，sum大移尾

7. binary search

• edge case 1: array==null || array.length ==0
• edge case 2: target < min(array) || target > max(array)
• edge case 3: if it is not a perfect match, found index diff by either +1 or -1

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

        int left = 0, right = nums.length - 1;

        while(left < right){
            // Prevent (left + right) overflow
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) { return mid; }
            else if (nums[mid] < target) { left = mid + 1; }
            else { right = mid - 1; }
        }

        // End Condition: left > right
        return -1;
}

8. binary search tree

    public static boolean contains(Node root, int value) {
        if (root == null) {
            return false;
        } else if (root.value == value) {
                return true;
   
        } else if (value < root.value) {
            return contains(root.left, value);
        } else {
            return contains(root.right, value);
        }
    }

9. longest substring without repeating char

• use hashmap to store existing char and index 
• use sliding window to track current substring
• if duplicate char is found, update sliding window to the right of duplicate

10. merge two sorted array

    input:
    nums1 = [1,2,3,0,0,0], m = 3
    nums2 = [2,5,6],       n = 3

    output: [1,2,2,3,5,6]

    public void merge(int a[], int m, int b[], int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

while (i >= 0 && j >= 0) {
            if (a[i] > b[j])
                a[k--] = a[i--];
            else
                a[k--] = b[j--];
            }
        while (j >= 0)
                a[k--] = b[j--];
    }

11. leetcode: https://www.youtube.com/watch?v=qg0CY00qJqI&list=PLi9RQVmJD2fYXgBAUfaN5MXgYPUTbzqeb&index=6

reference
1. cracking the coding interview.pdf
2. tree traversal, preorder, inorder, postorder

3. mtu interview with google

4. blog get job at google

5. Steven Skiena's The Algorithm Design Manual.