Interview

(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:

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
26
27
28
29
30
31
32
33
34
35
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:

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
26
27
28
29
30
31
32
33
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;
    }
}

Similar Problems:
Partition List
Insertion Sort List
Reverse Nodes in k-group
Remove Node in Binary Search Tree
Copy List with Random Pointer
Swap Nodes in pairs

Read More

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

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

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

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

(Jan 21 2015) English>Interview 3 minutes read (About 393 words)

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

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×