[2018-Interview] Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Answer from Jiuzhang:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    private int findPosition(int[] arr, int start, int end, int key) {
        int i;
        for (i = start; i <= end; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;
    }

    private TreeNode myBuildTree(int[] inorder, int instart, int inend,
            int[] preorder, int prestart, int preend) {
        if (instart > inend) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[prestart]);
        int position = findPosition(inorder, instart, inend, preorder[prestart]);

        root.left = myBuildTree(inorder, instart, position - 1,
                preorder, prestart + 1, prestart + position - instart);
        root.right = myBuildTree(inorder, position + 1, inend,
                preorder, position - inend + preend + 1, preend);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder.length != preorder.length) {
            return null;
        }
        return myBuildTree(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
    }
}

[2018-Interview] Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

My answer: iterative solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        Set<TreeNode> visitedNodes = new HashSet<TreeNode>();
        stack.addLast(root);

        while(!stack.isEmpty()) {
            TreeNode current = stack.peekLast();
            if (current.left != null && !visitedNodes.contains(current.left)) {
                stack.addLast(current.left);
                continue;
            } 
            
                result.add(current.val);
                visitedNodes.add(current);
                stack.removeLast();
                if (current.right != null) {
                    stack.addLast(current.right);
                }
            
        }
        
        return result;
    }
}

Jiuzhang solution:

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: Inorder in ArrayList which contains node values.
     */
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        TreeNode curt = root;
        while (curt != null || !stack.empty()) {
            while (curt != null) {
                stack.add(curt);
                curt = curt.left;
            }
            curt = stack.pop();
            result.add(curt.val);
            curt = curt.right;
        }
        return result;
    }
}

[2018-Interview] Intersection of Two Linked Lists

Original question:
https://leetcode.com/problems/intersection-of-two-linked-lists/description/


My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // the core logic is to find length diff between headA and headB
        // assuming headA has N more elements than headB does
        // then move node currentB from beginning of headB and the currentA node from Nth element of headA
        if (headA == null || headB == null) {
            return null;
        }
        if (headA == headB) {
            return headA;
        }
        ListNode currentA = headA;
        ListNode currentB = headB;
        ListNode endA = null;
        ListNode endB = null;
        
        while (true) {
            if (currentB == null) {
                currentB = headA;
            }
            if (currentA == null) {
                currentA = headB;
            }
            
            if (currentA.next == null) {
                endA = currentA;
            }

            if (currentB.next == null) {
                endB = currentB;
            }

            if (endA != null && endB != null && endA != endB) {
                return null;
            }

            if (currentA == currentB) {
                return currentA;
            }
            
            currentA = currentA.next;
            currentB = currentB.next;
        }
    }
}

[2018-Interview] Odd Even Linked List

Original question: https://leetcode.com/problems/odd-even-linked-list/description/

My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null ) {
            return head;
        }
        ListNode evenHead = head.next;

        ListNode currentOdd = head;
        ListNode currentEven = head.next;
        while (currentOdd != null && currentEven != null && currentEven.next != null) {
            currentOdd.next = currentEven.next;
            currentEven.next = currentEven.next.next;
            currentOdd = currentOdd.next;
            currentEven = currentEven.next;
        }
        currentOdd.next = evenHead;
        return head;
    }
}

[2018-Interview] Add Two Numbers

Original question: https://leetcode.com/problems/add-two-numbers/description/

My answer:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        int addOne = (l1.val + l2.val) / 10;
        int newVal = (l1.val + l2.val) % 10;
        ListNode root = new ListNode(newVal);
        l1 = l1.next;
        l2 = l2.next;
        ListNode currentNode = root;
        while (l1 != null && l2 != null) {
            newVal = (l1.val + l2.val + addOne) % 10;
            addOne = (l1.val + l2.val + addOne) / 10;
            ListNode newNode = new ListNode(newVal);
            currentNode.next = newNode;
            currentNode = currentNode.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        ListNode remainNode = l1 == null? l2 : l1;
        while (addOne != 0) {
            int currentVal = 0;
            if (remainNode != null) {
                currentVal = remainNode.val;
            }
            newVal = (currentVal + addOne) % 10;
            addOne = (currentVal + addOne) / 10;
            ListNode newNode = new ListNode(newVal);
            currentNode.next = newNode;
            currentNode = currentNode.next;
            remainNode = remainNode != null? remainNode.next : null;
        }
        if (remainNode != null) {
            currentNode.next = remainNode;
        }
        return root;
    }
}

[2018-Interview] Increasing Triplet Subsequence

Original question: https://leetcode.com/problems/increasing-triplet-subsequence/description/

Got answers from Jiuzhang:

Answer 1: O(n) time, O(1) space

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {
            return false;
        }
        int[] preNums = new int[2];
        preNums[0] = nums[0];
        preNums[1] = Integer.MAX_VALUE;
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] <= preNums[0]) {
                preNums[0] = nums[i];
            } else if (nums[i] <= preNums[1]) {
                preNums[1] = nums[i];
            } else {
                return true;
            }
        }
        return false;
    }
}

Answer 2: O(n) time, O(n) space

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

