一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2069|回复: 14
收起左侧

Google Onsite 12/8/2015

[复制链接] |试试Instant~ |关注本帖
ztchf 发表于 2016-2-13 02:03:45 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
1. a) 给了个board,每个entry有一个颜色,给定一个entry和一种颜色A,把所有和该entry颜色相同的connected board涂上颜色A。follow up: DFS 和 BFS有什么优缺点,时间空间复杂度
    b) 给很多学生,纸笔,统计单词数。好像面经里出现过
2. 这轮崩了。。a)给一个正整数n,求能被n整除的且只由数字1组成的正整数的最小值,如果找不到返回0,否则返回这个数的长度
                         b )题大概是这样的,首先,一个二叉树,每条edge有weight(想象成graph),matching代表了一组两两没有公共节点的edges。现在让找一个matching,满足两个条件,一是cover所有节点,二是edge之和最小。没做出来,提示下讨论了一种recursion的做法(因为是二叉树,所以可以左右找,总共要返回四种情况,实在水平有限,只能讲到这了)。。.1point3acres缃
3. topological sort一堆有先后顺序要求的Task
4. a) 不改变顺序的情况下,把array里的0都移到最后,leetcode原题
    b)  计算二叉树两个节点的最短距离。先找LCA,再分别求高度。

最后祝大家好运吧!

评分

2

查看全部评分

guixi107 发表于 2016-2-13 02:32:40 | 显示全部楼层
lz, 第二轮可以给些例子吗?

谢谢
回复 支持 反对

使用道具 举报

 楼主| ztchf 发表于 2016-2-13 06:26:56 | 显示全部楼层
guixi107 发表于 2016-2-13 02:32
lz, 第二轮可以给些例子吗?
. 1point3acres.com/bbs
谢谢

你是说第二题吧。你去看一下图论里maching的概念应该就明白了。画图不大好画
回复 支持 反对

使用道具 举报

comicrudy 发表于 2016-2-13 12:49:16 | 显示全部楼层
第二轮好难,数学不好不行啊。。

补充内容 (2016-2-13 12:56):
recursion应该是max(W(左边) + (DP(右子树) + DP(左孩子的左右子树)),W(右边) + (DP(左子树) + DP(右孩子的左右子树)))这样吧?能问一下2-a)的思路么?
回复 支持 反对

使用道具 举报

bulbswitch 发表于 2016-2-13 13:30:04 | 显示全部楼层
楼主我们同一天onsite啊
回复 支持 反对

使用道具 举报

 楼主| ztchf 发表于 2016-2-13 13:57:59 | 显示全部楼层
comicrudy 发表于 2016-2-13 12:49. visit 1point3acres.com for more.
第二轮好难,数学不好不行啊。。

补充内容 (2016-2-13 12:56):

对,大概是这样的,code太难写,来不及写就结束了。第一题实在回忆不起来方法了,但是他问了很多overflow的问题,应该比较triky的解法吧,没想出来
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-7 00:03:47 | 显示全部楼层
请问“给很多学生,纸笔,统计单词数”具体是什么呢?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-7 00:05:31 | 显示全部楼层
"一个二叉树,每条edge有weight(想象成graph),matching代表了一组两两没有公共节点的edges。现在让找一个matching,满足两个条件,一是cover所有节点"这题是图上的最小set题?是个NP问题
回复 支持 反对

使用道具 举报

cx00001 发表于 2016-5-17 11:29:15 | 显示全部楼层
bobzhang2004 发表于 2016-3-7 00:05
"一个二叉树,每条edge有weight(想象成graph),matching代表了一组两两没有公共节点的edges。现在让找一 ...

现在是树,把问题简化了,感觉像dp题
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-24 07:56:44 | 显示全部楼层
lz我想问下 二×树不是一定有perfect matching的吧。。 如果是不是要先判断能不能找到这样一个matching
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-5-24 08:01:31 | 显示全部楼层
第二题应该能把所有(v, w)这样的edges取出来 然后backtracking,结束条件是所有点都遍历到然后更新最小值。。。应该也可以把树当成二部图来做 被问到这种真实血崩。。。
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-19 13:59:54 | 显示全部楼层
2,有点难度    2a是模拟手动除法,然后用set存余数么?看到循环则停
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-19 14:03:35 | 显示全部楼层
comicrudy 发表于 2016-2-13 12:49
第二轮好难,数学不好不行啊。。. 1point3acres.com/bbs

补充内容 (2016-2-13 12:56):

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴大体思想应该是这样, 但有些特殊的case要处理,比如下面这个, A-C必须取. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
   A
  /  \
B   C
/ \
D E
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-4 00:33:47 | 显示全部楼层
comicrudy 发表于 2016-2-13 12:49
第二轮好难,数学不好不行啊。。

补充内容 (2016-2-13 12:56):

他不是要EDGE之和最小么,那么你这个RECURISION应该是求MIN,不是MAX吧
回复 支持 反对

使用道具 举报

liurudahai 发表于 2016-10-4 00:36:09 | 显示全部楼层
tigercode 发表于 2016-9-19 13:59. From 1point 3acres bbs
2,有点难度    2a是模拟手动除法,然后用set存余数么?看到循环则停

1 11 111 1111 11111 111111这样循环除一个数一定能得到有余数循环么?我在想余数会不会没有规律,比如前面一直是1, 1, 2,2, 3,4,5,2,3,4,然后突然就到0了这种
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 22:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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