拼扯惹斯特

迎难而上，祝我好运。面朝大海，春暖花开。

2018.8.9

269. alien-dictionary x3

• 给一个按照某种外星人字典序排好序的String数组，只包含小写字母，求这些出现过的字母的顺序。若有多种可能（平级）则任意顺序均可。
• topo排序问题，前后两个字符串逐个字符找到第一对不同的字符，确定先后顺序（前->后）构成一条边，两两字符串全部遍历完之后就形成了一个graph。维护一个inDegree，每次BFS时从入度为0的节点出发，将它可达的所有邻接点的入度都减1（删掉这些边），最后如果全部字符都遍历到了即可。如果出现了环，则一定会又入度不为0的点残留。

class Solution {
    public String alienOrder(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        Map<Character, Set<Character>> graph = new HashMap<>();
        Map<Character, Integer> inDegree = new HashMap<>();
        initInDegree(words, inDegree);
        buildGraph(words, graph, inDegree);
        Queue<Character> q = new LinkedList<>();
        for (char c : inDegree.keySet()) {
            if (inDegree.get(c) == 0) {
                q.offer(c);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char c = q.poll();
            sb.append(c);
            if (graph.containsKey(c)) {
                Set<Character> neighbors = graph.get(c);
                for (char neighbor : neighbors) {
                    inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                    if (inDegree.get(neighbor) == 0) {
                        q.offer(neighbor);
                    }
                }
            }
        }
        if (sb.length() != inDegree.size()) {
            return "";
        }
        return sb.toString();
    }
    private void initInDegree(String[] words, Map<Character, Integer> inDegree) {
        for (String word : words) {
            for (char c : word.toCharArray()) {
                inDegree.put(c, 0);
            }
        }
    }
    private void buildGraph(String[] words, Map<Character, Set<Character>> graph, Map<Character, Integer> inDegree) {
        for (int i = 1; i < words.length; i++) {
            String prev = words[i - 1];
            String curr = words[i];
            int len = Math.min(prev.length(), curr.length());
            for (int j = 0; j < len; j++) {
                char c1 = prev.charAt(j);
                char c2 = curr.charAt(j);
                if (c1 != c2) {     // 找到第一个不同的字母
                    graph.putIfAbsent(c1, new HashSet<Character>());
                    if (graph.get(c1).add(c2)) {
                        inDegree.put(c2, inDegree.get(c2) + 1);
                    }
                    break;
                }
            }
        }
    }
}

271. encode-and-decode-strings

• 实现encode和decode函数，将字符串List和单一条字符串互相转换。
• 字符含有哪些？（所有ASCII字符都可能出现）
• 由于每个符号都有可能出现，所以不能想着用某个特殊符号来拼接和拆分。因此需要额外的信息进行标记，这里用的是在/之前加上所跟字符串的长度的方式，decode时每次从特定位置开始找/，然后取出它前面的长度信息直接截取后面的子字符串。

public class Codec {
    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for (String str : strs) {
            sb.append(str.length()).append("/").append(str);    // 长度 + / + 字符串内容
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ans = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int index = s.indexOf("/", i);  
            int len = Integer.valueOf(s.substring(i, index));
            ans.add(s.substring(index + 1, index + 1 + len));
            i = index + 1 + len;
        }
        return ans;
    }
}

2018.8.4 电面

• 给一个n，返回所有可能的factor组合。lc 254 x2

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> ans = new ArrayList<>();
    if (n < 4) {
        return ans;
    }
    getFactors(n, 2, new ArrayList<Integer>(), ans);
    return ans;
}
private void getFactors(int n, int start, List<Integer> path, List<List<Integer>> ans) {
    if (n <= 1) {   // 已经除尽了，说明没有更多factor
        if (path.size() > 1) {  // 当前path就是一路走过来用过的factor
            ans.add(new ArrayList<Integer>(path));
        }
        return;
    }
    for (int i = start; i <= n; i++) {
        if (n % i == 0) {   // 可以整除，说明i是n的一个factor
            path.add(i);    // 将i加入path，将n除掉i，再递归从i开始继续往后找大于等于i的factor
            getFactors(n / i, i, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

2018.9.14 Onsite

• 给一个连接关系{A - > B; B - > A,C; C - > B; D - > E; E -> D}，group这些node并返回这些group：[(A,B,C), (D,E)].

public static List<List<Node>> getGroups(Map<Node, List<Node>> graph) {
    if (graph == null) {
        return null;
    }
    Set<Node> nodeSet = new HashSet<>();
    for (Node key : graph) {
        nodeSet.add(key);
        for (Node neighbor : graph.get(key)) {
            nodeSet.add(neighbor);
        }
    }
    List<List<Node>> ans = new ArrayList<>();
    while (!nodeSet.isEmpty()) {
        List<Node> group = new ArrayList<>();
        Iterator<Node> it = nodeSet.iterator();
        dfs(it.next(), graph, nodeSet, group);
        ans.add(group);
    }
    return ans;
}
private void dfs(Node curr, Map<Node, List<Node>> graph, Set<Node> nodeSet, List<Node> group) {
    group.add(curr);
    nodeSet.remove(curr);   // 移除表示已访问
    List<Node> neighbors = graph.get(curr);
    if (neighbors == null) {
        return;
    }
    for (Node neighbor : neighbors) {
        if (nodeSet.contains(neighbor)) {
            dfs(neighbor, graph, nodeSet, group);
        }
    }
}

425. word-squares x2

• 给一个wordList，将List中的String放入matrix中使得行、列的单词都来自于这个List。
• Trie + DFS，对于每个Trie节点，除了正常的nexts数组、isWord布尔值，额外维护一个List保存以「到达当前TrieNode路径」为prefix的所有word。固定一个word之后，下一个词的prefix可以通过纵向append得到，具体规律见这个discussion.

class Solution {
    class TrieNode {
        TrieNode[] nexts;
        List<String> prefixWords;
        boolean isWord;
        public TrieNode() {
            nexts = new TrieNode[26];
            prefixWords = new ArrayList<>();
            isWord = false;
        }
    }
    class Trie {
        TrieNode root;
        public Trie(String[] words) {
            root = new TrieNode();
            for (String word : words) { 
                TrieNode curr = root;
                for (int i = 0; i < word.length(); i++) {
                    int index = word.charAt(i) - 'a';
                    if (curr.nexts[index] == null) {
                        curr.nexts[index] = new TrieNode();
                    }
                    curr.prefixWords.add(word);
                    curr = curr.nexts[index];
                }
                curr.isWord = true;
            }
        }
        
        public List<String> getByPrefix(String prefix) {
            List<String> ans = new ArrayList<>();
            TrieNode curr = root;
            for (int i = 0; i < prefix.length(); i++) {
                int index = prefix.charAt(i) - 'a';
                if (curr.nexts[index] == null) {
                    return ans;
                }
                curr = curr.nexts[index];
            }
            ans.addAll(curr.prefixWords);
            return ans;
        }
    }
    private void dfs(int len, Trie trie, List<List<String>> ans, List<String> curr) {
        if (curr.size() == len) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        int index = curr.size();
        StringBuilder prefix = new StringBuilder();
        for (String s : curr) {
            prefix.append(s.charAt(index));
        }
        List<String> candidates = trie.getByPrefix(prefix.toString());
        for (String candidate : candidates) {
            curr.add(candidate);
            dfs(len, trie, ans, curr);
            curr.remove(curr.size() - 1);
        }
    }
    
    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> ans = new ArrayList<>();
        if (words == null || words.length == 0) {
            return ans;
        }
        int len = words[0].length();
        Trie root = new Trie(words);
        List<String> curr = new ArrayList<>();
        for (String word : words) {
            curr.add(word);
            dfs(len, root, ans, curr);
            curr.remove(curr.size() - 1);
        }
        return ans;
    }
}

2018.4 Onsite

index sum

• 一个array自己跟自己的element可以组成一个pair，这个pair有个sum，求the kth sum分别对应的index。应该类似于lc 215 k-th element吧，只不过需要多存一个index作为返回。
• 方法一：PriorityQueue维护top K元素即可。

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < nums.length; i++) {
        pq.offer(nums[i]);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

• 方法二：quickSelect，用快排的partition来找到元素。

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    shuffle(nums);
    int lo = 0, hi = nums.length - 1;
    k = nums.length - k;    // 转换成第k小的
    while (lo < hi) {
        int j = partition(nums, lo, hi);
        if (j == k) {
            break;
        } else if (j < k) { // 说明第k小的还在后面
            lo = j + 1;
        } else {    // 说明第k小的还在前面
            hi = j - 1;
        }
    }
    return nums[k];
}
private int partition(int[] nums, int lo, int hi) {
    int i = lo, j = hi + 1;
    while (i < j) {
        while (nums[++i] < nums[lo]) {
            if (i == hi) {
                break;
            }
        }
        while (nums[--j] > nums[lo]) {
            if (j == lo) {
                break;
            }
        }
        if (i >= j) {
            break;
        }
        swap(nums, i, j);
    }
    swap(nums, lo, j);
    return j;
}
public void shuffle(int[] arr) {
    Random r = new Random();
    for (int i = 0; i < arr.length; i++) {
        swap(arr, i, r.nextInt(i + 1));
    }
}
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

463. island-perimeter x2

• 给一个0/1二维矩阵，求其中为1的island的周长。
• 方法一：BFS，每个1都先算它有四条边，然后根据邻接情况减掉不是边的即可。

class Solution {
    public int islandPerimeter(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        int perimeter = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    perimeter += bfs(grid, i, j, visited);
                }
            }
        }
        return perimeter;
    }
    private int[][] dirs = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private int bfs(int[][] grid, int i, int j, boolean[][] visited) {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {i, j});
        visited[i][j] = true;
        int perimeter = 0;
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            perimeter += 4;
            for (int[] dir : dirs) {
                int row = curr[0] + dir[0], col = curr[1] + dir[1];
                if (isIsland(grid, row, col)) {
                    perimeter--;
                    if (!visited[row][col]) {
                        q.add(new int[] {row, col});
                        visited[row][col] = true;
                    }
                }
            }
        }
        return perimeter;
    }
    private boolean isIsland(int[][] grid, int i, int j) {
        return i >= 0 && i < grid.length
            && j >= 0 && j < grid[0].length
            && grid[i][j] == 1;
    }
}

