拼扯惹斯特

Posted on | Edited on | In | | Views:
Symbols count in article: 91k | Reading time ≈ 1:35

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

2018.8.9

269. alien-dictionary x3
  • 给一个按照某种外星人字典序排好序的String数组，只包含小写字母，求这些出现过的字母的顺序。若有多种可能（平级）则任意顺序均可。
  • topo排序问题，前后两个字符串逐个字符找到第一对不同的字符，确定先后顺序（前->后）构成一条边，两两字符串全部遍历完之后就形成了一个graph。维护一个inDegree，每次BFS时从入度为0的节点出发，将它可达的所有邻接点的入度都减1（删掉这些边），最后如果全部字符都遍历到了即可。如果出现了环，则一定会又入度不为0的点残留。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    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时每次从特定位置开始找/，然后取出它前面的长度信息直接截取后面的子字符串。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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)].

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public 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.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    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元素即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    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来找到元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    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都先算它有四条边，然后根据邻接情况减掉不是边的即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    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(无重复元素全排列)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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(有重复元素全排列)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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中。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    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，说明不存在。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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，然后从头取元素即可。或者用分治法递归来搞，
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    public 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)搞定，对于每个人，一旦他认识别人、或者别人不认识他就跳出循环。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /* 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是不是不认识所有人、且所有人都认识他。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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吧。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    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）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    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一下即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    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即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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字符串」。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    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计数记录用了多少个除数，这就是所求的商了，也是累计即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    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
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    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就是当前的最小操作数了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    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，并返回实际读取的字符数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    public class Solution 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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    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存放所有邻接点然后逐一上色。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    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）。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    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右子树即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    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方法了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    public 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的就是最短了。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    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的邻居点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    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数量。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    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如

    1
    2
    3
    4
    5
    6
    7
    8
    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如

    1
    2
    3
    4
    5
    |---A (2)
    |    |---B (2)
    |    |    |---C (1)
    |    |    |---A (1)
    |---B (1)

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    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超了就将链表最后一个节点删除即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    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的计数。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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数组来记录。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    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的对应位置；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    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
  • 给一串字符串数组，求这些字符串开头的公共部分。
  • 直接按照字典序排序，找首位和末尾的字符串比较看看有多少公共部分即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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从后往前取元素不断累加.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    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的时候需要判断当前这一波是否真的存入了元素。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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的时候直接用两个位置的相减即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    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，

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    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。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    // 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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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数量保证是最大值即可。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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有且仅有出现一次。判断这个棋盘是否符合数独规则，返回布尔值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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之后搞就行了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    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，求这两个数组的最长公共元素。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    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.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    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返回算式的结果。

  • 遇到符号就把前面的数字累加/减即可。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    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之后再继续往后。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    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起来。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    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访问过那些网站。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    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。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    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;
    }