热乎的google电面

楼主刚刚结束google电面,不知道过没过,发个面经攒人品。
楼主在美东,本来是约的PST 下午一点的面试,以为是东部时间的下午五点,结果四点的时候就打过来了。看来其实应该是西部世界一点。之前朋友推荐了个模拟面试的网站,叫pramp。为了热身一下,我约了三点的模拟面试,四点钟刚结束电话就打过来了。
面试官是个女性美国人,开始寒暄了一下,因为楼主的简历上都是[数科]的项目,她就讲了一下数科的技术在sde中也需要用到。但是寒暄过程中没问我什么问题。
寒暄结束后,讲了一下题目。电话的效果不是很好,听得不是很清楚。幸好她在doc上写了一下例子,楼主又一遍又一遍的确认,终于搞懂了是什么意思。
题目很简单,说有一堆forecast,每个forecast都可能依赖于另一些forecas。如果要update某个forecast, 需要将dependency也update。给定一个forecast id,需要返回它所有需要update的Forecast id。
其实就是一个有向图,问你指向某个节点的所有节点。
这道题楼主之前见过,但是不记得了。如果是某个节点指向的所有节点,那就可以直接用dfs了。最后用的笨方法,reconstruct这个graph,让子节点指向父节点,然后再做dfs。
照例讲思路,说复杂度,然后就开写,边写边讲。写完之后跑两个测试用例。
follow up是问如果需要保证遍历的层级顺序怎么办,回答用bfs
又问如果需要做并行优化怎么办,其实我也不知道,就说了个每次在某个节点遍历子节点的时候用新的线程,每个层级设置线程锁。
最后让我问问题,我说好像可以不用reconstruct这个图,有没有什么别的做法,她说拓扑排序。
然后就时间到了,其实还超了几分钟。
不知道能不能过,我还问她我的表现怎么样,她说我的方法可以得到结果,pretty cool。不知道是不是一种暗示。
地里保佑,许愿能拿到onsite的机会。

补充内容 (2018-10-3 06:23):
更新一下,收到了onsite面试的邀请,非常快

请问这一题是怎么找到后面那些需要更新的子树的父节点的呢?感谢!已

reconstruct这个graph了,做dfs就可以了

您说的reconstruct这个graph具体是怎么做呢?

翻转所有有向图的边的方向