• 方法二：找规律。对于每一个1的cell，看它的下方和右方neighbor是不是1，记录neighbor数，最后周长就是islands * 4 - neighbours * 2。

public int islandPerimeter(int[][] grid) {
    int islands = 0, neighbours = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] == 1) {
                islands++; // count islands
                if (i < grid.length - 1 && grid[i + 1][j] == 1) neighbours++; // count down neighbours
                if (j < grid[i].length - 1 && grid[i][j + 1] == 1) neighbours++; // count right neighbours
            }
        }
    }

    return islands * 4 - neighbours * 2;
}

2018.9 Onsite

permutation系列

• Permutations(无重复元素全排列)

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, boolean[] used) {
   if (tempList.size() == nums.length) {
      list.add(new ArrayList<>(tempList));
   } else {
      for (int i = 0; i < nums.length; i++) { 
         if (used[i]) continue;
         tempList.add(nums[i]);
         used[i] = true;
         backtrack(list, tempList, nums);
         used[i] = false;
         tempList.remove(tempList.size() - 1);
      }
   }
}

• Permutations(有重复元素全排列)

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, boolean[] used) {
    if (tempList.size() == nums.length) {
        list.add(new ArrayList<>(tempList));
    } else {
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            tempList.add(nums[i]);
            used[i] = true; 
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

2016.8 onsite

Letter Combinations of a Phone Number with isWord() API

• 和lc 17 Letter Combinations of a Phone Number类似，但会多给一个isWord()的API，需要判断生成的word是否在dict中。

final char[][] num2Char = new char [][] {
    {}, 
    {}, 
    {'a', 'b', 'c'}, 
    {'d', 'e', 'f'}, 
    {'g', 'h', 'i'},
    {'j', 'k', 'l'}, 
    {'m', 'n', 'o'}, 
    {'p', 'q', 'r', 's'},
    {'t', 'u', 'v'}, 
    {'w', 'x', 'y', 'z'}
};

// 判断是否在给定的dict中
// public boolean isWord(String word);

public List<String> letterCombinations(String digits) {
    List<String> ans = new ArrayList<>();
    if (digits == null || digits.length() == 0 
        || digits.indexOf('1') >= 0 || digits.indexOf('0') >= 0) {
        return ans;
    }
    char[] str = digits.toCharArray();
    dfs(str, 0, num2Char, new StringBuilder(), ans);
    return ans;
}
private void dfs(char[] str, int index, final char[][] num2Char,
                    StringBuilder sb, List<String> ans) {
    if (index == str.length && isWord(sb.toString())) {
        ans.add(sb.toString());
        return;
    }
    int temp = str[index] - '0';
    for (int i = 0; i < num2Char[temp].length; i++) {
        sb.append(num2Char[temp][i]);
        dfs(str, index + 1, num2Char, sb, ans);
        sb.deleteCharAt(sb.length() - 1);
    }
}

Duplicate Files in directory

• 给一个文件目录，设计一个方法能够找出该目录下（包括子目录）所有的duplicate files（文件内容一样但文件名不一定一样），
• 先DFS把所有file找出来，然后用MD5哈希值作为Map的key、file的Set作为value，将相同key的Set中的文件两两比较，防止是不同文件因为collision而放到这里。
• 但如果目录中只有少量的重复文件也要全部扫一遍算MD5，这样很不划算。因此考虑利用文件大小来归类，然后只有文件大小相同的才有可能出现duplicate，但这样可能还是要计算很多个相同文件大小的MD5。
• 再考虑是不是可以不求整个文件的MD5，而是只取一部分来MD5求哈希作为key（例如前1k个bytes），然后对于size > 1的组再根据[1k + 1, 2k]部分内容求MD5.这样如果只有少量的dulicate，通过这样拆分求key在前面几步就会把大量文件给排除了，后面求MD5的时候就少很多了。

走到0

• 可能类似于lc 457 ，但是不是找loop，也不要求移动方向一致，只是找是否存在arr[index] == 0。直接用Set存走过的index即可。或者也可以快慢指针，每次判断快指针是否指向了一个0即可，若快慢指针相遇都没有遇到0，说明不存在。

public boolean hasZero(int[] nums, int start) {
    if (nums == null || nums.length == 0 || start < 0 || start >= nums.length) {
        return false;
    }
    if (nums[start] == 0) { // 防止一个元素的时候slow == fast进不去while-loop
        return true;
    }
    int n = nums.length, slow = start, fast = getNextIndex(start, nums[start], n);
    while (slow != fast) {
        if (nums[slow] == 0 || nums[fast] == 0) {
            return true;
        }
        slow = getNextIndex(slow, nums[slow], n);   // 慢快指针分别移动一步两步
        fast = getNextIndex(fast, nums[fast], n);
        fast = getNextIndex(fast, nums[fast], n);
    }
    return false;
}
private int getNextIndex(int index, int step, int len) {
    int nextIndex = index + step;
    return nextIndex >= 0 ? nextIndex % len : nextIndex % len + len; // java的%求的是余数而不是真正的modulo
}

merge K sorted list

• 可以直接把元素通通存入PriorityQueue，然后从头取元素即可。或者用分治法递归来搞，

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    // last two params are used for dividing into sub problems
    return mergeKLists(lists, 0, lists.length);
}

private ListNode mergeKLists(ListNode[] lists, int start, int end) {
    if (end - start == 1) { // only one list
        return lists[start];
    } else if (end - start == 2) {  // merge two lists
        return mergeTwoLists(lists[start], lists[start + 1]);
    } else {
        int mid = start + (end - start) / 2;
        // cut into first and second halves
        return mergeTwoLists(mergeKLists(lists, start, mid), 
                                mergeKLists(lists, mid, end)); // warning not mid + 1
    }
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

2018.4 Onsite x2

battle ship游戏

• lc有个算battleship个数的，直接O(NM)求第一次出现的ship坐标即可。但游戏应该是给一个坐标进行轰炸，如果反复调用O(NM)太慢了，可以考虑存坐标-船的map，这样就是O(1)了。

277. find-the-celebrity x2

• 给一个API函数判断i是否认识j，celebrity的定义是在n个人中，n-1个人都认识他、他却完全不认识他们。
• naive方法是O(n^2)搞定，对于每个人，一旦他认识别人、或者别人不认识他就跳出循环。

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */
public class Solution extends Relation {
    public int findCelebrity(int n) {
        for (int i = 0; i < n; i++) {
            boolean found = true;
            for (int j = 0; j < n; j++) {
                if (j == i) {
                    continue;
                }
                if (!knows(j, i) || knows(i, j)) {  // 看别人是否都认识i且i完全不认识别人
                    found = false;
                    break;
                }
            }
            if (found) {
                return i;
            }
        }
        return -1;
    }
}

• 更巧妙的办法，从头开始一个pass，判断如果i认识j则把candidate设为j，如果i不认识j则j不可能是candidate；完了之后再一个pass看这个candidate是不是不认识所有人、且所有人都认识他。

public int findCelebrity(int n) {
    int candidate = 0;      // 先假设第一个人是名人
    for (int i = 1; i < n; i++) {   // 他认识别人就，把他排除掉了
        if (knows(candidate, i)) candidate = i;
    }
    for (int i = 0; i < n; i++) {   // 确认他是否认识某个人或者某个人不认识他，那他也不是名人
        if (i != candidate && (knows(candidate, i) || !knows(i, candidate))) return -1;
    }
    return candidate;
}

759. employee-free-time

• 给一个List of List，每一个子List存放每个employee的工作时间，求所有employee的共同空闲时间。没有则返回空List。
• 直接将List flatten，然后按照工作开始时间从小到大排序，再往后依次取工作时间，若当前开始时间比之前的结束时间长，说明出现了空闲时间；否则需要更新prev的end，保证prev的结束时间cover到所有结束时间，即取max。

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    List<Interval> ans = new ArrayList<>();
    if (schedule == null || schedule.size() == 0) {
        return ans;
    }
    List<Interval> workingTimes = new ArrayList<>();
    schedule.forEach(e -> workingTimes.addAll(e));
    Collections.sort(workingTimes, (a, b) -> a.start - b.start);
    Interval prev = workingTimes.get(0);
    for (int i = 1; i < workingTimes.size(); i++) {
        if (workingTimes.get(i).start > prev.end) {
            ans.add(new Interval(prev.end, workingTimes.get(i).start));
            prev = workingTimes.get(i);
        } else {
            prev.end = Math.max(prev.end, workingTimes.get(i).end);
        }
    }
    return ans;
}

求出现次数多于n/4的元素

• 169. majority-element是求n/2、229. majority-element-ii是求n/3。区别是这些给的都不是sorted array. 这题已经排序了，可以想到的是用两个相隔n/4的指针，若两端元素相等说明存在n/4 + 1个相同元素，这个就是其中一个答案了。

2018.5 Oniste

blacklist of words

• scan 某个query里面存不存在blacklist里面的word。借此机会复习一下trie吧。

class Trie {
    class TrieNode {
        boolean isWord;
        TrieNode[] next;
        public TrieNode() {
            isWord = false;
            next = new TrieNode[26];
        }
    }
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    public void insert(String word) {
        if (word == null || word.length() == 0) {
            return;
        }
        char[] wordChar = word.toCharArray();
        TrieNode curr = root;
        for (int i = 0; i < wordChar.length; i++) {
            int index = wordChar[i] - 'a';
            if (curr.next[index] == null) {
                curr.next[index] = new TrieNode();
            }
            curr = curr.next[index];
        }
        curr.isWord = true;
    }
    public boolean search(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        char[] wordChar = word.toCharArray();
        TrieNode curr = root;
        for (int i = 0; i < wordChar.length; i++) {
            int index = wordChar[i] - 'a';
            if (curr.next[index] == null) {
                return false;
            }
            curr = curr.next[index];
        }
        return curr.isWord;
    }
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return false;
        }
        char[] prefixChar = prefix.toCharArray();
        TrieNode curr = root;
        for (int i = 0; i < prefixChar.length; i++) {
            int index = prefixChar[i] - 'a';
            if (curr.next[index] == null) {
                return false;
            }
            curr = curr.next[index];
        }
        return true;
    }
}

