# FB Week3

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
nLogn

[-4, -1, -1, 0, 1, 1]
(F) (L) (H)
fixed num: -1
low: -1
high: 2
temp = -4 + 1 + 2

 public  List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res  = new HashSet<>();
        if(nums.length==0) return new ArrayList<>(res);
        Arrays.sort(nums);
        for(int i=0; i<nums.length-2;i++){
            int j =i+1;
           int  k = nums.length-1;
            while(j<k){
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==0)res.add(Arrays.asList(nums[i],nums[j++],nums[k--]));
                else if ( sum >0) k--;
                else if (sum<0) j++;
            }

        }
        return new ArrayList<>(res);

    }

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.

call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

// 1,2,3,4,5,6
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int min = 1;
        int max = n;
        
        while(min < max) {
            int mid = min + (max - min) / 2;
            if (isBadVersion(mid)) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        
        // here
        
        
        return min;
    }
}

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:
Input: [[7,10],[2,4]]
Output: 1

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
    }
}

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List<Node> neighbors;
}

Test case format:

For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

if (map.containsKey(label)) {
return node;
}
map.put(2, nodeOf2)

cloneNode(1)
for(node1.neighbors) {
cloneNode.neighbors.add(cloneGraph(node1.neighbor))
}

return cloneNode;

1 - 2
| |
3 - 4

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/

class Solution {
    private Map<Integer, Node> map = new HashMap();
    
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        
        if (map.containsKey(node.val)) {
            return map.get(node.val);
        }
        
        Node cloneNode = new Node(node.val);
        map.put(node.val, cloneNode);
        for (Node n: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(n));
        }
        
        return cloneNode;
    }
}

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> map = new HashMap<>();
        
        queue.offer(node);
        map.put(node, new Node(node.val));
        
        while (!queue.isEmpty()) {
            Node currNode = queue.poll();
            map.get(currNode).neighbors = new ArrayList<>();
            for (Node neighbor : currNode.neighbors) {
                if (!map.containsKey(neighbor)) {
                    map.put(neighbor, new Node(neighbor.val));
                    queue.offer(neighbor);
                }
                map.get(currNode).neighbors.add(map.get(neighbor));
            }
        }
        
        return map.get(node);
    }
}

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input:
11110
11010
11000
00000
Output: 1

Example 2:
Input:
00000
00000
00000
00000
Output: 3

class Solution {
  
    public int numIslands(char[][] grid) {
    
        int result = 0;
    
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    helper(grid, i, j, grid[0].length, grid.length);
                    result++;
                }
            }
        }
        
      return result;
    }
    
    public void helper(char[][] grid, int x, int y, int height, int width) {
        if (x < 0 || x >= width || y < 0 || y >= height || grid[x][y] == '0') {
            return;
        }
        
        grid[x][y] = '0';
        helper(grid, x + 1, y, height, width);
        helper(grid, x - 1, y, height, width);
        helper(grid, x, y + 1, height, width);
        helper(grid, x, y - 1, height, width);
    }
}

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

root
/ / |
b d m
a a a
d d d

class WordDictionary {

    class TrieNode {
        String item = "";
        TrieNode[] children = new TrieNode[26];
    }

    /** Initialize your data structure here. */
    
    private TrieNode root = new TrieNode();
    
    public WordDictionary() {
        
    }
    
    /** Adds a word into the data structure. */
    public void addWord(String word) {
        TrieNode node = root;
        for (char c: word.toCharArray()) {
            if (node.children[c - 'a'] == null) {
                node.children[c - 'a'] = new TrieNode();
            } 
            node = node.children[c - 'a'];
        }
        node.item = word;
    }
    
    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        
    }
    
    private boolean match(char[] chs, int k, TrieNode node) {
        if (k == chs.length) return !("".equals(node.item));
        
        if (chs[k] != '.') {
            return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
        } else {
            for (int i = 0; i < node.children.length; i++) {
                if (node.children[i] != null) {
                    if (match(chs, k + 1, node.children[i])) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists==null || lists.length==0) return null;
        
        PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length, (a,b) -> a.val - b.val);
        
        ListNode dummy = new ListNode(0);
        ListNode tail=dummy;
        
        // pq: 
        // 0 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
                                                 tail
        for (ListNode node:lists) {
           if (node!=null) {
              queue.add(node); 
           }
        }
         
        while (!queue.isEmpty()){
            tail.next=queue.poll();
            tail=tail.next;
            
            if (tail.next!=null)
                queue.add(tail.next);
        }
        return dummy.next;
    }
}

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Example 1:

Input: "42"
Output: 42
Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.
Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

1. string is empty
2. string included empty
3. sign(+/-)
4. convert string to int and avoid overflow

" -42"
index = 3

class Solution {
    public int myAtoi(String str) {
        // 1. string is empty
        if (str.length() == 0) return 0;
        
        // 2. string with whitespace
        int index = 0;
        while(index < str.length() && str.charAt(index) == ' '){
            index++;
        }
        
        if (str.length() == index) return 0;

        
        // 3. sign
        int sign = 1;
        if (str.charAt(index) == '+' || str.charAt(index) == '-') {
            sign = str.charAt(index) == '+' ? 1 : -1;
            index++;
        }
        
        // 4. convert string to int and avoid overflow
       int total = 0;
       while(index < str.length()) {
            int digital = str.charAt(index) - '0';
            
            if (digital > 9 || digital < 0) {
                break;
            }
            
            if (total > Integer.MAX_VALUE / 10 || (total == Intger.MAX_VALUE / 10 && digital > Integr.MAX_VALUE % 10)) {
                return sign == 1 ? Integr.MAX_VALUE : Integr.MIN_VALLUE;
            }
            
            total = total * 10 + digital;
            index++;
        }
        
        return total * sign;
    }
}

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

l r -> (l < r)
aba

l r
abca
lr
abca

isPalinromic(l + 1, r) || isPalinromic(l, r - 1)

public boolean validPalindrome(String s) {
    int l = 0;
    int r = s.length() - 1;
    while(l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return isPalindromic(s, l + 1, r) || isPalindromic(s, l, r - 1);
        }
        l++;
        r--;
    }
    return true;
}

public boolean isPalindromic(String s, int l, int r) {
    while(l < r) {
        if (s.charAt(l) != s.charAt(r)) {
            return false;
        }
        l++;
        r--;
    }
    return true;
} 

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Example 3:
Input: [10,9,20,null,null,15,7]

    10
   / \
  9  20
    /  \
   15   7

Output: 54

Example 3:
Input: [10,9,20,null,null,15,7]

        10
       /  \
      9   20
     /  \
    15   7

Output: 54

class Solution {
    int result;
    
    public int maxPathSum(TreeNode root) {
        result = Integer.MIN_VALUE;
        helper(root);
        return result;
    }
    
    public int helper(TreeNode node) {
        if (node == null) return 0;
        
        int left = Math.max(0, helper(node.left));
        int right = Math.max(0, helper(node.right));
        result = Math.max(result, left + right + node.val);
        return Math.max(left, right) + node.val;
    }
}