空起床 昂赛

上周五3/8面的onsite，hr说两天之内会联系我，结果等了两天也没啥消息，焦虑中发一下面经攒人品。
上午两轮算法，

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的OA，题目是round sum，OA做完followup call 然后onsite

hj867955629 发表于 2019-3-19 07:49
注意是7->0。没有入度为0，你不是就随便选一个点了吗？ 选了0就没办法保证最小了。
See https://www.1po ...

感觉没有问题，贴下我的code吧 (kotlin写的)

1. fun getMinV(edges: Array<Array<Int>>, n: Int) : MutableSet<Int>{
   
2.         (0 until n).forEach {
   
3.             graph[it] = HashSet<Int>()
   
4.         }
   
5. 
   
6.         for (edge: Array<Int> in edges) {
   
7.             graph[edge[0]]!!.add(edge[1])
   
8.         }
   
9. 
   
10.         val res = HashSet<Int>()
    
11.         val visited = HashSet<Int>()
    
12.         // Search from each vertice and find its source. Set of source would be the answer.
    
13.         for(i in 0 until n) {
    
14.             // If vertice is visited during previous DFS, its neighbors are traversed already. No need to go further.
    
15.             if (!visited.contains(i)) {
    
16.                 res.add(i)
    
17.                 visited.add(i)
    
18.                 // Search the vertex to update all its downstream vertex.
    
19.                 search(res, i, i, visited, HashSet<Int>())
    
20.             }
    
21.         }
    
22.         return res
    
23.     }
    
24. 
    
25.     private fun search(res: MutableSet<Int>, curr: Int, start: Int, visited: MutableSet<Int>, currVisited: MutableSet<Int>) {
    
26.         currVisited.add(curr)
    
27.         visited.add(curr)
    
28. 
    
29.         for (next in graph[curr]!!) {
    
30.             // If DFS meets some node already in res (and it's not start of this search), remove the node existing in res,
    
31.             // because current search will replace it as source.
    
32.             if (res.contains(next) && next != start) {
    
33.                 res.remove(next)
    
34.             }
    
35.             // If a node isn't searched in this round, keep searching it.
    
36.             // Note "currVisited.contains", instead of "visited". If vertice is in "visited", we still need to traverse further,
    
37.             // since it's likely we've found the real source for them, and will remove them from res.
    
38.             if (!currVisited.contains(next)) {
    
39.                 search(res, next, start, visited, currVisited)
    
40.             }
    
41.         }
    
42.     }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢分享！！

系统设计就是设计RSS 的newsfeed 面试官主要关注怎么建database的table, index, 不同table的join, sql vs nosql的比较，不同模型的trade off这些
都是之前地里说过的一些点，我系统设计准备的太仓促了，感觉也是所有轮中面的最不好的了。

请问最少点遍历有向图这道题用dfs+hashset就行了吧？不需要用什么scc吧？还有什么followup吗？

jason524 发表于 2019-3-18 16:54
试了dfs+hashset找source的解决方案，跑这个case没问题

注意是7->0。没有入度为0，你不是就随便选一个点了吗？ 选了0就没办法保证最小了。
See https://www.1point3acres.com/bbs ... p;page=2#pid6091607

楼主 文件系统是有watcher 的那个?要用trie做吗

有消息么？这都18号了