Interview Note - Graph & Search

Jan 29 2015 (Jan 29 2015) English>Interview 7 minutes read (About 1048 words)

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
 * };
 */
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if(node == null) {
            return null;
        }

        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));

        while(!queue.isEmpty()) {
            UndirectedGraphNode cur = queue.poll();
            for(int i = 0; i < cur.neighbors.size(); i++) {
                // !!! if node not in map, add a new node into the map !!!
                if(!map.containsKey(cur.neighbors.get(i))) {
                    map.put(cur.neighbors.get(i), new UndirectedGraphNode(cur.neighbors.get(i).label));
                    queue.offer(cur.neighbors.get(i));
                }
                // now we are sure that the node is existed, add the neighbors to the value
                map.get(cur).neighbors.add(map.get(cur.neighbors.get(i)));
            }
        }

        return map.get(node);
    }
}

Topological Sorting
DFS: O(n) time with O(n) space for the map and the result.

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        if(graph == null || graph.size() == 0) {
            return result;
        }
        // construct map with all nodes
        HashMap<DirectedGraphNode, Integer> map = new HashMap<DirectedGraphNode, Integer>();
        for(DirectedGraphNode node: graph) {
            // mark 0 as unsorted
            map.put(node, 0);
        }
        // find a new unsorted node to start sorting (if possible):
        while (hasUnsorted(map, graph)) {
            DirectedGraphNode node = null;
            for (DirectedGraphNode temp : graph) {
                if (map.get(temp) == 0) {
                    node = temp;
                }
            }
            // get the node and do sort(search):
            sort(map, graph, result, node);
        }
        return result;
    }
    
    // check if there is any node that not yet been sorted
    public boolean hasUnsorted(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph){
        for (DirectedGraphNode node : graph) {
            if (map.get(node) == 0) {
                return true;
            }
        }
        return false;
    }
    
    // search and sort the graph
    public void sort(Map<DirectedGraphNode, Integer> map, ArrayList<DirectedGraphNode> graph, ArrayList<DirectedGraphNode> result, DirectedGraphNode node){
        if (map.get(node) != 0) {
            // if 1: System.out.println("It is not a DAG");
            // if 2: sorted
            return;
        }
        // mark 1 as visited(not yet been sorted), do with its neighbors:
        map.put(node, 1);
        for (DirectedGraphNode next : node.neighbors) {
            sort(map, graph, result, next);
        }
        // mark 2 as sorted
        // map.put(node, 2);
        result.add(0, node);
    }
}

Interview Note - Dynanmic Programming

Jan 25 2015 (Jan 25 2015) English>Interview 8 minutes read (About 1184 words)

1. Dynamic Programming

A method for solving a complex problem by breaking it down into a collection of simpler sub-problems.

1.1 When to use

One of the following three:

Maximum/Minimum Problem
Yes or No Question
Count all possible solutions

Can’t do sort or swap operation

Note: DP can’t return all results, it only returns max/min, yes/no or a certain value(like length, possible solutions, etc.).

1.2 How to think

States: what we need to store for each sub-problem (usually an array).
Function: what is the relationship between each state.
Intialization: what is the start of each state.
Answer: what is the end of each state.

Example: Number Triangle
We use an array f[i][j] to record the minimum sum from (0, 0) to (i, j). For a certain (i, j), we know it is either from (i - 1, j - 1) or (i - 1, j). So the sub-problem is to traverse all elements in the triangle and calculate all the f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + T[i]][j]. The result will be the minimum one in f[n - 1][0, ..., n - 1].
We can also do it from bottom up. First we find the minimum of each pair in the last row, then we do above similarly but from bottom up. Finally the only one element left in the array is the result we are looking for.
A bonus point is doing this using only O(n) extra space, where n is the total number of rows in the triangle. Since each time we calculate f[i][j], the result is only related with f[i - 1][], we can only use 1D array and update the elements in it in each for loop.
Here is the code from bottom up with O(n) space cost.

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) {
            return 0;
        }

        int[] result = new int[triangle.size() + 1];
        
        for(int row = triangle.size() - 1; row >= 0; row--) {
            for(int col = 0; col <= row; col++) {
                result[col] = Math.min(result[col], result[col + 1]) + triangle.get(row).get(col);
            }
        }
        
        return result[0];
    }
}

Dynamic Programming uses extra space to remember the mid-result. So that it is more efficient than recursive searching, which may repeated calculate the same mid-result for many times. In the above example, if we do a brute force search, it cost O(2^n) time, where n is the height of the triangle (each row, we need to choose one from two, totally n rows). But it only costs O(n^2) in theoretical(m rows, each row has n elements, totally n^2) or O(n), which means all numbers we only need to visit once.

Interview Note - Linked List

Jan 24 2015 (Jan 24 2015) English>Interview 6 minutes read (About 857 words)

1. Introduce Dummy Node

When the head of the target list we want to return may be different from the original given list, we can use a dummy node linked to the result so that we can get what we want by calling dummy.next.

Remove Duplicates from Sorted List II:

public class Solution {
    public static ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        ListNode cur = head;
        int dup = Integer.MIN_VALUE;

        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                dup = cur.val;
                while(cur.val == dup) {
                    cur = cur.next;
                    // if the rest of elements are all the same
                    if(cur == null) {
                        return dummy.next;
                    }
                }
            } else {
                pre.next = cur;
                pre = pre.next;
                cur = cur.next;
                // add null to pre.next: in case the rest of elements are the same and returned above
                pre.next = null;
            }
        }
        // add the last element (since cur.next != null skip this element)
        pre.next = cur;

        return dummy.next;
    }
}

Reverse Linked List II:

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) {
            return head;
        }

        // find the m position node
        int count = 1;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        while(count < m) {
            pre = pre.next;
            count++;
        }

        // do the reverse: pre-> reverse[first->cur->next] ...
        ListNode first = pre.next;
        ListNode cur = pre.next.next;
        while(count < n) {
            ListNode next = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = next;
            count++;
            if(count == n) {
                first.next = next;
            }
        }

        return dummy.next;
    }
}

Interview Note - Binary Tree

Jan 23 2015 (Jan 23 2015) English>Interview 6 minutes read (About 953 words)

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).

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.

 */
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;
    }
}

Interview Note - Binary Search & Sorted Array

Jan 22 2015 (Jan 22 2015) English>Interview 6 minutes read (About 854 words)

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.

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:

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).
int mid = start + (end - start) / 2: in order to avoid overflow of start + end, we need to do a little trick here.
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

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.