Berkeley biostat应该是biostat里最非传统,最偏ml的超棒项目了!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 4013|回复: 11
收起左侧

dropbox第一面跪(?)经

[复制链接] |试试Instant~
我的人缘0
yxyxyx 发表于 2016-10-18 03:41:09 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩

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

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

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

x
dropbox第一面。

. Waral 博客有更多文章,dropbox本身题库很小,所以我大胆的猜了次题:不是log-hit就是文件查重。. 1point3acres

结果我猜错了。。。


问到的问题在面经版里出现且仅出现过一次:
http://www.1point3acres.com/bbs/thread-177627-1-1.html
. 围观我们@1point 3 acres
题目描述很不一样,不过基本问题是一样的。

基本思路的话就是用dp去做:开一个2维dp,dp[j]记录(之前所有到达第(i,j)个点的路径中的最小值)里的最大值。

状态转移公式的话就是(假设input数组叫height, 大小为m*n)
. from: 1point3acres
dp[j] = min(max(dp[j-1], dp[i-1][j-1], dp[i+1][j-1]), height[j]).. From 1point 3acres bbs

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

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

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



评分

参与人数 3大米 +17 收起 理由
farewell + 5 感谢!
frk + 2 谢谢你的介绍!
1peter + 10 回答的很好!

查看全部评分


上一篇:dropbox面筋
下一篇:Ziilow Data Analyst 求面经!!!
我的人缘0
 楼主| yxyxyx 发表于 2016-10-18 03:46:10 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
修改一下dp那部分的解释,原来的帖子里的[ i ] 被排版掉了:
. 围观我们@1point 3 acres
基本思路的话就是用dp去做:开一个2维dp,dp[ i ][ j ]记录之前所有(到达第(i,j)个点的路径中的最小值)里的最大值。
-google 1point3acres
状态转移公式的话就是(假设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]).. from: 1point3acres

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

使用道具 举报

我的人缘0
tzthink 发表于 2016-10-22 13:07:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
楼主能不能把问题描述一下,谢谢,链接里要积分150以上才能看到
回复

使用道具 举报

我的人缘0
sniffsky 发表于 2016-10-22 13:14:41 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (3)
 
 
0% (0)  踩
同求,积分不够。。。
回复

使用道具 举报

我的人缘0
1peter 发表于 2016-10-23 09:52:43 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
yxyxyx 发表于 2016-10-18 03:46
修改一下dp那部分的解释,原来的帖子里的[ i ] 被排版掉了:

基本思路的话就是用dp去做:开一个2维dp,d ...
. From 1point 3acres bbs
给lz加米了,lz能给出dp解法已经很厉害了。不过对于follow up,不应该是是一列一列地读,然后一列一列更新吗?(从上到下)-google 1point3acres
.本文原创自1point3acres论坛
补充内容 (2016-10-23 09:54):
也就是一个DP竖条向右滚动维护当列结果

评分

参与人数 1大米 +3 收起 理由
frk + 3 感谢分享!

查看全部评分

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘1
shiloh00 发表于 2016-10-23 09:57:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  70% (1030)
 
 
29% (432)  踩
LZ收到dropbox的信儿了么
回复

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-23 23:41:34 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
1peter 发表于 2016-10-22 21:52
给lz加米了,lz能给出dp解法已经很厉害了。不过对于follow up,不应该是是一列一列地读,然后一列一列更 ...

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

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-23 23:42:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (678)
 
 
2% (15)  踩
shiloh00 发表于 2016-10-22 21:57
LZ收到dropbox的信儿了么

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

使用道具 举报

我的人缘0
1peter 发表于 2016-10-23 23:51:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (41)
 
 
2% (1)  踩
yxyxyx 发表于 2016-10-23 23:41
恩一般来说应该是说每次只读一列然后去做,如果一列一列读还是太占内存的话就一个一个小矩形的读。。。意 ...
. 一亩-三分-地,独家发布
能够意会,只是矩形边界处理的代码就会复杂一点吧
回复

使用道具 举报

我的人缘0
jjson 发表于 2018-2-22 10:15:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (73)
 
 
0% (0)  踩
1peter 发表于 2016-10-23 09:52
给lz加米了,lz能给出dp解法已经很厉害了。不过对于follow up,不应该是是一列一列地读,然后一列一列更 ...

I think it should be reading 3 lines into memory ... each time you finish a round from left to right...
remove the first row, and read the next row to make up a new 3 lines again... and do left to right again...
. more info on 1point3acresThe running time is no different ... because you need mn cells processing any how.... From 1point 3acres bbs

But reading row by row can benefit from cache/less seek time while reading col by col... cannot ... because most matrix is storing row by row.
回复

使用道具 举报

我的人缘0
DetectiveConan 发表于 2018-9-13 05:42:53 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩
jjson 发表于 2018-2-22 10:15
I think it should be reading 3 lines into memory ... each time you finish a round from left to rig ...

I think this may be incorrect. For example, the optimal path is from left bottom to upper right.

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
zhizhiya 发表于 2018-9-13 06:54:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
看不到链接帖子里的问题。。有木有人发一下。。。
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

GMT+8, 2018-9-26 22:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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