// O(n) memory, if you want O(1)memory take a look at the c++ version
public class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums.length < 2)
            return false;
        int n = nums.length;
        boolean []has_first_small = new boolean[n];
        int smallest = nums[0];
        has_first_small[0] = false;
        for (int i = 0; i < n; i ++) {
            if (smallest < nums[i]) {
                has_first_small[i] = true;
            }
            smallest = Math.min(smallest, nums[i]);
        }
        
        int biggest = nums[n-1];
        for (int i = n-2; i >=0; i--) {
            if(has_first_small[i] == true) {
                if (nums[i] < biggest) {
                    return true;
                }
                biggest = Math.max(biggest, nums[i]);
            }
        }
        return false;
    }
}

[2018-Interview] Longest Palindromic Substring

Original question: https://leetcode.com/problems/longest-palindromic-substring/description/

My answer:

Used answer from Jiuzhang as reference:

https://www.jiuzhang.com/solutions/longest-palindromic-substring/

Answer 1: DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i ++) {
            isPalindrome[i][i] = true;
        }

        int maxLength = 1;
        int start = 0;
        
        for (int i = n - 2; i >= 0; i --) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt( i + 1);
            if (isPalindrome[i][i + 1] ) {
                start = i;
                maxLength = 2;
            }
        }

        for (int i = n - 1; i >= 0; i --) {// start from end; 
            // otherwise, if start from beginning, there won't be [i+1][j-1] for reference
            for (int j = i + 2; j < n; j ++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
                if (isPalindrome[i][j]) {
                    if (j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

Answer 2: try to find the longest palindrome with each point as center point

/**
* 本参考程序来自九章算法，由 @令狐冲 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0, len = 0, longest = 0;
        for (int i = 0; i < s.length(); i++) {
            len = findLongestPalindromeFrom(s, i, i);
            if (len > longest) {
                longest = len;
                start = i - len / 2;
            }
            
            len = findLongestPalindromeFrom(s, i, i + 1);
            if (len > longest) {
                longest = len;
                start = i - len / 2 + 1;
            }
        }
        
        return s.substring(start, start + longest);
    }
    
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            len += left == right ? 1 : 2;
            left--;
            right++;
        }
        
        return len;
    }
}

[2018-Interview] Longest Substring Without Repeating Characters

Original question: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

My answer:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int globalMaxLength = 1;
        int localMaxLength = 1;
        Map<Character, Integer> charIndex = new HashMap<Character, Integer>();
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() < 2) {
            return 1;
        }
        int l = 0;
        int r = 0;
        while (r < s.length()) {
            if (charIndex.containsKey(s.charAt(r)) && l <= charIndex.get(s.charAt(r))) {
                // l <= charIndex.get(s.charAt(r)), 

                // the opposite of l > charIndex.get(s.charAt(r)), 

                // which is good way to ignore the repeating char existed before
                globalMaxLength = Math.max(r - l, globalMaxLength);
                l = charIndex.get(s.charAt(r)) + 1;
            }
            charIndex.put(s.charAt(r), r);
            r ++;
        }
        globalMaxLength = Math.max(r - l, globalMaxLength);
        return globalMaxLength;
    }
}

[2018-Interview] Group Anagrams

Original question: https://leetcode.com/problems/group-anagrams/description/

My answer:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        if (strs == null || strs.length == 0) {
            return result;
        }
        
        Map<String, List<String>> stringAnagramMap = new HashMap<String, List<String>>();

        for (int i = 0; i < strs.length; i ++) {
            
            char[] charsOfStr = strs[i].toCharArray();
            Arrays.sort(charsOfStr);
            String sortedChar = String.valueOf(charsOfStr);
            
            if (!stringAnagramMap.containsKey(sortedChar)) {
                List<String> singleResult = new ArrayList<String>();
                stringAnagramMap.put(sortedChar, singleResult);
            }
            stringAnagramMap.get(sortedChar).add(strs[i]);
        }
        for (List<String> value : stringAnagramMap.values()) {
            result.add(value);
        }
        return result;
    }
}

[2018-Interview] Set Matrix Zeroes

Original question: https://leetcode.com/problems/set-matrix-zeroes/description/

My answer:

class Solution {
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        boolean originColumn = false; // if true, zero out the 0th column, used to avoid case where [i][0] is 0, while [0][0] is not
        boolean originRow = false; // if true, zero out the 0th row, used to avoid case where [0][j] is 0, while [0][0] is not
        if (matrix[0][0] == 0) {
            originColumn = true;
            originRow = true;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j ++) {
                // mark the index for 0s at row 0, and column 0
                if (matrix[i][j] == 0) {
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                        if (i == 0) {
                            originRow = true;
                        }
                        if (j == 0) {
                            originColumn = true;
                        }
                }
            }
        }
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 1; j < matrix[0].length; j ++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < matrix[0].length; j ++) {
            if (matrix[0][j] == 0) {
                for (int i = 1; i < matrix.length; i ++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (matrix[0][0] == 0) {
                if (originRow) {
                    for (int j = 1; j < matrix[0].length; j ++) {
                        matrix[0][j] = 0;
                    }                    
                }
                if (originColumn) {
                    for (int i = 1; i < matrix.length; i ++) {
                        matrix[i][0] = 0;
                    }                    
                }

        }
    }
}