一亩三分地论坛

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

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

Google8.6 热滚滚的面经

[复制链接] |试试Instant~ |关注本帖
lyj87372517 发表于 2015-8-7 05:31:21 | 显示全部楼层 |阅读模式

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

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

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

x
今天下午4:15面的,估计是个白人大哥,人挺耐心但自己水平太差被虐的体无完肤。。。. 1point 3acres 璁哄潧
问一个二维数组表示的n*n的矩阵,找出一条连续的最长的路径的长度。
比如
7 8 6
9 4 5
2 3 1
最长是2,3,4,5,6,返回长度5.
想到是DP但初始状态不知道怎么确定,以为和lc的 Minimum Path Sum 很像,结果他说不一定从(0, 0)开始就崩溃了。。。写了个暴力算法,让优化,估计GG了。。

评分

5

查看全部评分

M_Jason 发表于 2015-8-16 07:25:28 | 显示全部楼层
对,这题楼上的童鞋们已经提到了,用记忆化搜索能够很快的解决,需要用到dfs和HashMap。
回复 支持 0 反对 1

使用道具 举报

Linzertorte 发表于 2015-8-7 05:53:52 | 显示全部楼层
这又来滑雪了。
回复 支持 反对

使用道具 举报

eval 发表于 2015-8-7 06:00:53 | 显示全部楼层
poj 1088 滑雪 经典题啊
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-8-7 08:48:44 | 显示全部楼层
eval 发表于 2015-8-7 06:00
poj 1088 滑雪 经典题啊
. 1point 3acres 璁哄潧
哪里有这道题的解法呢?谢谢
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-7 09:24:41 | 显示全部楼层
blessed, and good luck
回复 支持 反对

使用道具 举报

yemingliang 发表于 2015-8-7 09:35:14 | 显示全部楼层
这道题是lintcode里面的Longest Increasing Continues Subsequences II, 解法主要就是DP+Recursion. 本来想把我以前写的代码贴出来,发现lint code现在好像和leetcod一样也是会员制了,果然天下没有免费午餐了。以后都不知道去哪儿刷题了,蛋疼!!!
回复 支持 反对

使用道具 举报

diefunction 发表于 2015-8-7 10:40:56 | 显示全部楼层
yemingliang 发表于 2015-8-7 09:35
这道题是lintcode里面的Longest Increasing Continues Subsequences II, 解法主要就是DP+Recursion. 本来想 ...

怎么会员制了。。。我的完全没变啊。。难道是因为之前都刷过了?
回复 支持 反对

使用道具 举报

mmliu 发表于 2015-8-7 14:02:17 | 显示全部楼层
yemingliang 发表于 2015-8-7 09:35. 1point3acres.com/bbs
这道题是lintcode里面的Longest Increasing Continues Subsequences II, 解法主要就是DP+Recursion. 本来想 ...
.1point3acres缃
我这边儿的也没有变,lintcode只是推出了一个laddder是需要邀请码的,其他都随意刷吧
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-8-7 21:18:30 | 显示全部楼层
woshiee123 发表于 2015-8-7 08:48
哪里有这道题的解法呢?谢谢

google下POJ 1088就有了。
回复 支持 反对

使用道具 举报

yemingliang 发表于 2015-8-7 23:43:23 | 显示全部楼层
可能是昨天他服务器出问题,刚发现好像又能刷了!多谢楼主提醒
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-8 02:21:01 | 显示全部楼层
楼主已经毕业了嘛?
回复 支持 反对

使用道具 举报

linlinying 发表于 2015-8-8 16:41:42 | 显示全部楼层
我觉得这题跟滑雪不太一样,这个要求的是连续路径,可以根据DP继续优化。这样的话根据矩阵里面每个点的值和它的坐标建一个hashmap。比如(0, 0)是7,且只有一个7,那么使得7为key,value为一个list,里面只有一个element就是1。
然后从数值最小的开始,此图中是1,然后找到1对应的list of coordinates,接下来再往下找2对应的list,如果中间有点和parent point只隔1,那么证明有路径过去,可以继续进行dfs,直到它的周围没有点可以比此点恰好大1.然后backtrace的时候标记child都遍历过了的点为visited以及从此点开始最长的长度,以后再碰到这个点的时候直接加上这个点至终点的长度。有个全局变量记录所有点得到过的最长路径,最后返回即可
最坏情况下路径经过每个点,这样复杂度是O(n^2).另外它还排除了周围没有比它恰好小1的点(这块儿的时间复杂度我也不知道怎么描述了),另外可以进行剪枝。如果max value - current value < current max 就没有必要再继续往大了搜了。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-8 21:00:58 | 显示全部楼层
嗯,记忆化搜索。就是POJ滑雪那题。
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-8-9 00:38:26 | 显示全部楼层
我半年前电面也是这题,我是简单的dfs, follow up 提速就加个hashmap
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-16 05:17:44 | 显示全部楼层
确实和滑雪有一丝丝差别。
需要把四周核查从
if(oriMatrix[i][j] > oriMatrix[i][j-1]) (四边之一).1point3acres缃
变为.鏈枃鍘熷垱鑷1point3acres璁哄潧
if(oriMatrix[i][j] == 1 + oriMatrix[i][j-1])

这样才是连续的。 滑雪是可以断开的,只要有落差就行。
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-16 07:18:23 | 显示全部楼层
woshiee123 发表于 2015-8-6 19:48. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
哪里有这道题的解法呢?谢谢

google 一下 “poj 1088“ 不就有了
http://www.cppblog.com/abilitytao/archive/2009/02/19/74271.aspx. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
http://my.oschina.net/Alexanderzhou/blog/203111
连豆瓣上都有: http://www.douban.com/note/209925117/
回复 支持 反对

使用道具 举报

say543 发表于 2015-8-17 08:10:00 | 显示全部楼层
弱弱的问一下请问DFS 怎么用hashMap 加速? 如果2维array没有重复的element 用一个2维来mark visited 因该就可以了? 有用hashMap的必要吗?
回复 支持 反对

使用道具 举报

handsomecool 发表于 2015-8-17 14:22:12 | 显示全部楼层
say543 发表于 2015-8-17 08:10
弱弱的问一下请问DFS 怎么用hashMap 加速? 如果2维array没有重复的element 用一个2维来mark visited 因该就 ...

过了好久,我也记得不是很清楚了。
用楼主发的例子吧,当时给我的好像也是这个例子:
7  8  6
9  4  5
2  3  1
我好像就只找递增的序列,比如当我找完前两排的时候,存在hashmap里面就是7->8, 8->8, 6->6, 9->9, 4->6,5->6等。 这时我找第三排的2然后找到3再找到4,发现4已经在map里了,就可以直接得出终点在6,从而在map里存入3->6, 2->6。同时每次存的时候我也记录一下max distance。存了2->6还要存3->6是为了保证每个数字只visit一遍。其实不用hashmap, 直接用个新的2d array存每个数字的终点也可以。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
至于你说的只存一个visited的bool, 我猜你是同时搜从当前位置的递增和递减序列然后加起来长度对吧? 感觉没啥问题还更省空间呢!厉害!
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-27 13:46:24 | 显示全部楼层
alucardzhou 发表于 2015-8-16 07:18
google 一下 “poj 1088“ 不就有了
http://www.cppblog.com/abilitytao/archive/2009/02/19/74271.aspx ...

豆瓣这个解法有没有问题啊?这个递归似乎没有初始值啊?第一个值代进去什么时候停止?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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