2018.3 Onsite x2

Longest increasing path in the binary tree

• 具体题意不明，可能是从root到leaf的上升序列（类似lc 298），或者是可以转折的（类似lc 549）。

class Solution {    // 从上到下的单向路径
    private int max = 0;
    public int longestConsecutive(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int len = 1;    // 以当前节点结束，则长度为1
        int left = helper(root.left), right = helper(root.right);
        if (root.left != null && root.left.val == root.val + 1) {
            len = left + 1; // 根据孩子节点val判断长度是否累加
        }
        if (root.right != null && root.right.val == root.val + 1) {
            len = Math.max(len, right + 1); // 取两个孩子长度的max
        }
        max = Math.max(max, len);
        return len;
    }
}
class Solution {    // 允许转折的路径
    int max = 0;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root);
        return max;
    }
    private int[] helper(TreeNode root) {
        if (root == null) {
            return new int[] {0, 0};
        }
        int[] left = helper(root.left), right = helper(root.right);
        int inc = 1, dec = 1;
        if (root.left != null) {
            if (root.left.val == root.val + 1) {   // 确认是否能和孩子形成升序/降序列
                inc = left[0] + 1;
            }
            if (root.left.val == root.val - 1) {
                dec = left[1] + 1;
            }
        }
        if (root.right != null) {
            if (root.right.val == root.val + 1) {
                inc = Math.max(inc, right[0] + 1);  // 取左右中最大的
            }
            if (root.right.val == root.val - 1) {
                dec = Math.max(dec, right[1] + 1);
            }
        }
        max = Math.max(inc + dec - 1, max);
        return new int[] {inc, dec};    // 返回以当前节点为起点的上升、下降序列长度
    }
}

2018.6 Onsite

• 实现min stack，需要多一个popMin方法. 思路是在push的时候如果min发生了变化就把当前的min push进去，再更新min。这样在pop的时候就可以通过对比min和当前pop的元素知道是否需要更新min，若min已经被pop了，那么前一个再pop出来就是当前的min。

class MinStack {
    private Stack<Integer> stack;
    private int min;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer>();
        min = Integer.MAX_VALUE;
    }
    
    public void push(int x) {
        if (stack.isEmpty()) {
            min = x;
        } else {

            if (x <= min) {
                stack.push(min);
                min = x;
            }
        }
        stack.push(x);
    }
    
    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        int temp = stack.pop();
        if (temp == min && !stack.isEmpty()) {  // means the min has gone 
            min = stack.pop();          // need to update
        }
        // return temp;
    }
    
    public int top() {
        if (stack.isEmpty()) {
            return 0;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if (stack.isEmpty()) {
            return 0;
        }
        return min;
    }
    public int popMin() {
        int temp = 0;
        while (!stack.isEmpty()) {
            temp = stack.pop();
            if (temp == min) {
                if (!isEmpty()) {
                    min = stack.pop();
                }
                break;
            }
        }
        return temp;
    }
}

2018.2 电面

• 给一个grid，里面有空地、墙和守卫，求离最近守卫距离最远的点的坐标集合。
• 从所有守卫开始BFS，最后一个level到达的点就是所求了。类似lc 286.

2018.3 Onsite

31. next-permutation

• 给一个int数组，将它改造成按字典序的下一个排列，若不存在则直接按从小到大的顺序调整。要求In-place对原数组操作，不能申请额外空间。
• 从右往左找相邻的两个数使得nums[i - 1] < nums[i]找到第一个升序对，然后再从右往左找首次出现的比nums[i]大的数nums[j]，二者对调，然后将nums[i + 1]及其之后的内容（一定是降序的）reverse一下即可。

public void nextPermutation(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }
    int i = nums.length - 1;
    for (; i >= 1; i--) {
        if (nums[i - 1] < nums[i]) {    // 第一个升序对；后续一定是完美降序
            int j = nums.length - 1;
            while (j >= i) {            // 找第一个恰好大于nums[i - 1]的数
                if (nums[j] > nums[i - 1]) {
                    swap(nums, i - 1, j);
                    break;
                }
                j--;
            }
            break;
        }
    }
    reverse(nums, i);
}
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
private void reverse(int[] nums, int start) {
    for (int i = start, j = nums.length - 1; i < j; i++, j--) {
        swap(nums, i, j);
    }
}

2018.7 Onsite

133. clone-graph

• 给一个无向有环全联通图的其中一个节点，要求拷贝一个完整的无向有环图，并返回拷贝而成的对应的该节点。而且两个节点之间可以有多条通路。
• 直接用map + DFS搞，对于每一个节点直接new一个相同label的节点出来，然后遍历所有的邻居递归调用clone即可。

private Map<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    return clone(node);
}
public UndirectedGraphNode clone(UndirectedGraphNode node) {
    if (node == null)   return null;
    if (map.containsKey(node.label)) {
        return map.get(node.label);
    }
    UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
    map.put(clone.label, cloned);
    for (UndirectedGraphNode neighbor : node.neighbors) {
        cloned.neighbors.add(clone(neighbor));
    }
    return cloned;
}

20. valid-parentheses

• 给一个字符串，判断其中三种括号(), [], {}是否匹配。用stack搞即可。
• follow-up: 求最少删几个字符可以使原字符串合法。例如(([{))就是把中间两个删除即可。
• 思路应该类似301. remove-invalid-parentheses，也是一个图论BFS。从当前字符串开始出发，所有可达点就是「删除一个字符串所得的新字符串」，注意需要用Set防止重复。每次对相同level的字符串判断是否valid，一旦出现了valid，则当前level所有的valid的字符串就是「最少删除之后的valid字符串」。

public List<String> removeInvalidParentheses(String s) {
    List<String> res = new ArrayList<>();
    if (s == null) return res;
    
    Set<String> visited = new HashSet<>();
    Queue<String> queue = new LinkedList<>();
    
    queue.add(s);
    visited.add(s);
    boolean found = false;
    
    while (!queue.isEmpty()) {
        curr = queue.poll();
        if (isValid(curr)) {
            res.add(curr);
            found = true;
        }
        
        if (found) continue;
        
        // generate all possible states
        for (int i = 0; i < curr.length(); i++) {
            String neighbor = curr.substring(0, i) + curr.substring(i + 1);
            if (!visited.contains(neighbor)) {
                queue.add(neighbor);
                visited.add(neighbor);
            }
        }
    }
    return res;
}
public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}

2018.5 Onsite

29. divide-two-integers

• 给两个数字，不使用乘、除、模运算前者除以后者之商，若结果越界则返回MAX_INT。
• 除了傻傻地一路减法减下去，还可以用位运算提速。提取出正负号之后统一按照正long数来处理。用sum来累计当前已经用了多少除数(dividend)，将next初始化为除数，在循环中找到恰好让sum + next > longDividend的next，然后把next往回移一位就是当前这一波累计的除数总和了，加到sum即可。同时用一个count计数记录用了多少个除数，这就是所求的商了，也是累计即可。

public int divide(int dividend, int divisor) {
    if ((dividend == Integer.MIN_VALUE && divisor == -1)
        || divisor == 0) {
        return Integer.MAX_VALUE;
    }
    if (dividend == 0) {
        return 0;
    }
    
    // using XOR to adjust sign
    int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1;
    int ans = 0;
    long longDividend = Math.abs((long)dividend);
    long longDivisor = Math.abs((long)divisor);
    long sum = 0;
    while (sum < longDividend) {    // warning use long abs value!
        int count = -1;     
        long next = longDivisor;
        while (sum + next <= longDividend) {
            count++;
            next <<= 1;
        }
        if (next == longDivisor) {  // 没有变化
            break;
        }
        sum += (next >> 1);     // how much has accumulated
        ans += (1 << count);    // how many divisor used
    }
    return sign * ans;
}

2018.5.21 电面

• lc 34 binary search

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return new int [] {-1, -1};
    }
    int first = searchFirst(nums, target);
    if (first == -1) {
        return new int [] {-1, -1};
    }
    int last = searchLast(nums, target);
    return new int[] {first, last};
}
private int searchFirst(int[] nums, int target) {
    // hope to biase to the front
    // invariant relation: A[start] < target <= A[end] 
    int start = -1, end = nums.length;
    while (end - start > 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] >= target) {   // end need to be more aggresive
            end = mid;      // shrink down
        } else {
            start = mid;    // step up
        }
    }
    return end == nums.length || nums[end] != target? -1: end;  // end will proceed at front
}
private int searchLast(int[] nums, int target) {
    // biase to the back
    // invariant relation: A[start] <= target < A[end] 
    int start = -1, end = nums.length;
    while (end - start > 1) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > target) {
            end = mid;      // shrink down
        } else {            // start need to be more aggressive
            start = mid;    // step up
        }
    }
    return start;
}

2018.7.1 电面 x2

• lc 72 edit distance
• 给两个字符串word1, word2，求使用addition, replacement, removement三种操作的情况下最少多少步可以从word1转换成word2。
• dp[i][j]表示当前长度i的子字符串1转换成长度j的子字符串2最少需要的操作数。初始条件显然是dp[0][x] = dp[x][0] = x。对于任意一个dp[i][j]，需要由上、左上、左三个方格的计算结果决定，往上dp[i-1][j]表示一个deletion，往左dp[i][j-1]表示一个addition，左上dp[i-1][j-1]表示一个replacement。每次选取三者中最小的，加上1就是当前的最小操作数了。

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    int len1 = word1.length(), len2 = word2.length();
    int[][] dp = new int [len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else {
                // s1取i-1、s2取j-1个字符的情况，然后s1和s2都取，不需要增加操作数
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // left: s1取i、s2取j-1个字符的操作数，现在相当于需要往s1中加s2对应位置的字符才能匹配上
                    // up: s1取i-1、s2取j个字符的操作数，相当于要从s1中删除字符才能匹配上
                    // left-up: s1取i-1、s2取j-1个字符的操作数，现在相当于要进行替换才能匹配上
                    int left = dp[i][j - 1], up = dp[i - 1][j], upLeft = dp[i - 1][j - 1];
                    dp[i][j] = Math.min(Math.min(left, up), upLeft) + 1;
                }
            }
        }
    }
    return dp[len1][len2];
}

