Google NYC onsite 感受分享

工作一年之后第二次面G，waive了电面，onsite五轮，都是coding1. Move zero + House robber 第一题完全是warmup 写第二题DP方程的时候出了点小错，面试官提醒改过来了，这应该是一点瑕疵


2. Game of Life + followup 如果board很大怎么办 （并行/分布式处理）
3. 一个family tree，给两个node，判断有没有血缘关系。这题事先设计数据结构，开始我考虑是parent指向child，然后稍微一比划不对，没让我多想面

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

说实话面G之前我也看了很多版里面的面筋，我的算非常简单的题了。自己总结了教训就是，如果题目不清楚是应该和面试官讨论，但一旦题目清楚你进入解题阶段，不仅code要bug free，分析也要尽量完美，别指望着面试官指正你。特别是像我遇到这样的简单题，要求肯定就更严了。

祝各位好运吧。

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

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

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

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

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

跟楼主的详尽过程点个赞！

谢谢分享。好经验。

> 问题就是有时候面试官提示了一些，没能独立分析出问题。.

有时候，面试更依靠运气和机会。上面的理由有点牵强。我想，即使你全部独立做出来，他们还会给其它理由的。


补充内容 (2016-9-13 09:23):
楼主，有更好的offer等着你！

greentrail 发表于 2016-9-13 09:22
> 问题就是有时候面试官提示了一些，没能独立分析出问题。.

有时候，面试更依靠运气和机会。上面的理由 ...

嗯，运气也是很重要
除非大牛实力碾压，大部分人还是努力+运气啦

directed map怎么判断连通 求On解法

楼主你运气好好，基本都是leetcode

william_gong 发表于 2016-9-16 16:58
directed map怎么判断连通 求On解法

可以用unionfind然后find用压缩路径

pushazhiniao 发表于 2016-9-11 11:47
跟楼主的详尽过程点个赞！

楼主看你的帖子，还有这个帖子已经一些别的面筋。感觉方差好大啊难度，风格也不同

gaocan1992 发表于 2016-9-17 09:04
可以用unionfind然后find用压缩路径

union find 的复杂度是on吗？
这个我还真不知道。。。