一亩三分地论坛

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

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

1109 Google 电面 全职

[复制链接] |试试Instant~ |关注本帖
saklyn 发表于 2016-11-10 09:00:23 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 本科 全职@Google - Other - 技术电面 |Otherfresh grad应届毕业生

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

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

x
发面经攒人品!!!!GG我现在是一路黑到底了!!!去年被烙印黑了一次,今年被放了一次鸽子,今年又被烙印黑!!!!电话迟到十分钟打来,提前十分钟结束,总共四十分钟。面试官全程一句话都不说,贴了题目,问我你明白我们要找什么了,我说明白了,然后就没有任何声音了。

今天的店面,只有一道题目:给一个矩阵,找一条从第一行到最后一行的和最大的路径。可以从第一行任意位置开始,但是只能向下往相邻的位置走。可以在最后一行任意位置结束。. from: 1point3acres.com/bbs
比如:
3   5  9 -1
-4  -3  0  3
7   0 -8  5
最大的和是9+3+5,找到最大和之后然后要打印出路径。

找到最大和用dp,打印出路径用dfs。我dfs卡了一阵,快写完被提前挂了电话,明明只差三行了,大概自己刷题的水平还没到写dp和dfs行云流水吧。



补充内容 (2016-11-10 09:01):
请大家多给点大米!!!
被GG伤得太厉害,需要大米!!.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (2016-11-10 09:21):
相邻表示,向左下,向下,向右下


补充内容 (2016-11-11 00:43):
HR电话里跟我说挂了,二十四小时之内给feedback还是挺快。我说面试官全程任何feedback都没给我,hr说她收到的feedback就是这样,认为我还不够。

评分

6

查看全部评分

类与对象tju 发表于 2016-11-11 08:05:56 | 显示全部楼层
这个找路径用dp也行吧,一维数组记录最大值,2维数组记录当前行到下一行的index位置

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

prodigalr 发表于 2016-11-10 09:10:03 | 显示全部楼层
没看懂,3,5,9不是在都在第一行吗,为什么是和最大的路径

补充内容 (2016-11-10 09:12):
懂了,忽略我~
回复 支持 反对

使用道具 举报

xhlzyllx 发表于 2016-11-10 09:15:04 | 显示全部楼层
烙印这么过分吗
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-11-10 09:16:57 | 显示全部楼层
相邻的意思是向左向右都可以吗还是说只能向右。。。。向左向右都可以感觉DP很难写啊
回复 支持 反对

使用道具 举报

 楼主| saklyn 发表于 2016-11-10 09:18:18 | 显示全部楼层
prodigalr 发表于 2016-11-10 09:16
相邻的意思是向左向右都可以吗还是说只能向右。。。。向左向右都可以感觉DP很难写啊

三种情况,左右下
回复 支持 反对

使用道具 举报

 楼主| saklyn 发表于 2016-11-10 09:19:45 | 显示全部楼层
xhlzyllx 发表于 2016-11-10 09:15.1point3acres缃
烙印这么过分吗

是,我全程都在说,听不见对方一句话,还被提前挂掉电话,我还没解释完。.1point3acres缃
去年GG面实习的那个烙印稍微好点。
回复 支持 反对

使用道具 举报

 楼主| saklyn 发表于 2016-11-10 09:21:09 | 显示全部楼层
相邻表示,向左下,向下,向右下
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-11-10 09:22:31 | 显示全部楼层
求问楼主怎么做的。如果是三个方向,不是就变成dp[j] = max(dp[j-1], dp[j+1], dp[i-1][j]) + matrix[j],这个感觉会死循环啊。求指导!

补充内容 (2016-11-10 09:23):
忽略我,看了楼主更新的定义了~
回复 支持 反对

使用道具 举报

tjcd 发表于 2016-11-10 10:45:23 | 显示全部楼层
这是CV里面一道经典的DP题 reference: "Seam Carving for Content-Aware Image Resizing"
回复 支持 反对

使用道具 举报

mulberry 发表于 2016-11-10 10:49:58 | 显示全部楼层
LZ已经不错了,我估计当场都不一定写的出来。
回复 支持 反对

使用道具 举报

 楼主| saklyn 发表于 2016-11-10 10:50:41 | 显示全部楼层
tjcd 发表于 2016-11-10 10:45
这是CV里面一道经典的DP题 reference: "Seam Carving for Content-Aware Image Resizing"

难怪觉得似曾相识,但是我曾经图像处理的课整个是逃过去的。。
回复 支持 反对

使用道具 举报

sunnyroom 发表于 2016-11-26 04:39:46 | 显示全部楼层
类与对象tju 发表于 2016-11-11 08:05
这个找路径用dp也行吧,一维数组记录最大值,2维数组记录当前行到下一行的index位置

用两个一维数组做记录。
从最后一行开始,往上计算每行每个位置到最后一行的最大值。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 13:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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