Google Onsite

pawprinter 发表于 2016-9-20 08:03
请问第二题怎么算满足不查看周围8个value的要求？

假设棋盘如下
1 4 7 10
2 5 8 11
3 6 9 12

你算5的时候就已经知道4和7那一列有多少个活着的cell了，于是算8的时候就可以重复使用这个

iFrances 发表于 2016-9-21 01:57
LZ请问 game of life board无限大怎么处理呢?

我说的就是把board分割后分机器存，然后只存活的cell在hashmap里

第四题的解法， 面试的时候写出来就屌了

Dynamic graph
http://courses.csail.mit.edu/6.851/spring14/scribe/L20.pdf

楼主面得是Google Seattle?

lz什么时候收到最终结果的呢？

kevinwangjk 发表于 2016-9-18 05:00
用的是DFS，起点为所有碰到X=0和Y=1的边的censor，终点是X＝1或者Y＝0的边，如果有一条censor形成的path ...

还是没看懂，SENSOR的探测范围不是一个圆么，如何DFS？

kevinwangjk 发表于 2016-9-18 05:02
我想了好久想不出什么好办法，结果他最后提示就是每次删朋友后要重新建立所有有关人的关系图。每个人有一 ...

每次求间接朋友关系可以用DFS吧，当然如果想要O1的找到间接朋友关系确实是需要每次删除都重新构建间接朋友关系图

xpli521 发表于 2016-9-18 05:54
原来是这个意思，那楼主你看看下面这个思路可行吗，
class Person{
  int id;

感觉就算B在A的直接朋友里，还要考虑B是不是也在A的间接朋友里，比如A和B直接加了好友，但也可能A加了C，C也加了B，所以B也是A的间接好友

kevinwangjk 发表于 2016-9-18 08:12
用个BST存interval，然后加interval的时候merge重复的，key用lower bound

如果你的BST是
       [4, 6]
[1, 3]     [8, 9]

下一个interval是[3, 5]。合并之后的BST应该是
       [1, 6]
              [8, 9]

这个合并怎么写，递归向下？

hxtang 发表于 2016-9-19 02:51
删除A-B的时候肯定是要访问所有A的间接朋友和B的所有间接朋友
我觉得导致慢的可能是对A的每个间接朋友C ...

请问大神，game of life那题，board 无限大时该怎么处理。。。。
碰见这种输入 是 stream啊， 什么什么无限大啊， 就没思路了