d********n
发帖数: 54 | 1 本人PhD，3年半工作经验。2个月前收到Google recruiter电话，开始面试，一个月前
拿到offer，然后开始了漫长的谈判，昨天终于签字。上来share一下面经。
2年前面过google，职位不喜欢，把它拒了。因为他们有记录，所以这次只安排了4人面
试。
第一个是老美，先问了一些简单问题，比如怎么判断一个32 bit是big endian 还是
small endian等等。最后出了一道算法题，也很容易，给定K个sorted array，要求输
出一个大的sorted array。简单的merge sort就解决了。不过merge sort 要求每次K个
array中，最小的element。简单的当然是scan这K个array。我提出可以把K个array的当
前element放入Heap structure，这样每次搜索就从O(K)降低到O(logK)。最后写了个程
序。
第二个是老中。也是先问了一些简单问题，然后让我设计一个分布式文件系统，给定
path name，可以读写文件。具体的system design这里就不提了。其中一个细节是，给
定path name，怎么知道哪个node拥有这个文件。我提出需要实现一个lookup function
，它可以是一个hash function，也可以是一个lookup table。如果是lookup table，
为了让所有client sync，可以考虑额外做一个lookup cluster。然后Interviewer很纠
结，既然可以用hash function，为什么还搞得那么复杂。我就告诉他hash function的
缺点。假定一开始有N个node，hash function把M个文件uniformly distribute到N个
node上。某天发现capacity不够，加了一个node。首先，要通知所有的client machine
，configuration 改变了。如果不想重启client machine的process，这不是一个
trivial job。其次，文件到node的mapping也变了。比如，本来按照hash function，
一个文件是放在node 1。加了一个node 后，它可能就map到node 2了。平均来说，N/(N
+1)的文件需要move到新的node。这个data migration还是很大的。然后我就提出一些
hash function的design，可以减少data migration。
最后他提了一个问题，说要实现一个function，要统计distributed file system所有
目录的大小。前提是，一个目录下的文件可能放在不同的node上。我说这个不就是在每
个node上统计，然后发到一个merge吗。他说对，但是又问用什么data structure来表
示。我说这就是hash table，key就是directory name，value就是大小。因为
directory本身是树结构，这个hash table的key可以用tree来组织。最后让我实现一个
function，把我说得这个data structure serialize成byte array。因为这个byte
array就是网络传输的data。我用了depth first traverse。不过等我程序写完，才发
现，用breath first traverse会更方便，code也会很简洁。
第三个也是老中。他可能没有很好的准备，问题一开始有点含混不清。花了一点时间，
基本明确，他是要我用pthread实现thread pool，以及thread job management。先是
define class interface，然后用pthread的mutex和semaphore实现了consumer/
producer queue。这个queue允许users（producers)加入thread jobs，thread
managers(consumers)拿出thread jobs，并执行。当场design class interface，并做
到面面俱到有点难，好在
我山寨了Java的thread class。有了interface，implementation还是比较容易的。他
顺便也问了一些multiple thread的问题，比如怎么做singleton等等。
第四个是老印。他问了一道算法题，假定有个graph，怎么找出不带circle的最长path
。我纠结了很久，最后用dynamic programming 解决的。好在他主要focus在idea上面
，没让我把code写完。等我想清楚算法，一半时间已经过去了。要写完code，我还真做
不到。
总的感觉，我面了不少公司，google是最难的。尽管人数不多，但全是engineer，问得
全是technical，而且都要求white board coding。这次好在也没问太复杂的算法题。
问得一些CS的基本概念，以及system design，design pattern之类的，都是我擅长的
。Data structure方面，也集中在hash table，也是我用了很多的。唯一一个有难度的
是最后关于graph的，平时很少涉及。好在以前研究过dynamic programming，通常总能
套在这类问题上。 |
A*********r
发帖数: 564 | 2 太牛了，一个多月过去了，还记得题目。。
我面完回到家，忙其他的忙了一个多星期，到现在就只记得一道题了，面经都没法写。。
方便透露一下offer的大概么？
【在 d********n 的大作中提到】
: 本人PhD，3年半工作经验。2个月前收到Google recruiter电话，开始面试，一个月前
: 拿到offer，然后开始了漫长的谈判，昨天终于签字。上来share一下面经。
: 2年前面过google，职位不喜欢，把它拒了。因为他们有记录，所以这次只安排了4人面
: 试。
: 第一个是老美，先问了一些简单问题，比如怎么判断一个32 bit是big endian 还是
: small endian等等。最后出了一道算法题，也很容易，给定K个sorted array，要求输
: 出一个大的sorted array。简单的merge sort就解决了。不过merge sort 要求每次K个
: array中，最小的element。简单的当然是scan这K个array。我提出可以把K个array的当
: 前element放入Heap structure，这样每次搜索就从O(K)降低到O(logK)。最后写了个程
: 序。
|
g******d
发帖数: 511 | 3 最后一题的graph是directed还是undirected? |
d********n
发帖数: 54 | 4 undirected
【在 g******d 的大作中提到】
: 最后一题的graph是directed还是undirected?
|
p********7
发帖数: 549 | 5 多半是有向
【在 g******d 的大作中提到】
: 最后一题的graph是directed还是undirected?
|
p********7
发帖数: 549 | 6 很多和工作经验有关的啊，和针对fresh的题目有点不用呢 |
g*********s
发帖数: 1782 | 7 第四题，longest simple path in graph是NPC问题啊。你怎么用dp解决的？
如果是DAG，确实存在线性的dp解法。
【在 d********n 的大作中提到】
: 本人PhD，3年半工作经验。2个月前收到Google recruiter电话，开始面试，一个月前
: 拿到offer，然后开始了漫长的谈判，昨天终于签字。上来share一下面经。
: 2年前面过google，职位不喜欢，把它拒了。因为他们有记录，所以这次只安排了4人面
: 试。
: 第一个是老美，先问了一些简单问题，比如怎么判断一个32 bit是big endian 还是
: small endian等等。最后出了一道算法题，也很容易，给定K个sorted array，要求输
: 出一个大的sorted array。简单的merge sort就解决了。不过merge sort 要求每次K个
: array中，最小的element。简单的当然是scan这K个array。我提出可以把K个array的当
: 前element放入Heap structure，这样每次搜索就从O(K)降低到O(logK)。最后写了个程
: 序。
|
h**********d
发帖数: 4313 | |
P*****o
发帖数: 294 | |
x******3
发帖数: 245 | |
b*****c
发帖数: 165 | 11 "然后我就提出一些
hash function的design，可以减少data migration。"
LZ能否透露一下是怎么样的design? |
e**********6
发帖数: 78 | 12 LZ第一题用的是K-way mergesort？这题似乎直接用普通的2-way mergesort就能挺好的
解决？另外每次在push数组第一个元素进入heap的时候，max-heapify都要花O(logk)，
所以每次遍历一边数组的第一个元素，时间复杂度就是O(k*logk)。而每次扫一遍，只
花log(k)。。。个人感觉用了heap反倒提升了复杂度？ |
