给Google onsite面经添砖加瓦

代号9527 发表于 2016-11-11 23:42
恭喜大神，请问过完hc就是offer吗还是要先team match？

谢谢！今年new grad都是先offer再match的！

chaosMonkey 发表于 2016-11-11 19:11
g家的问题都是这么难吗？

同意楼上观点。而且我的面试官都会或多或少地帮我往正确的思路上指引，所以乍一看觉得难的题最后也都能做出来，回想也没那么可怕。

做lz第二轮第二题，才发现python的yield真是好用

1. def derived_gen(gen):
   
2.   while True:
   
3.     n = gen.next()
   
4.     val = gen.next()
   
5.     for i in xrange(n):
   
6.       yield val
   
7. 
   
8. for n in derived_gen(iter([2, 3, 0, 5, 3, 2, 1, 8]))
   
9.   print n
   
10.       

复制代码

zzgzzm 发表于 2016-10-24 14:37
第四轮 药片题：药瓶中每一个状态是由w（整片个数）， h（半片个数）以及到达该状态的概率p唯一决定的。这 ...

这种方法占用的空间开销太大了吧？

luofeidream 发表于 2016-11-24 08:16
这种方法占用的空间开销太大了吧？

的确是。。。对于level order traversal的办法，level k就有组合数C(k,k/2)个nodes，而这个数是远远大于O(2^(k/2))量级的，所以时间空间代价都远远大于O(2^(k/2))  (k=198天)。其实我在写level order traversal的办法时也觉得这是只是理论上的推导，因为大量细小的概率乘机载求和那么在实现时精度早就没有了。

我在想除非这个就应该当个纯数学题来解，感觉和二项式系数有关系，但也没看出具体的线索。其实在第198天时的状态无非就是(1,0)或(0,2)，但它们各自的概率是什么以及有没有对称性似乎都很难讲。我目前还没有想出explicit的数学表达式结果（关键是转移概率总是随时间动态变化的）。

妈呀这论坛发代码怎么这么丑。。发GIST了。。。。
两种O(n^2)的算法。。第一种是维护两天的状态和到达状态的概率。
这种方式的空间复杂度是O(N),因为只有两个数组prevDay和currDay,而且也不涉及浮点运算精度问题。时间复杂度是O(MN),因为需要循环N天，每次循环都要遍历数组。

第二种算法就是上面说的dfs+memorization，按照我的思路，dfs()应该有两个参数，就是当前的两种药片数，返回值是从这个state到目标target的概率。这样可以把概率memorization起来。

抛砖引玉。。。何况可能连砖都不是。。轻拍





补充内容 (2016-11-24 15:41):
恩写多了。。还是涉及浮点运算问题的。。。

jfree811 发表于 2016-10-15 20:43
话说google面试的时候能和中国面试官说中文吗？之前看别人写的帖子有提到直接中文交流。

这个看面试官吧，他要是跟你讲中文面，你就回中文，他要是说英文，你就英文对他~见机行事

剧院的订座系统 怎么做的呀

感谢你的分享。有所启发受益了。谢谢

恭喜楼主啊~~~ 谢谢分享