2018.2.13 电面 x3

• 给一堆time range，可能有重合。比如[1,3], [2,4], [5,6]。总共的uniq的时间，即merge之后的总时间长度。类似lc 56，但不需要维护所有的interval了，只需要保存prev，当后续interval没有overlap的时候就累加time range即可。

public int getTimeRange(List<Interval> intervals) {
    if (intervals == null) {
        return new ArrayList<Interval>();
    }
    Collections.sort(intervals, (a, b) -> {
        if (a.start != b.start) {
            return a.start - b.start;
        } else {
            return a.end - b.end;
        }
    });
    Interval prev = null;
    int range = 0;
    for (Interval itv : intervals) {
        if (prev == null) {
            prev = itv;
        } else {
            if (itv.start > prev.end) {
                range += (prev.end - prev.start);
                prev = itv;
            } else {
                prev.end = Math.max(prev.end, itv.end);
            }
        }
    }
    range += (prev.end - prev.start);
    return range;
}

• follow-up: 最长的连续range（能合并的合并，最长的range）.直接在上面加个取长度即可。
• follow-up2: 求出现次数最多的range。思路也是先排序，利用一个currCount统计当前的time range数，出现了重叠就将prev设置为overlap的部分并累加，当overlap结束就更新maxCount即可。

public static Interval getMaxInterval(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
        return null;
    }
    Collections.sort(intervals, (a, b) -> {
        if (a.start != b.start) {
            return a.start - b.start;
        } else {
            return a.end - b.end;
        }
    });
    int maxCount = 1, currCount = 1;
    Interval prev = null, ret = null;
    for (Interval itv : intervals) {
        if (prev == null) {
            prev = itv;
            currCount = 1;
        } else {
            if (itv.start >= prev.end) {
                prev = itv;
                currCount = 1;
            } else {
                prev = new Interval(itv.start, Math.min(prev.end, itv.end));
                currCount += 1;
                if (currCount > maxCount) {
                    ret = prev;
                }
            }
        }
    }
    return ret;
}

2017.11 电面

• 类似于lc 158，给一个API read4(char[] buf)，每次可以从某个file中读4个字符到buf，并返回实际读取的字符数。

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    private int N = 4, tempIndex = 0, lastLimit = 0;
    char[] temp = new char[N];
    public int read(char[] buf, int n) {
        if (n < 1) {
            return n;
        }
        int index = 0;
        if (tempIndex == lastLimit) {
            lastLimit = read4(temp);
            tempIndex = 0;
        }
        while (lastLimit > 0) {
            while (n > 0 && tempIndex < lastLimit && index < buf.length) {
                buf[index++] = temp[tempIndex++];
                n--;
            }
            // 如果n读够了，直接返回
            if (n == 0) {
                return index;
            }
            // 如果tempIndex到头了，可以继续读
            lastLimit = read4(temp);
            tempIndex = 0;
        }
        return index;
    }
}

2015.10 电面

785. is-graph-bipartite x3

• 给一个数组，每个index对应着该node的所有邻接点。问这个graph能否只用两个颜色给node上色使得相邻两个点的颜色都不一样。
• 方法一：DFS。对于每一个点都一波直接深度搜索上色，用一个数组存储上色状态，0表示未访问过，-1和1分别表示两个颜色，在dfs时对于当前的点若已经访问过就判断是否符合当前给定的颜色，若未访问则直接上色并DFS到它所有邻接点。需要注意可能有若干独立的cluster，因此不能一次DFS搜索就结束了，而是需要一个循环保证对所有未访问过的点都进行一次DFS。

class Solution {
    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length == 0) {
            return true;
        }
        int[] colors = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if (colors[i] == 0 && !checkColor(graph, colors, -1, i)) {
                return false;
            }
        }
        return true;
    }
    private boolean checkColor(int[][] graph, int[] colors, int currColor, int currNode) {
        if (colors[currNode] != 0) {
            return colors[currNode] == currColor;
        }
        colors[currNode] = currColor;
        for (int neighbor : graph[currNode]) {
            if (!checkColor(graph, colors, -currColor, neighbor)) {
                return false;
            }
        }
        return true;
    }
}

• 方法二：BFS，还是用queue存放所有邻接点然后逐一上色。

class Solution {
    public boolean isBipartite(int[][] graph) {
        if (graph == null || graph.length == 0) {
            return true;
        }
        int[] colors = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {    // 只check没有访问过的点，即各个独立的cluster
            if (colors[i] == 0 && !checkColor(graph, colors, -1, i)) {
                return false;
            }
        }
        return true;
    }
    private boolean checkColor(int[][] graph, int[] colors, int currColor, int currNode) {
        if (colors[currNode] != 0) {
            return colors[currNode] == currColor;
        }
        Queue<Integer> q = new LinkedList<>();
        int color = currColor;
        q.offer(currNode);
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int node = q.poll();
                if (colors[node] != 0) {
                    if (colors[node] != color) return false;
                } else {
                    colors[node] = color;
                }
                for (int neighbor : graph[node]) {
                    if (colors[neighbor] == 0) q.offer(neighbor);   // 避免回头路
                }
            }
            color = -color;
        }
        return true;
    }
}

2017.10 电面

720. longest-word-in-dictionary

• 给一个string数组，只含有小写字母，这些word可能形成链式如a, ap, app, appl, apple，求能形成链式的最长的单词，若有多个则取lexicographical最小的。
• 用sort + Set的方式比较trivial，排序后就可以逐个取word判断prefix是否在Set中。
• 想考的方法其实是Trie。根据所给的word构建Trie，每个节点直接存储word而不是boolean isWord，因为最后要求的是最长的String，直接存String方便返回。构建完Trie之后就从root开始找最长的连续的到达leaf的路径，要求路径上每一个word都长度更长（increasing）。

class Solution {
    class TrieNode {
        TrieNode[] nexts = new TrieNode[26];
        String word = "";
    }
    class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String word) {
            TrieNode curr = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                int index = c - 'a';
                if (curr.nexts[index] == null) {
                    curr.nexts[index] = new TrieNode();
                }
                curr = curr.nexts[index];
            }
            curr.word = word;
        }
    }
    private String dfs(TrieNode node) {
        String ret = node.word;
        for (TrieNode next : node.nexts) {
            if (next != null && next.word.length() > 0) {
                String childWord = dfs(next);
                if (childWord.length() > ret.length()) {
                    ret = childWord;
                }
            }
        }
        return ret;
    }
    public String longestWord(String[] words) {
        if (words == null || words.length == 0) {
            return "";
        }
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        return dfs(trie.root);
    }
}

2018.3 电面

• 将二叉树转换成双向链表。应该是类似lc 426的。

426. convert-binary-search-tree-to-sorted-doubly-linked-list

• 给一个BST，将它转换成排好序的循环双向链表（头尾相接），返回头部。可以把左右孩子就看作是当前节点的前后链表节点，不需要额外搞ListNode类。
• BST要维持顺序，那就是用中序遍历。利用全局变量prev来记录每一个子树的结尾节点，先build左子树，然后把当前节点拼到prev的后面，再去继续build右子树即可。

private Node prev = null;
public Node treeToDoublyList(Node root) {
    if (root == null) {
        return null;
    }
    Node dummy = new Node();    // 伪头部的next就是head
    prev = dummy;   
    buildDoublyList(root);
    prev.right = dummy.right;
    dummy.right.left = prev;
    dummy.left = dummy.right = null;    // 清理dummy
    return prev.right;
}
// 执行buildDoublyList后会将node下面的部分都形成双向链表
public void buildDoublyList(Node node) {
    if (node == null) {
        return;
    }
    buildDoublyList(node.left); // 先对左子树build一下，prev会指向最后一个节点
    prev.right = node;          // 将node拼进去
    node.left = prev;
    prev = node;                // 左半部分+当前节点的结尾就是node
    buildDoublyList(node.right);// 继续build右子树
}

• 方法二：分治法。先把左右子树的循环双向链表build好，再把当前节点塞到中间，同时把新的前后循环连接一下。注意在分别build的时候，需要把root本身设一个自循环，这样就可以重复使用connect方法了。

public Node treeToDoublyList(Node root) {
    if (root == null) {
        return null;
    }
    Node leftHead = treeToDoublyList(root.left);
    Node rightHead = treeToDoublyList(root.right);
    root.left = root;
    root.right = root;
    return connect(connect(leftHead, root), rightHead);
}
public Node connect(Node leftHead, Node rightHead) {
    if (leftHead == null) {
        return rightHead;
    }
    if (rightHead == null) {
        return leftHead;
    }
    Node leftTail = leftHead.left;
    Node rightTail = rightHead.left;
    leftTail.right = rightHead;
    rightHead.left = leftTail;
    leftHead.left = rightTail;
    rightTail.right = leftHead;
    return leftHead;
}

2017.12 电面

127. word-ladder

• 给一个List的String，然后一个初始String一个目标String，要求每次变动一个字母且变动后的词语来自该List的情况下，最短需要变几次得到目标String。
• 可以看作BFS问题，每个word就是一个node，neighbor就是换掉一个字母后且在wordList中存在的词。这样BFS最快到达dest的就是最短了。

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
    if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0
        || beginWord.length() != endWord.length() || wordList == null || wordList.size() == 0) {
        return 0;
    }
    Set<String> wordSet = new HashSet<>(wordList);
    Queue<String> toVisit = new LinkedList<>();
    bfs(beginWord, wordSet, toVisit);
    int dist = 2;
    while (!toVisit.isEmpty()) {
        int size = toVisit.size();
        for (int i = 0; i < size; i++) {
            String curr = toVisit.poll();
            if (curr.equals(endWord)) {
                return dist;
            } else {
                bfs(curr, wordSet, toVisit);
            }
        }
        dist++;
    }
    return 0;
}
private void bfs(String beginWord, Set<String> wordSet, Queue<String> toVisit) {
    wordSet.remove(beginWord);
    StringBuilder sb = new StringBuilder(beginWord);
    for (int i = 0; i < sb.length(); i++) {
        char origin = sb.charAt(i);
        for (int k = 0; k < 26; k++) {
            char c = (char)('a' + k);
            sb.setCharAt(i, c);
            String curr = sb.toString();
            if (wordSet.contains(curr)) {
                toVisit.add(curr);
                wordSet.remove(curr);
            }
        }
        sb.setCharAt(i, origin);
    }
}

