包子大道消息: 老外海归 &Baozi Training Leetcode 207 Course Schedule

包子面试培训

发布于 2020-06-12 17:49:03

3720

发布于 2020-06-12 17:49:03

文章被收录于专栏：包子铺里聊IT

最近伴随着BLM各种运动，包子君发现TikTok上面各种这方面的短视频播放率非常高，老外各路人马upload的内容非常详实，而且下面的评论也非常active，所以越来越觉得字节可能真的是会我们中国公司出海的一匹黑马。???

大概10多年前国内公司也许还会有外来的和尚会念经这种想法（咦，我怎么突然想起来施拉普纳，米卢，里皮了呢？又暴露年龄了）。现在中国IT企业走出国门，强龙不压地头蛇，低调务实的本土化，实在是高，简单的总结一下这些洋教头吧（不包括我们本土选手陆奇，沈向洋和李开复 et al）

姓名: Kevin Mayer

外企履历: Disney 老兵，Chairman of streaming, 一身正气，“美国队长”

"海归"title：TikTok CEO，字节跳动COO，一个字，?

姓名: Hugo Barra

外企履历: Google VP on Andorid, 坊间据说被Google Cofounder Sergey 给绿了。。。

"海归"title: 小米Global VP，雷布斯天竺国“Are you okay”虎哥就在旁边，现在又回美国了，VP of VR @Facebook

姓名: Daniel Povey

外企履历: Associate Professor @CLSP at JHU

"海归"title: 小米 Chief Speech Scientist 。包子君也不知道这个事情最后到底怎么样了，不过技术大牛归国都是这种。华人有很多厉害的教授回去，阿里达摩院高僧很多。

姓名: James Mitchell

外企履历: Director at Goldman Sachs

"海归"title: SVP and Chief Stategy Officer at 腾讯，只是想说不仅仅是搞技术的，其他function的也有好多老外回去做高管的, 海纳百川嘛

图片均来自伟大的互联网，版权归原作者所有。

文章来源：https://www.theinformation.com/articles/tiktok-hire-signals-chinese-firms-growing-openness-to-western-executives

Blogger: http://blog.baozitraining.org/2020/06/leetcode-solution-207-course-schedule.html

Youtube: https://youtu.be/4vaaXaqNvek

博客园: https://www.cnblogs.com/baozitraining/p/12908513.html

B站: https://www.bilibili.com/video/BV1hp4y1Q7cz/

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
You may assume that there are no duplicate edges in the input prerequisites.
1 <= numCourses <= 10^5

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
Youtube BFS in 2015, Youtube DFS in 2015
B站

Thought Process

It is a classic dependency graph problem. We can translate this problem to direct if there is a cycle in a directed graph or not. A text book solution is Kahn's algorithm for topological sorting. We can have a simple way to represent the graph or use a more proper adjacency lists (a little bit overkill for this problem though)

Solutions

Use adjacency lists BFS

 1 private class Node {
 2     public int val;
 3     public List<Node> neighbors;
 4 
 5     public Node(int val) {
 6         this.val = val;
 7         this.neighbors = new ArrayList<>();
 8     }
 9 }
10 
11 private List<Node> buildGraph(int num, int[][] prerequisites) {
12     List<Node> graph = new ArrayList<>();
13 
14     for (int i = 0; i < num; i++) {
15         graph.add(new Node(i));
16     }
17 
18     for (int i = 0; i < prerequisites.length; i++) {
19         graph.get(prerequisites[i][0]).neighbors.add(graph.get(prerequisites[i][1]));
20     }
21 
22     return graph;
23 }
24 
25 // model to a Nodes, still BFS with topological order to detect if a graph is a DAG
26 // https://www.geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs/
27 public boolean canFinishGraph(int numCourses, int[][] prerequisites) {
28     if (numCourses <= 1 || prerequisites.length == 0 || prerequisites[0].length == 0) {
29         return true;
30     }
31     List<Node> graph = this.buildGraph(numCourses, prerequisites);
32 
33     Queue<Node> q = new LinkedList<>();
34 
35     for (Node n : graph) {
36         if (n.neighbors.size() == 0) {
37             q.add(n);
38         }
39     }
40 
41     Set<Node> visited = new HashSet<>();
42     while (!q.isEmpty()) {
43         Node cur = q.poll();
44 
45         visited.add(cur);
46 
47         for (Node n : graph) {
48             if (n.neighbors.contains(cur)) {
49                 n.neighbors.remove(cur);
50                 // only enqueue the nodes while there is no more neighbors
51                 if (n.neighbors.size() == 0) {
52                     q.add(n);
53                 }
54             }
55         }
56 
57     }
58 
59     return visited.size() == numCourses;
60 }
61 @shixiaoyu
62

