Google NYC onsite 感受分享

楼主是做什么方向的？属于前端还是后端呢？

楼主，family tree那个题目，用dfs具体是怎么解得啊，先把一个node的所有ancestor找出来然后dfs另一个node的ancestor的一个个试看看有重复的么？还是有什么更好的方法呢？
我的想法是从两个node开始bfs分别bfs，分别存一个visited的hashset看什么时候有交集，这样visited的总node数比较小ancestor每往上走一层数目要多一倍

还有directed graph那题问的是求连通还是强连通啊？如果只是连通是不是可以直接转化成undirected graph就行了啊，如果是强连通好像clrs上是楼主说的那个算法

lz请问可以具体说说这个题怎么并行处理吗 谢谢
2. Game of Life + followup 如果board很大怎么办 （并行/分布式处理）

blactangeri 发表于 2016-10-12 09:47
lz请问可以具体说说这个题怎么并行处理吗 谢谢
2. Game of Life + followup 如果board很大怎么办 （并行/ ...

这个题并行应该比较简单，不同的thread处理不同的区域，它们只share读上一个generation的数，不会发生冲突。如果是分布的话，每个机器分配一小块区域，不过需要互相传递一下边界上的update，因为边界的update依赖于其他区域的边界。

rinto 发表于 2016-10-12 10:30
这个题并行应该比较简单，不同的thread处理不同的区域，它们只share读上一个generation的数，不会发生冲 ...

谢谢回复

就是说并行和分布都需要读取其他相邻thread的数据，比如说应该有n个thread同时运行， 但最后thread2 ~ thread n 都需要用前一个thread的结果 是这样吗？

blactangeri 发表于 2016-10-13 20:56
谢谢回复

就是说并行和分布都需要读取其他相邻thread的数据，比如说应该有n个thread同时运行， 但最后 ...

"thread2 ~ thread n 都需要用前一个thread的结果"我不知道你的前一个指的是哪个，应该是它们都会用到相邻的结果，你从矩阵的角度来看，比如thread i分到矩阵的一小块，那么它算它那个小块边边的时候是不是要看一下边边相邻又在它这块之外的那些元素呢。如果在同一个机子上并行，它读起来没有问题，因为都在内存里（另外它只是读前一轮的结果，这一轮并不是覆盖掉前一轮数据，所以不用担心冲突），如果分到了不同的机子，它就需要communicate才能得到那些元素。

我的意思是thread i”相邻“的thread要具体地根据小块在矩阵里的位置算一下。不过如果只是并行，直接读好了，不用管之前谁写的

多谢lz分享！

TonyLic 发表于 2016-9-18 05:52
随便选一个点，DFS，如果是连通的，翻转每条路径，再次从这个点DFS，如果还是连通的，那原来整个图是连通 ...

这个解法不是n^2吗..最多n^2 edges..

5. 求undirected map是否连通 是不是问的是是否连通, 不是连通的数量, 跟lc上的一样?就是连通的 return true;
else return false;