Google Zenefits Nvidia

Google

一面：Longest Consecutive Path in a Tree

二面：有一大坨candidate，每个人有一个ID integer，从中随机选择500个人参加Google的party，保证公平

Nvidia

一面：Search in rotated array，问了data mining的两个水问题，问了overfitting是什么，用线性的cost函数和quadratic的cost函数有什么trade off，一个收敛快，但容易有overfitting

二面：Seralize and Deseralize Binary Tree，问了奇葩的安卓问题，有一个安卓平板，你一直在往上面烧一个程序，这个程序让这个平板reboot，烧了一夜，第二天早上起来黑屏了，你怎么debug，除了看log你还怎么debug

三面：thread和process区别，不保护线程的后果是啥（deadlock），如何预防deadlock，java的多线程有哪些方式，写一个code把string abc变成abbccc，给了两段C代码改错，分别是防止buffer溢出和数组溢出

Zenefits

一面：有个vector<Iterator>，里面装了m个iterator，每个iterator是一个vector<int>的iterator，假设有next和hasNext接口，让你实现一个Zigzag traversal iterator

[

  [1,2,3]

  [5,4]

  [6,7,8,9]

一直调用next会返回1,5,6,2,4,7,3,8,9，先用了O(mn)的方法，m是最长的iterator的数组的长度，又改成queue或者cycle linkedlist，复杂度是O(k), k是总元素个数

Follow Up是，如果iterator有prev和hasPrev接口，实现Zigzag iterator的prev和hasPrev，用C++的deque和stack

二面：打印公司manager结构，要indent，follow up按字母序排序，聊了data mining project

bitware 发表于 2015-11-25 14:11
google二面那题怎么解，重复产生500个随机数，并且keep一个set么？

应该是用Reservoir sampling 这个做。

google二面那题怎么解，重复产生500个随机数，并且keep一个set么？

bitware 发表于 2015-11-25 14:11
google二面那题怎么解，重复产生500个随机数，并且keep一个set么？

楼主说的一大坨应该是指无法预先知道 N，所以不能直接用rand(1,N)的意思。那么我们只能慢慢从data stream读取S[i], 同时维护一个vector<int> R为最终产生的sample。也就是一楼说的reservoir sampling :
/*
  S has items to sample, R will contain the result
*/
ReservoirSample(S[1..n], R[1..k])
  // fill the reservoir array
  for i = 1 to k
      R[i] := S[i]

  // replace elements with gradually decreasing probability
  for i = k+1 to n
    j := random(1, i)   // important: inclusive range
    if j <= k
        R[j] := S[i]
具体可以用数学归纳法证明在iterator i到k的时候(k>500) 对于每个数1,2,...k被选中的概率都是500/k。所以k到 N 的时候，每个数字被选中的概率都相等 为500/N

crisc3 发表于 2015-11-25 15:58
楼主说的一大坨应该是指无法预先知道 N，所以不能直接用rand(1,N)的意思。那么我们只能慢慢从data stream ...

基本上就是这样的 赞赞赞 涨姿势