Time Complexity: O(V), since each vertex is visited only once during BFS Space Complexity: O(V+E) since we use adjacency lists to represent a directed graph

Use simple hashmap BFS

 1 public boolean canFinishBfsTopoSort(int numCourses, int[][] prerequisites) {
 2     if (numCourses <= 1 || prerequisites.length == 0 || prerequisites[0].length == 0) {
 3         return true;
 4     }
 5 
 6     Map<Integer, Set<Integer>> graph = new HashMap<>();
 7 
 8     // could be extracted into a build graph function
 9     for (int i = 0; i < numCourses; i++) {
10         graph.put(i, new HashSet<>());
11     }
12 
13     for (int i = 0; i < prerequisites.length; i++) {
14         graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
15     }
16 
17     int coursesRemaining = numCourses;
18     Queue<Integer> queue = new LinkedList<>();
19 
20     // initialize
21     for (Map.Entry<Integer, Set<Integer>> entry : graph.entrySet()) {
22         // this is the reverse as the graph topological order, but it is the actual problem solving order
23         // e.g., a->b, -> reads as depends on, meaning you have to finish b to do a, so it will print out b, a
24         if (entry.getValue().size() == 0) {
25             queue.offer(entry.getKey());
26             coursesRemaining--;
27         }
28     }
29 
30     // BFS
31     while (!queue.isEmpty()) {
32         int key = queue.poll();
33         System.out.println("** key: " + key);
34         for (Map.Entry<Integer, Set<Integer>> entry : graph.entrySet()) {
35             Set<Integer> curDependencies = entry.getValue();
36 
37             if (curDependencies.contains(key)) {
38                 curDependencies.remove((Integer)key); // need to cast or else it will be remove(int index)
39                 if (curDependencies.size() == 0) { // immediately check to avoid another loop
40                     queue.offer(entry.getKey());
41                     coursesRemaining--;
42                 }
43             }
44         }
45     }
46 
47     return coursesRemaining == 0;
48 }

Time Complexity: O(V), since each vertex is visited only once during BFS

Space Complexity: O(V) since we are using a hashmap

Use recursion DFS

 1 // This is a DFS solution, basically just like detecting if a graph has loops.
 2 // Used a lookup table prune, with lookup, this is O(V + E), same as BFS since each node is visited once and only once
 3 public boolean canFinish(int numCourses, int[][] prerequisites) {
 4     if (numCourses <= 1 || prerequisites.length == 0 || prerequisites[0].length == 0) {
 5         return true;
 6     }
 7 
 8     // this is adjacency list, used a set to dedup
 9     Map<Integer, Set<Integer>> graph = new HashMap<>();
10 
11     for (int i = 0; i < numCourses; i++) {
12         graph.put(i, new HashSet<>());
13     }
14 
15     for (int i = 0; i < prerequisites.length; i++) {
16         graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
17     }
18 
19     Map<Integer, Boolean> lookup = new HashMap<>();
20 
21     boolean[] visited = new boolean[numCourses];
22     for (int i = 0; i < numCourses; i++) {
23         if (!this.explore(i, graph, visited, lookup)) {
24             return false;
25         }
26     }
27     return true;
28 }
29 
30 // This is the DFS way to solve it, This could also generate a topological order, think about post order way
31 // return false if there is a loop, true if no loop
32 private boolean explore(int vertex, Map<Integer, Set<Integer>> graph, boolean[] visited, Map<Integer, Boolean> lookup) {
33     // keeps track of if the node has been visited or not,
34     // with this lookup, it's pruning (memorization so that we don't need to re-calculate previously visited node)
35     /*
36            1
37          /    \
38        0       3  - 4
39          \ 2  /
40       e.g., when recursion 0 -> 1 -> 3 -> 4
41                  in 2nd round, 0 -> 2 -> 3(could directly return)
42      */
43     if (lookup.containsKey(vertex)) {
44         return lookup.get(vertex);
45     }
46 
47     visited[vertex] = true; // keeps track of visited or not during recursion
48 
49     Set<Integer> dependencies = graph.get(vertex);
50     for (Integer i : dependencies) {
51         if (visited[i] || !this.explore(i, graph, visited, lookup)) {
52             return false;
53         }
54     }
55     visited[vertex] = false;
56     lookup.put(vertex, true);
57     return true;
58 }

Time Complexity: O(V), since each vertex is visited only once during BFS

Space Complexity: O(V) since we used a lookup hashmap for memorization purpose (not considering function stack space)