Google 2019/03/15 Onsite

RicciWoo 发表于 2019-3-16 21:38
这是这道题好玩的地方，不用notification机制的。
一开始我的想法是，每次先把absolution时间需要最早执 ...

恕我愚钝，没看明白这个定时系统是什么意思
是说有个定时系统，对于所有的callback，都在给定时间提交，那自己写的这个callback意义在哪呢？我直接提交原来的callback不就好了？
或者麻烦楼主给举个例子？

zorrowei 发表于 2019-3-17 04:51
第五轮的这个循环法：珀斯特顺序遍历二叉树，对空间复杂有要求么？可以就是常规的while-loop加一个站么？

对空间没有要求，但是给定node的通常结构不能修改

bdhmwzfa 发表于 2019-3-17 09:09
大概明白了
那么这道题其实也可以用拓扑排序的，只不过排序方法不一样，按照入度进行排序，入度为零的点 ...

这个我也没想出来怎么做，欢迎讨论

RicciWoo 发表于 2019-3-17 09:36
这个我也没想出来怎么做，欢迎讨论

我现在的想法是，优先选择那些从当前节点出发最长路径最长的那些点
比如现在有三个点可以选A B C，而这三个点向下执行最长路径分别为6 3 3，那么肯定优先选择A，因为选择A，也许能把总时间控制在6，不选肯定要超过6的，我还没想出反例来
至于有tie的情况，可以随意选择？

RicciWoo 发表于 2019-3-16 21:27
切巧克力确实是用copy books的思路，binary search，或叫二分答案。
schedule jobs，我面试一开始就说用 ...

如果是树的话，我提出一个greedy的想法：谁的子孙多，就prioritize。

1. 
   
2. 0
   
3.             1         2
   
4.           3   4     5   
   
5.         7             12
   
6.      15    16
   
7.    31 32  33 34
   
8. 
   
9. 如果只有两个工人，那么顺序应该是：
   
10. 0
    
11. 1,2
    
12. 3,5 （4的子孙是0， 所以后做）
    
13. 7,4
    
14. 15,16
    
15. 31,32
    
16. 33,34

复制代码

如果是DAG就不能用这个方法，因为还有虽然谁谁谁没有子孙但是做了它可以开启下面的node。除了笨办法，还没想出来。

14417335 发表于 2019/03/17 21:13:10


如果是树的话，我提出一个greedy的想法：谁的子孙多，就prioritize。

[mw_shl_code=bash,false]
0
            1         2
...

狗家店面跪经
https://www.1point3acres.com/bbs/thread-503615-1-1.htmlhttps://www.1point3acres.com/bbs/thread-503615-1-1.html 有个好像是一样的题，这里有人发代码，是先用拓波找顺序再用heap算时间，十天内两题了有点高频啊

谢谢楼主分享

kaipeng21 发表于 2019-3-27 06:33
狗家店面跪经
https://www.1point3acres.com/bbs/thread-503615-1-1.htmlhttps://www.1point3acres.com/ ...

谢谢你的分享，可能是遇到了同一个面试官，应该是TF组做compiler相关的印度人

所以lz，第四轮工人那题的follow up是用匈牙利算法吗？

mooc 发表于 2019-3-31 12:34
所以lz，第四轮工人那题的follow up是用匈牙利算法吗？

我没做完，所以没有follow up啊