• follow-up：如何记录最短路径？其实就是126。还是用BFS找最短路径，维护一个distMap记录每个节点到达时所经过的步数，到达终点后再从头开始DFS，每次只去步数增长1的邻居点。

public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    List<List<String>> ans = new ArrayList<>();
    if (beginWord == null || endWord == null || beginWord.length() == 0 || endWord.length() == 0
        || beginWord.length() != endWord.length() || wordList == null || wordList.size() == 0) {
        return ans;
    }
    Map<String, Integer> distMap = new HashMap<>();
    for (String word : wordList) {
        distMap.put(word, Integer.MAX_VALUE);
    }
    if (!distMap.containsKey(endWord)) {
        return ans;
    }
    distMap.put(beginWord, 0);
    
    Map<String, Set<String>> neighborMap = new HashMap<>();
    Queue<String> toVisit = new LinkedList<>();
    toVisit.offer(beginWord);
    boolean found = false;
    while (!toVisit.isEmpty() && !found) {
        int size = toVisit.size();
        for (int i = 0; i < size; i++) {
            String currWord = toVisit.poll();
            if (currWord.equals(endWord)) {
                break;
            } else {
                bfs(currWord, distMap, neighborMap, toVisit);
            }
        }
    }
    dfs(beginWord, endWord, distMap, neighborMap, ans, new ArrayList<>());
    return ans;
}
public void bfs(String fromWord, Map<String, Integer> distMap, 
                Map<String, Set<String>> neighborMap, Queue<String> q) {
    StringBuilder sb = new StringBuilder(fromWord);
    for (int i = 0; i < sb.length(); i++) {
        char origin = sb.charAt(i);
        for (int k = 0; k < 26; k++) {
            char c = (char)('a' + k);
            sb.setCharAt(i, c);
            String curr = sb.toString();
            if (distMap.containsKey(curr) && distMap.get(fromWord) + 1 <= distMap.get(curr)) {
                q.add(curr);
                distMap.put(curr, distMap.get(fromWord) + 1);
                neighborMap.putIfAbsent(fromWord, new HashSet<>());
                neighborMap.get(fromWord).add(curr);
            }
        }
        sb.setCharAt(i, origin);
    }
}
public void dfs(String fromWord, String toWord, Map<String, Integer> distMap, 
                Map<String, Set<String>> neighborMap, List<List<String>> ans, List<String> path) {
    path.add(fromWord);
    if (fromWord.equals(toWord)) {
        ans.add(new ArrayList<>(path));
        path.remove(path.size() - 1);
        return;
    }
    Set<String> neighbors = neighborMap.get(fromWord);
    if (neighbors != null) {
        for (String neighbor : neighbors) {
            if (distMap.get(neighbor) == distMap.get(fromWord) + 1) {
                dfs(neighbor, toWord, distMap, neighborMap, ans, path);
            }
        } 
    }
    path.remove(path.size() - 1);
}

2017.10 电面 x4

• pinterest页面例子，每个图片都等宽但不等高，给一堆pin的id、高度，求放置pin的策略，让每个col的pin都比较好看，即按顺序拼pin，每次选最短的column append到底部。例如输入pins = [{'id':1, 'height': 100}, {'id':2, 'height':300}, {'id':3, 'height':150}.....]，以及col = 3。返回List of List[[1,.....],[2,...],[3,...]]，每一个List表示该column存放的图片的id。
• 如何保证每次都取最短的col去append？联想到了PriorityQueue，可以logK插入，每次都直接取到最短的进行append。时间复杂度O(NlogK)，其中K是col数量。

public static List<List<Integer>> getColumnPinIds(Map<Integer, Integer> heightMap, int colTotal) {
    int[] colHeights = new int[colTotal];
    PriorityQueue<Integer> pq = new PriorityQueue<>((i, j) -> colHeights[i] != colHeights[j] ? 
                        colHeights[i] - colHeights[j] : i - j);
    for (int i = 0; i < colTotal; i++) {
        pq.offer(i);
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < colTotal; i++) {
        ans.add(new ArrayList<>());
    }
    for (int pinId : heightMap.keySet()) {
        int colIndex = pq.poll();
        colHeights[colIndex] += heightMap.get(pinId);
        ans.get(colIndex).add(pinId);
        pq.offer(colIndex);
    }
    return ans;
}

• 如果不让用heap？那就直接O(NK)，每次都遍历k个col看看谁最小即可。
• follow-up: resize一下窗口，如何快速rearrange这些pin？

2017.10 电面

• behavior tree. 给一对用户的action如

  user_id, timestamp, action
  100, 1000, A
  200, 1003, A
  300, 1009, B
  100, 1026, B
  100, 1030, C
  200, 1109, B
  200, 1503, A

  如何从上面的log file构造成一个system log的graph如

  |---A (2)
  |    |---B (2)
  |    |    |---C (1)
  |    |    |---A (1)
  |---B (1)

• 这个和Trie很类似。可以考虑对于序列中每一个动作，维护一个TrieNode，其中包含action, count, 和后续操作节点nexts.

class LogParser {
        static class TrieNode {
        String action;
        int count;
        Map<String, TrieNode> nexts;
        public TrieNode() {
            count = 0;
            nexts = new HashMap<>();
        }
    }

    public static void insertActions(TrieNode root, List<String> actions) {
        TrieNode curr = root;
        for (String action : actions) {
            curr.nexts.putIfAbsent(action, new TrieNode());
            curr.nexts.get(action).count++;
            curr = curr.nexts.get(action);
        }
    }
    static  class Record {
        int userId;
        int timestamp;
        String action;
        public Record(int userId, int timestamp, String action) {
            this.userId = userId;
            this.timestamp = timestamp;
            this.action = action;
        }
    }
    public static TrieNode getGraph(String[] logs) {
        Record[] records = new Record[logs.length];
        for (int i = 0; i < logs.length; i++) {
            String[] splitted = logs[i].split(",");
            int userId = Integer.parseInt(splitted[0].trim());
            int timestamp = Integer.parseInt(splitted[1].trim());
            String action = splitted[2].trim();
            records[i] = new Record(userId, timestamp, action);
        }
        Arrays.sort(records, (a, b) -> a.timestamp - b.timestamp);
        Map<Integer, List<String>> userActionMap = new HashMap<>();
        for (Record record : records) {
            userActionMap.putIfAbsent(record.userId, new ArrayList<>());
            userActionMap.get(record.userId).add(record.action);
        }
        TrieNode root = new TrieNode();
        for (int userId : userActionMap.keySet()) {
            insertActions(root, userActionMap.get(userId));
        }
        return root;
    }
    public final static String PADDING_STRING = "|   ";
    public final static String LEADING_STRING = "|---";
    public static void printGraph(TrieNode node, StringBuilder sb) {
        for (String nextAction : node.nexts.keySet()) {
            System.out.print(sb);
            System.out.print(LEADING_STRING);
            System.out.print(nextAction);
            System.out.println("(" + node.nexts.get(nextAction).count + ")");
            sb.append(PADDING_STRING);
            printGraph(node.nexts.get(nextAction), sb);
            sb.delete(sb.length() - PADDING_STRING.length(), sb.length());
        }
    }
}

2018.3 Onsite

LC 146 LRU

• 说是设计Gmail界面，说是类似实现LRU。实现Cache就是用Map，但是least recent特性就需要额外的数据结构来提升效率：双向链表。Map中存放key - Node映射，所有的cache都放在一个双向链表上，每次get的时候就将get到的node挪到第一位。put时若capacity超了就将链表最后一个节点删除即可。

class LRUCache {
    class Node {
        int key;
        int val;
        Node prev;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            prev = null;
            next = null;
        }
    }
    Map<Integer, Node> map;
    Node fakeHead, fakeTail;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        fakeHead = new Node(-1, -1);
        fakeTail = new Node(-1, -1);
        fakeHead.next = fakeTail;
        fakeTail.prev = fakeHead;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node ret = map.get(key);
            moveToFirst(ret);
            return ret.val;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (map.containsKey(key)) {
            Node oldNode = map.get(key);
            oldNode.val = value;
            moveToFirst(oldNode);
            return;
        }
        if (map.size() == capacity) {
            map.remove(fakeTail.prev.key);
            remove(fakeTail.prev);
        }
        Node newNode = new Node(key, value);
        insertToFirst(newNode);
        map.put(key, newNode);
    }
    
    private void moveToFirst(Node node) {
        remove(node);
        insertToFirst(node);
    }
    private void insertToFirst(Node node) {
        node.next = fakeHead.next;
        fakeHead.next = node;
        node.prev = fakeHead;
        node.next.prev = node;
    }
    private void remove(Node node) {
        if (node.prev == null) {
            return;
        }
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

2018.1 Onsite

437. path-sum-iii

• 给一个二叉树，给一个目标值sum，求有几条从上往下累加的路径之和等于sum。
• 除了O(N^2)的笨方法，考虑使用cache保存已有结果，这里用到的是prefixSum的思路。在深入下层节点的时候直接累计currSum，同时在cache中找是否存在若干段path是currSum - target，这样就可以把这些prefix从path中给去掉就可以得到target了。在深入更下层节点之前，需要更新currSum的计数，这样在更深层的时候就知道最新的currSum作为prefixSum的计数。

public int pathSum(TreeNode root, int sum) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    dfs(root, 0, sum, map);
    return count;
}
int count;
private void dfs(TreeNode root, int currSum, int target, Map<Integer, Integer> map) {
    if (root == null) {
        return;
    }
    currSum += root.val;
    count += map.getOrDefault(currSum - target, 0);
    map.put(currSum, map.getOrDefault(currSum, 0) + 1);
    
    dfs(root.left, currSum, target, map);
    dfs(root.right, currSum, target, map);
    
    map.put(currSum, map.get(currSum) - 1);
}

362. design-hit-counter

• 实现一个hitCount类，通过hit(timestamp)表示在什么时候出现了hit（可能同一时刻有多次hit），然后通过getHits得到最近300s内hit了多少次。
• 利用循环数组记录hits即可，容量可以直接设为300，这样最多就可以同时记录300s中每一秒的hit数量，在getHis的时候直接遍历一边如何保证每个bucket都是valid的count呢，就需要记录每一个bucket对应的hit的时刻是几时，因此需要另一个time数组来记录。

