一亩三分地论坛

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

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

Google onsite 5轮 面经 2016年3月

[复制链接] |试试Instant~ |关注本帖
ivyac 发表于 2016-4-18 07:32:51 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
一共五轮

1. 寻找最长递增数列,init是找长度,follow up是打印出序列,follow follow up是打印出所有可能序列,follow follow follow up 是变成字符串找最长递增。
2. K最常用url链接,出现无数次。
3. 两个可循环buffer相互拷贝,key point大约是解决index收尾相接。follow up是怎么地高效率,减少拷贝次数。
4. 设计一个迷宫游戏,怎么走出迷宫,BFS解决。
5. tree版本的2sum,找出一个定值,数据结构变成tree,follow up是 3sum, n sum.

题都做出来的,就是2轮印度大叔看我实在不爽,无论如何也无法取悦,就跪在他的面前了。找个地方哭一会,睡了。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
tigercode 发表于 2016-9-11 02:58:21 | 显示全部楼层
1. 1-d dp; followup, 同时存个parent[i],最后可以backtracking; follow followup 题意不是很清楚,但应该是dfs; 字符串和数列有什么本质区别么?
回复 支持 1 反对 0

使用道具 举报

mingzhou1987 发表于 2016-4-18 08:33:41 | 显示全部楼层
碰到三哥面试官只能祈福了。第五题的tree是bst么?
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-4-18 08:35:55 | 显示全部楼层
楼主能不能简要说说第三题呢,不是很懂,谢谢了
回复 支持 反对

使用道具 举报

 楼主| ivyac 发表于 2016-4-18 09:07:08 | 显示全部楼层
mingzhou1987 发表于 2016-4-18 08:33
碰到三哥面试官只能祈福了。第五题的tree是bst么?

就是LC上2sum 3sum什么的 数据结构换成BST. 面经上有。
回复 支持 反对

使用道具 举报

 楼主| ivyac 发表于 2016-4-18 09:11:23 | 显示全部楼层
mingzhou1987 发表于 2016-4-18 08:35
楼主能不能简要说说第三题呢,不是很懂,谢谢了

两个循环buffer都长为10。从buffer1的第8位置开始拷贝到buffer2第9位,拷贝5个字节。怎么handle index,就是超出的部分要overwirte前面的。怎么减少拷贝次数,就是到达buffer的尽头再整体拷贝一串,而不是one by one.
回复 支持 反对

使用道具 举报

x1957 发表于 2016-4-18 13:08:46 | 显示全部楼层
2. K最常用url链接,出现无数次。
这个怎么做的啊?
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-22 06:18:04 | 显示全部楼层
同想问下K个最常用链接是怎么做?谢谢
回复 支持 反对

使用道具 举报

Effiel 发表于 2016-4-25 08:48:26 | 显示全部楼层
jy_121 发表于 2016-4-22 06:18
同想问下K个最常用链接是怎么做?谢谢

这是一个系统设计题,应该先问输入大小, 不同URL的个数。然后开始设计
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-4-25 12:36:32 | 显示全部楼层
Effiel 发表于 2016-4-25 08:48.鏈枃鍘熷垱鑷1point3acres璁哄潧
这是一个系统设计题,应该先问输入大小, 不同URL的个数。然后开始设计
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
好的,谢谢了。
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-4-29 05:50:04 | 显示全部楼层
请问能详细一点吗?什么是tree 的2sum 如果能给个example 就最好了
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-4-29 17:10:26 | 显示全部楼层
tree版的2sum, 是要求O(1)空间吗?
回复 支持 反对

使用道具 举报

m1h1r0 发表于 2016-5-1 00:14:56 | 显示全部楼层
2. K最常用url链接,出现无数次。
请问原题是什么?我没有看到过,有链接吗?谢谢!
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:19:32 | 显示全部楼层
对于第二题,是不是可以和HR argue呢?然后加面?
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:20:45 | 显示全部楼层
请问第二题,如果有url出现无数次,那还怎么计算top k呢
比如多于k的url出现无数次,那究竟谁是k里的
不是特别明白题意
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 01:22:06 | 显示全部楼层
CrossTheWall 发表于 2016-4-29 17:10
tree版的2sum, 是要求O(1)空间吗?

恐怕很难O(1)吧. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

你想move 前后pointer的话,recursion不好做
如果是iterative inorder traversal,那至少O(lgn)
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-5-1 03:49:49 | 显示全部楼层
tcomein2009 发表于 2016-5-1 01:22
恐怕很难O(1)吧. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

你想move 前后pointer的话,recursion不好做
. Waral 鍗氬鏈夋洿澶氭枃绔,
tree 是BST吗? 不然我觉得要至少要遍历整棵树呀
回复 支持 反对

使用道具 举报

tcomein2009 发表于 2016-5-1 07:28:53 | 显示全部楼层
陈润鹏 发表于 2016-5-1 03:49
tree 是BST吗? 不然我觉得要至少要遍历整棵树呀

对  楼主说是
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-2 17:03:19 | 显示全部楼层
tcomein2009 发表于 2016-5-1 01:22
恐怕很难O(1)吧

你想move 前后pointer的话,recursion不好做

可以O(1)的, 做一个tree Iterator来建立线索树, Iterator前进有两种方式,一种按中序, 一种按反中序,不过面试中让写这个难度确实不小。
回复 支持 反对

使用道具 举报

tigercode 发表于 2016-9-11 03:00:51 | 显示全部楼层
2. Map<String, Integer> 和minHeap with size k,heap node存(count, url)
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 10:04

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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