新鲜 狗家面经 Phone

楼主让朋友内推，投了三个岗位，SDE - General， SDE - Fed ML， Applied Scientist - AI

SDE - Fed ML 第二天秒拒，楼主有这方便的paper，也不care，所以估计这个岗位要找博士期间纯做Fed ML的人吧
Applied Scientist - AI 这个本来就很难，不是有high influence paper或者有大佬力挺，估计也没戏，不意外，过了一周rej了
然后就有HR联系我，问 只有SDE - General 愿不愿意来试试，从refer到安排面试大概2周，约了2周之后的phone

这里说一点的是，狗家的面试体验很不错，HR 很热情，各种鼓励你，跟你沟通。

这里是phone面试details， 纯phone interview，没有video：
0. 听声音一个白人小哥，上来时候手机信号不太好，我听不清他说的话，就让他检查一下mic，白人小哥没说话。。。我就说你能不能听清我？小哥秒回，可以。我就没纠结，想着大不了多问几次好了。白人小哥直说了他在google，工作了4年，没说他自己名字。。然后废话不多说，说我们开始coding吧。

1. 题目：你有一堆路由器，如果一个路由器和另外一个路由器之间的距离小于10，就可以用一个路由器把另外一个路由器点亮。然后给你一个路由器的list，每个list的element存的是路由器的2维坐标，请问如果你知道了一个起始路由器，那个一个目标路由器会不会被点亮。

2. 楼主clairfy完问题之后，说了用graph上的bfs来解，然后小哥说可以，就让我开始写。g家都是白板，不要求comppile，但是需要你口头run 结果。楼主一边写，一些给注释，每次写之前都会给intuition和要写什么function，比较可惜的是小哥从头到尾没有一点feedback。快写完的时候，我说：如果你有什么问题或者疑惑，随时stop me，我们可以讨论，小哥又是没说话。。。我猜可能在一边工作一边面试？

3. 写完之后，小哥自言自语的看了一遍代码，然后跟我说他不熟悉python，让我写一个test case带他走一遍。走完之后，问我，你会自己怎么设计test case，我说考虑graph 为 空，或者graph 有 seperated connected component的case，也给了两个例子，小哥没有comments，全程只是我在单方面输出。

4. clarify + 写题 + test case用了30min，这个地方就比较诡异了，小哥突然说，我们时间还很多，该干点啥。 我黑人问号？？！，不应该给我下一道题？我们接着做？之前看地理的都是2道题，小哥突然说那你给我分析一下复杂度吧，graph bfs，O(n), O(n) TIME, SPACE 分析完，小哥说，你有什么问题问我。

5. 我问了一下，组内做什么，答:knowledge graph, 对这个职位的applicant有什么要求，答：公司文化fit的相关pr文稿念了一些。回答简短，这个时候，结合只有一道题的coding，我隐约觉得有点不太对了，有follow up了一些kg相关的问题。

3天后，hr通知rej了，不给任何feedback，一年freeze。

怎么说呢，楼主刷了300多题，g家的高频提，面之前一周刷了70来个，面试的过程 我觉得是面试了很多家公司里发挥最好的，代码也没什么问题，一次过了。挂的比较诡异，楼主口语25，给过很多会议的presentation和tutorial，感觉表述应该没有太大问题。感觉可能已经有理想的更强的candidate了吧。

欢迎大家分析一下rej的原因，如果你觉得有帮助，请加一些大米，谢谢！

我怎么觉得更像是union-find的路数呢？题目只有坐标，那是不是应该两两遍历，看距离是不是在10之内，如果是就union到一起，最后只要判断两个路由的parents是不是一致。BFS做则先要两两遍历，距离在10以内建立一个graph的双向边，然后从源路由开始BFS到目标路由，感觉多一步

hmmm 面L4的话可能要更独立一点？ 可能你哪里写错了吧 不知

O(n)做不到吧

tianlong1989 发表于 2021-03-09 18:51:02
O(n)做不到吧

同意 zszszs

既然是坐标，普通的办法就说两两遍历check distance，那么可以排序了直接找neighbor+unionfind吧。

O(n)不对吧，input只有坐标，build graph的时候你必须两两check距离，这就O(n^2)了。但我觉得这个面试官真的也很不好，如果思路错了那他应该指出来或者给提示，全程不沟通是什么鬼。

BFS是O(E)，不是O(n)。这道题的E是n^2。假设这样的话楼主就错了两个地方（楼主刷了这么多题，不至于nested for loop看不到，仅仅假设），BFS的时间是错的，nested for loop又没分析对。

另,union-find在这种情况下应该不如BFS.

先建图， 然后在DFS吧 或者BFS也可以
不过这种不是找smallest length or path 就直接建图 然后dfs就Ok了吧