一亩三分地论坛

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

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

dropbox第一面跪(?)经

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

2016(10-12月) 码农类 博士 全职@Dropbox - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
dropbox第一面。

dropbox本身题库很小,所以我大胆的猜了次题:不是log-hit就是文件查重。
-google 1point3acres
结果我猜错了。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


问到的问题在面经版里出现且仅出现过一次:
http://www.1point3acres.com/bbs/thread-177627-1-1.html

题目描述很不一样,不过基本问题是一样的。

基本思路的话就是用dp去做:开一个2维dp,dp[j]记录(之前所有到达第(i,j)个点的路径中的最小值)里的最大值。. 鍥磋鎴戜滑@1point 3 acres

状态转移公式的话就是(假设input数组叫height, 大小为m*n)

dp[j] = min(max(dp[j-1], dp[i-1][j-1], dp[i+1][j-1]), height[j]).

然后看dp[n], i=0...m-1中的最大值即可。. visit 1point3acres.com for more.

之后拓展是如果height矩阵太大怎么办。可以一行一行的读,或者每次只读要更新的位置对应的dp值(比如要更新(i,j)只要读(i-1,j-1),(i,j-1),(i+1,j-1)这几个地方的dp和height[j])就行。

楼主一开始做错了,max写成了min,改了20多分钟才改明白。。。做完基本问题都过了45分钟了。。。还是水平太弱- -。不求过了,发个面经攒人品。
.1point3acres缃


评分

1

查看全部评分

 楼主| yxyxyx 发表于 2016-10-18 03:46:10 | 显示全部楼层
修改一下dp那部分的解释,原来的帖子里的[ i ] 被排版掉了:

基本思路的话就是用dp去做:开一个2维dp,dp[ i ][ j ]记录之前所有(到达第(i,j)个点的路径中的最小值)里的最大值。
. more info on 1point3acres.com
状态转移公式的话就是(假设input数组叫height, 大小为m*n)

dp[ i ][ j ] = min(max(dp[ i ][ j-1 ], dp[ i-1 ][ j-1 ], dp[ i+1 ][ j-1 ]), height[ i ][j]).

然后看dp[ i ][n], i=0...m-1中的最大值即可。
回复 支持 1 反对 0

使用道具 举报

tzthink 发表于 2016-10-22 13:07:57 | 显示全部楼层
楼主能不能把问题描述一下,谢谢,链接里要积分150以上才能看到
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-10-22 13:14:41 | 显示全部楼层
同求,积分不够。。。
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-23 09:52:43 | 显示全部楼层
yxyxyx 发表于 2016-10-18 03:46
修改一下dp那部分的解释,原来的帖子里的[ i ] 被排版掉了:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
基本思路的话就是用dp去做:开一个2维dp,d ...

给lz加米了,lz能给出dp解法已经很厉害了。不过对于follow up,不应该是是一列一列地读,然后一列一列更新吗?(从上到下)

补充内容 (2016-10-23 09:54):
也就是一个DP竖条向右滚动维护当列结果
回复 支持 反对

使用道具 举报

shiloh00 发表于 2016-10-23 09:57:32 | 显示全部楼层
LZ收到dropbox的信儿了么
回复 支持 反对

使用道具 举报

 楼主| yxyxyx 发表于 2016-10-23 23:41:34 | 显示全部楼层
1peter 发表于 2016-10-22 21:52
给lz加米了,lz能给出dp解法已经很厉害了。不过对于follow up,不应该是是一列一列地读,然后一列一列更 ...

恩一般来说应该是说每次只读一列然后去做,如果一列一列读还是太占内存的话就一个一个小矩形的读。。。意会一下。。。
回复 支持 反对

使用道具 举报

 楼主| yxyxyx 发表于 2016-10-23 23:42:04 | 显示全部楼层
shiloh00 发表于 2016-10-22 21:57 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ收到dropbox的信儿了么

并没有。根据dropbox过了面试发邮件很快的尿性,目测已跪
回复 支持 反对

使用道具 举报

1peter 发表于 2016-10-23 23:51:08 | 显示全部楼层
yxyxyx 发表于 2016-10-23 23:41
恩一般来说应该是说每次只读一列然后去做,如果一列一列读还是太占内存的话就一个一个小矩形的读。。。意 ...

能够意会,只是矩形边界处理的代码就会复杂一点吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 09:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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