class HitCounter {
    private int[] hits;
    private int[] time;
    final private int TIMEWINDOW = 300;
    /** Initialize your data structure here. */
    public HitCounter() {
        hits = new int [TIMEWINDOW];
        time = new int [TIMEWINDOW];
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        int index = timestamp % TIMEWINDOW;
        if (time[index] != timestamp) {
            time[index] = timestamp;
            hits[index] = 1;
        } else {
            hits[index]++;
        }
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        int count = 0;
        for (int i = 0; i < TIMEWINDOW; i++) {
            if (timestamp - time[i] < TIMEWINDOW) {
                count += hits[i];
            }
        }
        return count;
    }
}

2017.12 Onsite

392. is-subsequence

• 给两个字符串，判断其中一个字符串s是否是另一个字符串t的子序列串，这个字串不要求字符连续出现，只要求出现顺序一致且全部出现即可。
• trivail的方法是直接两个指针扫，只有当s的字符和t匹配了才挪动s的指针。
• 如果t很大，而s是很多个小字符串需要连续调用这个函数呢？这就可以考虑使用记录索引+二分查找了。首先对t中每个字符记录出现的索引并存入List，这个是不会变的。然后对于输入s，每个字符都对该字符的List用二分查找找索引的「第一次出现/插入位置」，找到后就作为后一次搜索的索引。如果插入位置是在最后，说明t无法满足s的对应位置；

public boolean isSubsequence(String s, String t) {
    if (s == null || s.length() == 0) {
        return true;
    }
    List<Integer>[] indexCache = new List [26];
    char[] tChar = t.toCharArray();
    
    for (int i = 0; i < tChar.length; i++) {
        int index = tChar[i] - 'a';
        if (indexCache[index] == null) {
            indexCache[index] = new ArrayList<Integer>();
        }
        indexCache[index].add(i);
    }
    
    char[] sChar = s.toCharArray();
    int pos = 0;    // 在t中出现的最小索引
    for (int i = 0; i < sChar.length; i++) {
        int index = sChar[i] - 'a';
        if (indexCache[index] == null) {
            return false;
        }
        
        int insertPos = Collections.binarySearch(indexCache[index], pos);
        if (insertPos < 0) {
            insertPos = -insertPos - 1;
        }
        if (insertPos == indexCache[index].size()) {
            return false;
        }
        pos = indexCache[index].get(insertPos) + 1; // 下一步所需最小索引更新为已有索引的下一位
    }
    return true;
}

2018.5 电面

67. add-binary

• 给两个String表示的二进制数，返回二者相加后的二进制字符串。
• 模拟加法，可以从两个数的最后一位开始加，最后reverse一下即可，注意最后需要确认首位是否需要加上carry。

public String addBinary(String a, String b) {
    if (a == null || a.length() == 0) {
        return b;
    } else {
        if (b == null || b.length() == 0) {
            return a;
        }
    }
    StringBuilder sb = new StringBuilder();
    char[] aChar = a.toCharArray(), bChar = b.toCharArray();
    int i = aChar.length - 1, j = bChar.length - 1, carry = 0;
    while (i >= 0 || j >= 0) {
        int sum = carry;    // from prev result
        if (i >= 0) {
            sum += aChar[i--] - '0';
        }
        if (j >= 0) {
            sum += bChar[j--] - '0';
        }
        sb.append(sum % 2); // what's left after taking out carry
        carry = sum / 2;    // 3,2 -> 1; 1,0 -> 0
    }
    if (carry != 0) {
        sb.append(carry);   // warning! the most significant position
    }
    return sb.reverse().toString();
}

2017.11 Onsite

14. longest-common-prefix

• 给一串字符串数组，求这些字符串开头的公共部分。
• 直接按照字典序排序，找首位和末尾的字符串比较看看有多少公共部分即可。

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    Arrays.sort(strs);
    String s1 = strs[0];
    String s2 = strs[strs.length - 1];
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            break;
        }
        sb.append(s1.charAt(i));
    }
    return sb.toString();
}

2018.8 Onsite

560. subarray-sum-equals-k

• 给一个int数组和一个k，问有多少连续的subarray之和等于k。这些int都在[-1000, 1000]，数组长度最多20000。
• 一开始想用双指针，但有正有负，更新条件不好搞。正解是使用Map，在计算sum的时候顺便看看之前是否出现过sum - k。这其实和path sum III 很像，都是利用prefix sum.

public int subarraySum(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int count = 0, sum = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (map.containsKey(sum - k)) {     // 看之前是否已经出现了这一段prefix
            count += map.get(sum - k);      // 这样sum - prefix就等于k了
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return count;
}

2018.5 Onsite

698. partition-to-k-equal-sum-subsets

• 给一个只含有(0, 10000)的int数组和一个k，判断是否可以将该数组划分为k个相等sum的partition。
• 似乎是个NP-hard的问题。只能用暴力办法，DFS+标记数组，每次累加过后进入下一层看看是否达到了targetSum，达到了就清空继续往后找新的一组subset.最后如果只剩下一组了，直接返回true，因为此时其他k - 1个组都已经达到targetSum了，当前的sum = k * targetSum - (k - 1) * targetSum = targetSum.

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length || k < 1) {
            return false;
        }
        if (k == 1) {
            return true;
        }
        int sum = IntStream.of(nums).sum();  // Java8的stream!
        if (sum % k != 0) {
            return false;
        }
        int targetSum = sum / k;
        boolean[] visited = new boolean[nums.length];
        return checkPartition(nums, visited, 0, targetSum, 0, k);
    }
    public boolean checkPartition(int[] nums, boolean[] visited, int startIndex, int targetSum, int currSum, int k) {
        if (k == 1) {    // 提前break
            return true;
        }
        if (currSum == targetSum) {
            return checkPartition(nums, visited, 0, targetSum, 0, k - 1);
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (checkPartition(nums, visited, i + 1, targetSum, currSum + nums[i], k)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}

• 方法二：更快的做法是先对数组排序，然后存k个bucket，每个bucket从后往前取元素不断累加.

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length || k < 1) {
            return false;
        }
        if (k == 1) {
            return true;
        }
        int sum = IntStream.of(nums).sum();  // Java8的stream!
        if (sum % k != 0) {
            return false;
        }
        int targetSum = sum / k;
        Arrays.sort(nums);
        return checkPartition(nums, targetSum, new int[k], nums.length - 1);
    }
    public boolean checkPartition(int[] nums, int targetSum, int[] buckets, int numsIndex) {
        if (numsIndex < 0) {
            for (int bucket : buckets) {
                if (bucket != targetSum) {
                    return false;
                }
            }
            return true;
        }
        for (int i = 0; i < buckets.length; i++) {
            if (buckets[i] + nums[numsIndex] <= targetSum) {
                buckets[i] += nums[numsIndex];
                if (checkPartition(nums, targetSum, buckets, numsIndex - 1)) {
                    return true;
                }
                buckets[i] -= nums[numsIndex];
            }
        }
        return false;
    }
}

• follow-up: 如果去掉正数的限制，允许出现负数和0？
• 上面的方法只考虑了直接累积叠加，无法解决负数问题。因此需要引入一个elementCount来统计当前这一波存入了多少element，当达到targetSum的时候需要判断当前这一波是否真的存入了元素。

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length || k < 1) {
            return false;
        }
        if (k == 1) {
            return true;
        }
        int sum = IntStream.of(nums).sum();
        if (sum % k != 0) {
            return false;
        }
        int targetSum = sum / k;
        boolean[] visited = new boolean[nums.length];
        return checkPartition(nums, visited, 0, targetSum, 0, k, 0);
    }
    public boolean checkPartition(int[] nums, boolean[] visited, int startIndex, int targetSum, int currSum, int k, int elementCount) {
        if (k == 0) {      // 必须算完才行
            return true;
        }
        if (currSum == targetSum && elementCount > 0) {
            return checkPartition(nums, visited, 0, targetSum, 0, k - 1, 0);
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (checkPartition(nums, visited, i + 1, targetSum, currSum + nums[i], k, elementCount + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        return false;
    }
}

• follow-up: 如何记录路径？也就是在dfs的时候多用一个List记录存入的数字即可。

数组与query x2

• 给一个长度为N的数组，其中每一个数字都是8bit的正整数（0～255）。给一个二维数组M，类似于[[1,100],[5,1000],etc]，求所给range的mean。
• naive方法是对于每一个query，都求一个sum / size，复杂度O(M*N)。可以用lc 303 rangeSum的思路，先求一波和，然后求sum的时候直接用两个位置的相减即可。

public int[] getMeans(int[] nums, int[][] queries) {
    if (nums == null || nums.length == 0
    || queries == null || queries.length == 0) {
        return null;
    }
    int N = nums.length, M = queries.length;
    int[] sums = new int[N];
    sums[0] = nums[0];
    for (int i = 1; i < N; i++) {
        sums[i] = sums[i - 1] + nums[i];
    }

    double[] means = new double[M];
    for (int i = 0; i < M; i++) {
        int start = quries[i][0];
        int end = quries[i][1];
        means[i] = (sum[end] - (start > 0 ? sums[start - 1] : 0)) 
                    / (double)(end - start + 1);
    }
}

• follow-up: 还是这些input，但query内容变为「求每个range的median」。median自然想到排序，而这个0～255的限制范围就容易想到木桶排序，然后根据个数就可以找到median了。在预处理的时候直接给每一个元素维护一个长度为256的bucket，

static public double[] getMedians(int[] nums, int[][] queries) {
    if (nums == null || nums.length == 0
    || queries == null || queries.length == 0) {
        return null;
    }
    int N = nums.length, M = queries.length;
    int[][] buckets = new int[N][256];
    buckets[0][nums[0]]++;
    for (int i = 1; i < N; i++) {
        buckets[i] = Arrays.copyOf(buckets[i - 1], 256);
        buckets[i][nums[i]]++;
    }

    double[] medians = new double[M];
    for (int i = 0; i < M; i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        int[] tempBucket = Arrays.copyOf(buckets[end], 256);
        if (start > 0) {
            for (int j = 0; j < 256; j++) {
                tempBucket[j] -= buckets[start - 1][j];
            }
        }
        medians[i] = getMedian(tempBucket, (end - start) / 2, ((end - start + 1) & 1) == 0);
    }
    return medians;
}
static private double getMedian(int[] bucket, int pos, boolean isEven) {
    int i = 0, index = -1;
    while (i < 256) {
        index += bucket[i++];
        if (index >= pos) {
            break;
        }
    }
    if (!isEven || index > pos) {
        return i - 1;
    }
    int first = i - 1;
    while (i < 256) {
        index += bucket[i++];
        if (index > pos) {
            return (first + i - 1) / 2.0;
        }
    }
    return first;
}

• 再follow-up: 当N特别大的时候，无法全部放入内存，如何在预处理的时候进行压缩。(给定一个压缩指标K, K<<N， 问怎么在预处理的时候进行压缩，同时效率还是O(M+N). 答案是每次隔K个进行存储，这样在查找的时候每次需要K次，但是K是常数，所以效率还是O(M+N).????)

2017.11 Onsite

139. word-break

• 给一个List表示词典，给一个String，求能否把该String按照某种方式以空格分割，使得每个单词都来自于字典。
• 利用DP状态转换，若当前子字符串在dict中且子字符串之前的部分也符合要求，则当前这一段都true。

public boolean wordBreak(String s, List<String> wordDict) {
    if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) {
        return false;
    }
    Set<String> set = new HashSet<>();
    int maxLen = 0;
    for (String word : wordDict) {
        maxLen = Math.max(word.length(), maxLen);
        set.add(word);
    }
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int end = 1; end <= s.length(); end++) {
        for (int start = end - 1; end - start <= maxLen && start >= 0; start--) {
            if (set.contains(s.substring(start, end)) && dp[start]) {
                dp[end] = true;
                break;
            }
        }
    }
    return dp[s.length()];
}

