Google SDE（应该是level 4） onsite

考了4题coding， 1题behavior. 自己觉得coding的题很意外，也可能是因为是转专业的关系知识不够全面。但感觉只刷题是不够的了。。。1. 好像是binary tree sum， follow up是只能o(1) space, 感觉应该就是用morris算法，可惜已经记不得细节了.

2. 问了一些以前的项目， 一道k nearest points， follow up 是用machine learning optimize.
3. 不记得原题了， 但记得是2个follow up, 1个是要用"trial and error", 1个是区间合并还是overlap， 但只写了一个

4. 这个自己觉得非常意外，给了一个process grid （？）， n台机器，写个程序来优化process。interviewer解释的就是问怎么把这个process grid里面的sections分给n台机器最优，说可以ignore communication time (但是之前又花了很多时间讨论这个process grid的communication time是怎么算的。。。)。转专业的人全程懵逼。。。其实我连这个process grid应该长什么样子也是后来网上查到的。。。感觉应该是monte carlo之类的办法optimize，但是我想不出来loss function长什么样子。。。

我觉得很难，可能因为我是转专业的。感觉跟其他posts上看见的coding test不太一样，现在可能会需要准备更大范围才可以了？

helenship1 发表于 2020-1-30 06:11
刚才去问了别人才知道第4个题是关于优化partitioning the grid for parallel processing。。。原来真没见过 ...

看上去就像个一般的system design的题吧？（当然有专业术语process grid, etc.)

跟人继续讨论外加查paper, 这个grid partitioning其实是graph partition的一个应用，这里并不是要优化process的时间（这点完全搞错了），而是要让partition之后group之间的edge最少。wiki上面graph partition说的很清楚，是个np-hard的问题。graph partition有一些算法，但没听说过。🐶自己发的paper的算法比较复杂，简单说就是想办法降到一维，然后dp。high performance computing system的infrastructure，graph theory这些东西是by default是应该熟悉的？很复杂的降维处理是coding test要考的？在想要不要申诉一下，虽然对我可能也没什么用。但如果确实不合适，也该让recruiter知道，或许可以提醒这个面试官不要出题太随意，不是每个人都熟悉他熟悉的方向，毕竟这个只是general hire， job description和面之前发的大纲没有提这些。

以前课题和现在的工作都有用到过machine learning的方法，但是完全没有infrastructure的背景（这个是关键，没背景就理解不了这个grid partitioning），而且这次recruiter事前说的很清楚就是coding test， 没提machine learning的coding。第二题我也不sure用什么办法优化，就说了用clustering。

刚才去问了别人才知道第4个题是关于优化partitioning the grid for parallel processing。。。原来真没见过。。。

出题范围这么狂野。。。

发现有一篇google去年发的research paper, 提出一个graph partition的算法，主要用在google map上，也提到了用在了infrastructure上。应该就是这个grid partitioning。太难了。。。

楼主什么专业？毕业后有相关工作经验吗？

面SDE也要ML？

helenship1 发表于 2020/01/31 08:21:58
发现有一篇google去年发的research paper, 提出一个graph partition的算法，主要用在go...

求问一下paper的名字～～

Lz是面ml岗吗？还有第二题怎么用machine learning优化呀？