前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >包子大道消息: 老外海归 &Baozi Training Leetcode 207 Course Schedule

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

作者头像
包子面试培训
发布2020-06-12 17:49:03
3660
发布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:

代码语言:javascript
复制
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:

代码语言:javascript
复制
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
代码语言:javascript
复制
 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
代码语言:javascript
复制
 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
代码语言:javascript
复制
 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)

References

  • Leetcode official solution
  • GeeksforGeeks Detect Cycle in a directly graph using topological sort
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-06-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 包子铺里聊IT 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem Statement
  • Video Tutorial
  • Thought Process
  • Solutions
    • Use adjacency lists BFS
      • Use simple hashmap BFS
        • Use recursion DFS
        • References
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档