一亩三分地论坛

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

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

Google/Youtube 9月8日 Onsite 面经

[复制链接] |试试Instant~ |关注本帖
agneshanlu 发表于 2015-9-10 02:48:27 | 显示全部楼层 |阅读模式

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

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

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

x
国人小哥shadow,白人geek主面。问题:将一个image mirror一下。image是用bit表示的。白人小哥不太理人。
国人小哥,不知道结果怎么样,不过感觉就在一直提醒我,给我感觉挺好的。问题是一个文件,一个set的word,让你找出出现次数最多的word。
白人lead,问题:总结一下就是, 有n个点,[0,1,2],输出序列为:[0,1,2,1,0,2,0] 满足: 0->1, 1->0, 0->2, 2->0, 1->2, 2->1, 求得最短输出序列。
午饭,国人小哥很好。一直跟我聊天。这轮不算在面试之中。
白人,感觉人很好。问题是: longest consecutive sequence in array。followup: longest consecutive sequence in tree,但是是简化版,只要求从parent 到root的longest sequence。
白人小哥。问了我一曾经onsite的时候面过的题目。就是一个matrix存value。两种操作,一种是query(x1,y1, x2, y2)返回此区间的value的和。 第二种是update(x, y, v),要求更新matrix的值。followup 分别是如果你想要query快,如果你想要update快。如果你想即让query快,又想要update快。怎么办?
感觉整体下来面试不难,但是我每一轮都没有bugfree,每当我说我想要过一个例子来看一下有没有bug,面试官都是觉得没时间了,然后就帮我指出来哪里可能有问题。这个也是我担心的一点。

找工作已经整整三个多月快四个月了。每次感觉快无望的时候,又来了面试,最近又开始了新的一轮招聘。大家一起加油!
Anyway,求人品求bless,求nextstep!

多谢地里的面经!

评分

3

查看全部评分

本帖被以下淘专辑推荐:

SDU_Phonism 发表于 2015-9-10 18:18:21 | 显示全部楼层
hbsophia 发表于 2015-9-10 16:15
lz, 这个序列的题目好难啊感觉,感觉之前没有遇到过呢。。。求lz能不能把解法再详细点?. from: 1point3acres.com/bbs

多谢多谢。 ...

这题我的想法是这样。。。

要求的这个序列,如果将两点之间看做一条单向边的话,其实这个序列就相当于将一个完全图遍历每个边,且每个边只遍历一次,就是一笔画问题。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
因为是完全图,一定存在解,然后直接dfs就行。。。然后观察一下dfs的解。很容易找到规律。所以最终是可以得到这题的构造解的。
回复 支持 3 反对 0

使用道具 举报

sishuxuan 发表于 2015-9-10 02:49:32 | 显示全部楼层
赞!祝楼主怒拿offer!
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-10 03:13:59 | 显示全部楼层
sishuxuan 发表于 2015-9-10 02:49
赞!祝楼主怒拿offer!

多谢多谢,也祝你一切顺利。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-9-10 03:41:56 | 显示全部楼层
blessed 楼主
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-10 03:54:01 | 显示全部楼层
LZ能细讲下这题吗? 有n个点,[0,1,2],输出序列为:[0,1,2,1,0,2,0] 满足: 0->1, 1->0, 0->2, 2->0, 1->2, 2->1, 求得最短输出序列。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-10 03:54:07 | 显示全部楼层
LZ能细讲下这题吗? 有n个点,[0,1,2],输出序列为:[0,1,2,1,0,2,0] 满足: 0->1, 1->0, 0->2, 2->0, 1->2, 2->1, 求得最短输出序列。
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-10 03:59:43 | 显示全部楼层
wenqiang88 发表于 2015-9-10 03:54.鏈枃鍘熷垱鑷1point3acres璁哄潧
LZ能细讲下这题吗? 有n个点,[0,1,2],输出序列为:[0,1,2,1,0,2,0] 满足: 0->1, 1->0, 0->2 ...