• follow-up: 如果wordDict很大怎么存？用Trie。用Trie也存不下呢？？？
• theyearofdragon可以分成the year of dragon或者they ear of dragon，显然第一种分法好些，问怎么去判断分成不同语句哪种最好。？？？

column放pin

• Pinterest主页上有N个column，给一个set of pins，pins有score和length，每次把score最高的pin贴到最短的column上，return List<List<Pin>>表示每个column里的pins。

static class Pin implements Comparable<Pin> {
    double score;
    double height;
    public Pin(double score, double height) {
        this.score = score;
        this.height = height;
    }
    
    @Override
    public int compareTo(Pin that) {
        return this.score == that.score ? 
            (int)(this.height - that.height)
            : (int)(that.score - this.score);
    }
}
public static List<List<Pin>> getPinPos(List<Pin> pinList, int col) {
    Collections.sort(pinList);
    List<List<Pin>> ret = new ArrayList<>();
    double[] heights = new double[col];
    PriorityQueue<Integer> pq = new PriorityQueue<>((i, j) -> heights[i] != heights[j] ? (int)(heights[i] - heights[j]) : i - j);
    
    for (int i = 0; i < col; i++) {
        ret.add(new ArrayList<>());
        pq.offer(i);
    }
    for (Pin pin : pinList) {
        int index = pq.poll();
        heights[index] += pin.height;
        ret.get(index).add(pin);
        pq.offer(index);
    }
    return ret;
}

• follow up: 用户的手机屏幕只有M长，如果屏幕的顶点距离主页顶点距离为K(???)，求出能显示出的pins。

Merge interval

• 给List of Interval，含有start, end, weight属性。如果两个interval overlap了，overlap部分的weight相加变成新的interval，返回merge之后的interval list。但是如果有多个overlap怎么办？比如[0,1], [0,4], [0,5], [3,6]这种，merge多次吗？

2018.7 Onsite

相似Set

• 输入一个data stream，比如：a -> [b]; b -> [a, d, f]; c -> [b, j]; ...，表示这些元素是相似的，且相似具有传递性，最后输出所有相似的set。
• 可以考虑用并查集，每一个起始点作为root，其余点就是它的children。

// TODO
public static void printGroup(Map<String, List<String>> map) {
    if (map == null || map.size() == 0) {
        return;
    }
    Map<String, String> parentMap = new HashMap<>();
    Set<String> nodeSet = new HashSet<>();
    for (String key : map.keySet()) {
        map.putIfAbsent(key, key);
        nodeSet.add(key);
        String parent = findParent(key);
        List<String> equivalents = map.get(key);
        for (String equivalent : equivalent) {
            nodeSet.add(equivalent);
            String currParent = findParent(equivalent);
            if (!currParent.equals(parent)) {
                map.put(currParent, parent);
            }
        }
    }
    // ....
}
public static String findParent(String str, Map<String, String> parentMap) {
    while (!parentMap.getOrDefault(str, str).equals(str)) {
        String parent = parentMap.get(str);
        parentMap.put(str, parentMap.getOrDefault(parent, parent));
        str = parent;
    }
    return str;
}

• 或者直接建graph之后，找connected component来搞，似乎实现起来更不容易出错？

[2016.5 Onsite]

124. binary-tree-maximum-path-sum

• 给一个二叉树，求其中的任意一条路径使得经过所有节点的值最大，不一定要经过root。

class Solution {
    private int max;        // store the value of taking current root as swag point "^"
    public int maxPathSum(TreeNode root) {
        max = Integer.MIN_VALUE;
        return Math.max(dfs(root), max);
    }
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        max = Math.max(max, left + right + root.val);   // take both of the branches
        return root.val + Math.max(left, right);    // means only take one of the branches
    }
}

meeting-rooms-ii变种

• 给一堆task的开始和结束时间和每个task所需的cpu数量，求完成所有task的最小cpu数。
• 先根据开始时间排序，然后往PriorityQueue中逐个加入task，若当前开始时间比队首的结束时间大，说明可以复用前面的cpu了，每次注意要更新cpu数量保证是最大值即可。

public int minCPU(Task[] tasks) {
    if (tasks == null || tasks.length == 0) {
        return 0;
    }
    Arrays.sort(tasks, (a, b) -> a.start - b.start);
    PriorityQueue<Task> pq = new PriorityQueue<>(); // 同时执行的task
    int max = 0, curr = 0;
    for (int i = 0; i < tasks.length; i++) {
        // 若当前task比最先结束的task晚开始，就可以用之前释放的cpu了
        while (!pq.isEmpty() && tasks[i].start >= pq.peek().end) {
            curr -= pq.poll().cpu;  // 更新当前pq中所有任务所需cpu
        }
        curr += tasks[i].cpu;
        max = Math.max(curr, max);
        pq.offer(tasks[i]);
    }
    return max;
}

判断相同文件

• 给定两个函数，get_files(dir), get_dir(dir) 返回所有内容相同的file. 问怎么定义内容相同，用文件名还是binary， 小哥说要内容相同，那我就用recursion遍历所有file， 然后用hashing把文件的内容hash成key放在dictionary，最后返回这个dictionary。
• follow up说， 如果hashing非常expensive怎么办? hashing前先check file size，如果文件大小一样，再用hashing判断是不是一样。
• 2nd follow up说get_files, get_dir如果expensive怎么办，答曰用parrallel programming （gpu or multi core） 可以优化。

2018.5 Onsite

read-n-characters-given-read4变种

• 给一堆有序号的无限block，给你一个读给定index的单个block的API，每个block 64MB，然后给你一个开始的byte位置(例如：3MB，就是从index = 0 开始)，和要读的byte长度(例如：67MB)，返回读的结果。就分情况，慢慢写，先是第一个block(可能，只是读部分)，然后中间连续读几个block(计算一下就好)，最后一个block可能只读部分。 感觉整体就是玩index。

见上面的word-ladder

36. valid-sudoku

• 给一个二维char数组，里面是一个未完成的数独9x9棋盘，要求每一行、每一列、每个3x3方块中数字1-9有且仅有出现一次。判断这个棋盘是否符合数独规则，返回布尔值。

public boolean isValidSudoku(char[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) {
        return false;
    }
    Set<String> set = new HashSet<>();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            if (board[i][j] != '.') {
                if (!set.add(board[i][j] + " in row " + i) 
                    || !set.add(board[i][j] + " in col " + j) 
                    || !set.add(board[i][j] + " in block " + (i / 3) + '-' + (j / 3))) {
                    return false;
                }
            }
        }
    }
    return true;
}

类似362. design-hit-counter详情母鸡

• 定义 eventOccur()，numEvent() 方法，有个sliding window size N。然后扩展，减少空间，Map，加一个功能，返回当前时间eventOccur() call次数最多的时间，要求 amortized O(1), 楼主一时想不到，最后只想到类似 LFU 的那种 2 map + DLL，1 个 map key 是 count，DLL 存 Cell(time, count)，一个就是整个cell。这个能保证O(logN), 面试官表示满意，方法不错，但是他后来是说，既然之前用了 queue 存所有 time + count，直接maintain 一个 max variable，每次 max variable 超过了 sliding window，则遍历 剩下的queue里的 count 就好，对于无限流，这个就是 amortized O(1), 但是楼主想不通，就举了个，每次 时间下 call evenOccur() 次数是递减的，那么就是每次都是O(n); 面试官表示是的，这个特殊的例子是O(n), generally 还是每 N 次才更新。

---

以下是卡拉特面经

统计点击率

• 给一堆网址和点击率，求不同部分域名的点击率。如mobile.sports.yahoo.com就需要统计四个部分。lc 811
• split之后搞就行了。

public List<String> subdomainVisits(String[] cpdomains) {
    List<String> ans = new ArrayList<>();
    if (cpdomains == null || cpdomains.length == 0) {
        return ans;
    }
    Map<String, Integer> map = new HashMap<>();
    for (String cpdomain : cpdomains) {
        String[] data = cpdomain.split(" ");
        int count = Integer.parseInt(data[0]);
        int index = 0;
        while (index >= 0) {
            String key = data[1].substring(index == 0 ? index : index + 1);
            map.put(key, map.getOrDefault(key, 0) + count);
            index = data[1].indexOf(".", index + 1);
        }
    }
    for (String key : map.keySet()) {
        ans.add(map.get(key) + " " + key);
    }
    return ans;
}

