楼主: TonyLic
跳转到指定楼层
上一主题 下一主题
收起左侧

Google NYC onsite 感受分享

🔗
bigoldcat 2016-10-11 07:57:45 | 只看该作者
全局:
楼主是做什么方向的?属于前端还是后端呢?
回复

使用道具 举报

🔗
rinto 2016-10-12 02:38:20 | 只看该作者
全局:
楼主,family tree那个题目,用dfs具体是怎么解得啊,先把一个node的所有ancestor找出来然后dfs另一个node的ancestor的一个个试看看有重复的么?还是有什么更好的方法呢?
我的想法是从两个node开始bfs分别bfs,分别存一个visited的hashset看什么时候有交集,这样visited的总node数比较小ancestor每往上走一层数目要多一倍

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

使用道具 举报

🔗
blactangeri 2016-10-12 09:47:00 | 只看该作者
全局:
lz请问可以具体说说这个题怎么并行处理吗 谢谢
2. Game of Life + followup 如果board很大怎么办 (并行/分布式处理)

评分

参与人数 1大米 +3 收起 理由
zsmj001 + 3 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

🔗
rinto 2016-10-12 10:30:46 | 只看该作者
全局:
blactangeri 发表于 2016-10-12 09:47
lz请问可以具体说说这个题怎么并行处理吗 谢谢
2. Game of Life + followup 如果board很大怎么办 (并行/ ...

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

使用道具 举报

🔗
blactangeri 2016-10-13 20:56:41 | 只看该作者
全局:
rinto 发表于 2016-10-12 10:30
这个题并行应该比较简单,不同的thread处理不同的区域,它们只share读上一个generation的数,不会发生冲 ...

谢谢回复

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

评分

参与人数 1大米 +3 收起 理由
zsmj001 + 3 欢迎来一亩三分地论坛!

查看全部评分

回复

使用道具 举报

🔗
rinto 2016-10-13 21:55:29 | 只看该作者
全局:
blactangeri 发表于 2016-10-13 20:56
谢谢回复

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

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

使用道具 举报

🔗
rinto 2016-10-13 21:57:16 | 只看该作者
全局:
我的意思是thread i”相邻“的thread要具体地根据小块在矩阵里的位置算一下。不过如果只是并行,直接读好了,不用管之前谁写的
回复

使用道具 举报

🔗
wstc2008 2016-10-13 22:50:29 | 只看该作者
全局:
多谢lz分享!
回复

使用道具 举报

🔗
leixiang5 2016-10-31 11:36:47 | 只看该作者
全局:
TonyLic 发表于 2016-9-18 05:52
随便选一个点,DFS,如果是连通的,翻转每条路径,再次从这个点DFS,如果还是连通的,那原来整个图是连通 ...

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

使用道具 举报

🔗
qiuxuxing007 2016-11-7 07:34:57 | 只看该作者
全局:
5. 求undirected map是否连通 是不是问的是是否连通, 不是连通的数量, 跟lc上的一样?就是连通的 return true;
else return false;
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表