就是用backtracking来找一个序列,序列里面存在任何两两组合排序的序列。最后跟面试官讨论出来说用adjacency matrix 来表示a->b有没有得到过。
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-10 16:11:03 | 显示全部楼层
请问下lz, image mirror 是啥意思呀?多谢多谢!祝lz好运,早点拿到dream offer
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-10 16:15:09 | 显示全部楼层
agneshanlu 发表于 2015-9-10 03:59
就是用backtracking来找一个序列,序列里面存在任何两两组合排序的序列。最后跟面试官讨论出来说用adjace ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
lz, 这个序列的题目好难啊感觉,感觉之前没有遇到过呢。。。求lz能不能把解法再详细点?

多谢多谢。早日拿到dream offer
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-10 19:35:49 | 显示全部楼层
SDU_Phonism 发表于 2015-9-10 18:18
这题我的想法是这样。。。

要求的这个序列,如果将两点之间看做一条单向边的话,其实这个序列就相当于 ...

怎么证明完全图一定存在解?
回复 支持 反对

使用道具 举报

SDU_Phonism 发表于 2015-9-10 19:52:16 | 显示全部楼层
wenqiang88 发表于 2015-9-10 19:35
怎么证明完全图一定存在解?

因为是一笔画问题,且按照题意,是个有向完全图,所以每个点都是偶数个边,所以一定有解,证明就是七桥问题的证明方法。https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-10 20:08:04 | 显示全部楼层
SDU_Phonism 发表于 2015-9-10 19:52
因为是一笔画问题,且按照题意,是个有向完全图,所以每个点都是偶数个边,所以一定有解,证明就是七桥问 ...
. 鍥磋鎴戜滑@1point 3 acres
学习了,多谢!
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-11 00:21:49 | 显示全部楼层
hbsophia 发表于 2015-9-10 16:11
请问下lz, image mirror 是啥意思呀?多谢多谢!祝lz好运,早点拿到dream offer
-google 1point3acres
image mirror说白了就是将一个二维矩阵按照对称轴左右对称得到翻转的图形。这道题就是要注意因为矩阵里面每一个值都是由byte表示。但是我们用bit来表示一个像素点的话,需要同时把bit翻转。
例如:
[1,2,3]             [00000001,00000010,00000011]            [11000000, 01000000, 10000000]
[4,5,6]  ==》 [00000100,00000101,00000110]  ==》 [01100000, 10100000, 00100000]
[7,8,9]             [00000111,00001000,00001001]            [10010000, 00010000, 11100000]
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-11 00:22:10 | 显示全部楼层

多谢多谢多谢多谢!多谢!
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-11 00:22:48 | 显示全部楼层
hbsophia 发表于 2015-9-10 16:15
lz, 这个序列的题目好难啊感觉,感觉之前没有遇到过呢。。。求lz能不能把解法再详细点?

多谢多谢。 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
你可以看看10楼的回复。感觉很棒啊!
回复 支持 反对

使用道具 举报

hbsophia 发表于 2015-9-11 08:52:09 | 显示全部楼层
agneshanlu 发表于 2015-9-11 00:22
你可以看看10楼的回复。感觉很棒啊!

10 楼没有了呢,lz, 看不到了呢
回复 支持 反对

使用道具 举报

wenhanz 发表于 2015-9-11 10:19:34 | 显示全部楼层
agneshanlu 发表于 2015-9-11 00:22
你可以看看10楼的回复。感觉很棒啊!
. 鍥磋鎴戜滑@1point 3 acres
楼主!十楼被外星人抓走了! 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-11 10:58:21 | 显示全部楼层
hbsophia 发表于 2015-9-11 08:52
10 楼没有了呢,lz, 看不到了呢

在推荐里面。在上面。
回复 支持 反对

使用道具 举报

 楼主| agneshanlu 发表于 2015-9-11 10:59:51 | 显示全部楼层
wenhanz 发表于 2015-9-11 10:19
楼主!十楼被外星人抓走了!
. Waral 鍗氬鏈夋洿澶氭枃绔,
外星人就是派大星。我给点了个赞。在最上面呢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 21:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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