求最长公共子数组

• 实现一个函数取两个数组作为input，求这两个数组的最长公共元素。

public static String[] longestCommonSubarray(String[] log1, String[] log2) {
    if (log1 == null || log2 == null || log1.length == 0 || log2.length == 0) {
        return null;
    }
    int maxLen = 0, end = -1;
    int[][] dp = new int[log1.length + 1][log2.length + 1];
    for (int i = 0; i <= log1.length; i++) {
        for (int j = 0; j <= log2.length; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else {
                if (log1[i - 1].equals(log2[j - 1])) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    if (dp[i][j] > maxLen) {
                        maxLen = dp[i][j];
                        end = i;
                    }
                }
            }
        }
    }
    if (maxLen == 0) {
        return new String[] {"None"};
    }
    String[] ret = new String[maxLen];
    for (int i = 0; i < ret.length; i++) {
        ret[i] = log1[end - maxLen + i];
    }
    return ret;
}

矩阵中最长上升序列

• 给一个矩阵，求最长上升序列的长度。lc 329.

public static int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return 0;
    }
    int rowTotal = matrix.length, colTotal = matrix[0].length, len = 0;
    int[][] cache = new int[rowTotal][colTotal];
    for (int i = 0; i < rowTotal; i++) {
        for (int j = 0; j < colTotal; j++) {
            len = Math.max(len, getLen(matrix, cache, i, j));
        }
    }
    return len;
}
private static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static int getLen(int[][] matrix, int[][] cache, int i, int j) {
    if (i < 0 || i > matrix.length || j < 0 || j > matrix[i].length) {
        return 0;
    }
    if (cache[i][j] > 0) {
        return cache[i][j];
    }
    int len = 1;
    for (int[] dir : dirs) {
        int rowNext = i + dir[0];
        int colNext = j + dir[1];
        if (rowNext < 0 || rowNext >= matrix.length
            || colNext < 0 || colNext >= matrix[rowNext].length
            || matrix[rowNext][colNext] <= matrix[i][j]) {
            continue;
        }
        int nextLen = getLen(matrix, cache, rowNext, colNext);
        len = Math.max(nextLen + 1, len);
    }
    cache[i][j] = len;
    return len;
}

2018.9.20 电面

• 给一个String，只含有数字和加、减。实现eval返回算式的结果。
• 遇到符号就把前面的数字累加/减即可。

public int calculate(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int val = 0, num = 0, sign = 1;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + (int)(c - '0');
        } else if (c == '+' || c == '-') {
            val = val + sign * num;
            num = 0;
            sign = c == '+' ? 1 : -1;
        }
    }
    val = val + sign * num;
    return val;
}

• follow-up: 除了上面这些，还含有括号。lc 224。利用Stack，遇到加减还是直接算个num出来，遇到左括号说明前面的计算告一段落，将前面的数字和符号都push进stack，遇到右括号时就说明当前括号以内的结果出来了，就从栈顶取数值和符号，合并出整体num之后再继续往后。

public int calculate(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int val = 0, sign = 1;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < s.length(); i++) {
        if (Character.isDigit(s.charAt(i))) {
            int num = s.charAt(i) - '0';
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                num = num * 10 + (int)(s.charAt(++i) - '0');
            }
            val += sign * num;
        } else {
            if (s.charAt(i) == '+') {
                sign = 1;
            } else if (s.charAt(i) == '-') {
                sign = -1;
            } else if (s.charAt(i) == '(') {
                stack.push(val);
                stack.push(sign);
                val = 0;
                sign = 1;
            } else if (s.charAt(i) == ')') {
                val = stack.pop() * val + stack.pop();
            }
        }
    }
    return val;
}

• follow-up2: 如果再输入一个map包含一些exp: val对，但是算式中并不是所有的变量都能找到对应的val。可以考虑用replaceAll+正则表达式将输入字符串中的部分换成有效数字。然后还是用stack，只不过现在需要一个类来把数字、字符串、符号wrap起来。

public static String calculate(String s, Map<String, Integer> map) {
    if (s == null || s.length() == 0) {
        return null;
    }
    for (String key : map.keySet()) {
        String regStr = String.format("(?<!\\w)%s(?!\\w)", key);
        s = s.replaceAll(regStr, Integer.toString(map.get(key)));
    }
    System.out.println(s);
    Stack<Part> stack = new Stack<>();
    Part curr = new Part(0, null, 1);
    for (int i = 0; i < s.length(); i++) {
        if (Character.isDigit(s.charAt(i))) {
            int num = s.charAt(i) - '0';
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                num = num * 10 + (int)(s.charAt(++i) - '0');
            }
            curr.num += curr.sign * num;
        } else {
            if (s.charAt(i) == '+') {
                curr.sign = 1;
            } else if (s.charAt(i) == '-') {
                curr.sign = -1;
            } else if (s.charAt(i) == '(') {
                stack.push(curr);
                curr = new Part(0, null, 1);
            } else if (s.charAt(i) == ')') {
                Part prev = stack.pop();
                curr.num = prev.sign * curr.num + prev.num;
                if (curr.var != null && prev.sign < 0) {
                    curr.var.setCharAt(0, curr.var.charAt(0) == '+' ? '-' : '+');
                    if (prev.var != null) {
                        curr.var.insert(0, prev.var);
                    }
                }
            } else if (s.charAt(i) == ' ') {
                continue;
            } else {
                StringBuilder sb = new StringBuilder().append(s.charAt(i));
                while (i + 1 < s.length() && s.charAt(i + 1) != ' '
                        && s.charAt(i + 1) != '+' && s.charAt(i + 1) != '-'
                        && s.charAt(i + 1) != '(' && s.charAt(i + 1) != ')') {
                    sb.append(s.charAt(++i));
                }
                if (curr.sign > 0) {
                    sb.insert(0, '+');
                } else {
                    sb.insert(0, '-');
                }
                if (curr.var != null) {
                    sb.insert(0, curr.var);
                }
                curr.var = sb;
            }
        }
    }
    return curr.toString();
}

2018.3.14电面

• 给一个二维String数组，每一行存放每个点赞记录url, user, timestamp。1.求每个网站的最早点赞记录。2.给一个user，求与他点赞过的url重复最多的用户。
• 第一问略。第二问，将数据存入user -> set(url)，和url -> set(user)，根据给定user找到他点赞过的url集合，然后对于里面的每个url找点赞过的用户集合，统计每个用户出现的次数即可。注意这个不是最省memory的方法，可以只维护url2User，同时把这个user访问过的url存入Set，这样就可以只遍历这个set了而不用额外维护每个user访问过那些网站。

public static String getCommonUser(String[][] logs, String user) {
    if (logs == null || logs.length == 0 || user == null) {
        return null;
    }
    Map<String, Set<String>> user2Url = new HashMap<>();
    Map<String, Set<String>> url2User = new HashMap<>();
    for (String[] log : logs) {
        user2Url.putIfAbsent(log[0], new HashSet<String>());
        user2Url.get(log[0]).add(log[1]);
        url2User.putIfAbsent(log[1], new HashSet<String>());
        url2User.get(log[1]).add(log[0]);
    }
    if (!user2Url.containsKey(user)) {
        return null;
    } 
    Set<String> urls = user2Url.get(user);
    int max = 0;
    String ret = null;
    Map<String, Integer> overlapCount = new HashMap<>();
    for (String url : urls) {
        Set<String> users = url2User.get(url);
        for (String curr : users) {
            if (curr.equals(user)) {
                continue;
            }
            overlapCount.put(curr, overlapCount.getOrDefault(curr, 0) + 1);
            if (overlapCount.get(curr) > max) {
                max = overlapCount.get(curr);
                ret = curr;
            }
        }
    }
    return ret;
}

2018.9.15 电面

• 给一堆edges。1. 找nodes that have no parents, and nodes that have 1 parent； 2. 找graph中两个node有无common ancestor（直接相连的不算共同祖先）；3. 找furthest ancestor from node。

public static List<Integer> getIndependentNode(int[][] edges) {
    if (edges == null) {
        return null;
    }
    Map<Integer, Set<Integer>> parentMap = getParentMap(edges);
    List<Integer> ans = new ArrayList<>();
    for (int key : parentMap.keySet()) {
        if (parentMap.get(key).size() <= 1) {
            ans.add(key);
        }
    }
    return ans;
}
public static boolean hasCommonAncestor(int[][] edges, int node1, int node2) {
    Map<Integer, Set<Integer>> parentMap = getParentMap(edges);
    Set<Integer> ancestorSet = new HashSet<>();
    Queue<Integer> q = new LinkedList<>();
    q.offer(node1);
    while (!q.isEmpty()) {
        Set<Integer> parentSet = parentMap.get(q.poll());
        for (int parent : parentSet) {
            q.offer(parent);
            ancestorSet.add(parent);
        }
    }
    
    q.offer(node2);
    while (!q.isEmpty()) {
        Set<Integer> parentSet = parentMap.get(q.poll());
        for (int parent : parentSet) {
            if (ancestorSet.contains(parent)) {
                return true;
            }
            q.offer(parent);
        }
    }
    return false;
}
public static int getFurthestAncestor(int[][] edges, int node) {
    int ret = -1;
    if (edges == null) {
        return ret;
    }
    Map<Integer, Set<Integer>> parentMap = getParentMap(edges);
    if (parentMap.get(node).isEmpty()) {
        return ret;
    }
    Queue<Integer> q = new LinkedList<>();
    q.offer(node);
    while (!q.isEmpty()) {
        ret = q.peek();
        int size = q.size();
        while (size-- > 0) {
            Set<Integer> parentSet = parentMap.get(q.poll());
            for (int parent : parentSet) {
                q.offer(parent);
            }
        }
    }
    return ret;
}
private static Map<Integer, Set<Integer>> getParentMap(int[][] edges) {
    if (edges == null) {
        return null;
    }
    Map<Integer, Set<Integer>> parentMap = new HashMap<>();
    for (int[] edge : edges) {
        parentMap.putIfAbsent(edge[0], new HashSet<>());
        parentMap.putIfAbsent(edge[1], new HashSet<>());
        parentMap.get(edge[1]).add(edge[0]);
    }
    return parentMap;
}