求问有什么站立式办公桌推荐?

一亩三分地论坛

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

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3597|回复: 9
收起左侧

dropbox第一面跪(?)经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
yxyxyx 发表于 2016-10-18 03:41:09 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】

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

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

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

x
dropbox第一面。

dropbox本身题库很小,所以我大胆的猜了次题:不是log-hit就是文件查重。

结果我猜错了。。。
. 1point3acres

问到的问题在面经版里出现且仅出现过一次:. 一亩-三分-地,独家发布
http://www.1point3acres.com/bbs/thread-177627-1-1.html
. visit 1point3acres for more.
题目描述很不一样,不过基本问题是一样的。-google 1point3acres

基本思路的话就是用dp去做:开一个2维dp,dp[j]记录(之前所有到达第(i,j)个点的路径中的最小值)里的最大值。
. From 1point 3acres bbs
状态转移公式的话就是(假设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中的最大值即可。

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

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



评分

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

查看全部评分


上一篇:dropbox面筋
下一篇:Oculus research店面
我的人缘0
 楼主| yxyxyx 发表于 2016-10-18 03:46:10 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
修改一下dp那部分的解释,原来的帖子里的[ i ] 被排版掉了: 来源一亩.三分地论坛.

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

状态转移公式的话就是(假设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中的最大值即可。
回复 支持 2 反对 0

使用道具 举报

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

使用道具 举报

我的人缘0
sniffsky 发表于 2016-10-22 13:14:41 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
同求,积分不够。。。
回复 支持 反对

使用道具 举报

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

基本思路的话就是用dp去做:开一个2维dp,d ...

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

补充内容 (2016-10-23 09:54):.1point3acres网
也就是一个DP竖条向右滚动维护当列结果

评分

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

查看全部评分

回复 支持 反对

使用道具 举报

我的人缘0
shiloh00 发表于 2016-10-23 09:57:32 | 显示全部楼层
  此人我要顶:
 
55% (4) 【我投】
  此人我要踩:
 
45% (5) 【我投】
LZ收到dropbox的信儿了么
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| yxyxyx 发表于 2016-10-23 23:42:04 | 显示全部楼层
  此人我要顶:
 
100% (1) 【我投】
  此人我要踩:
 
0% (0) 【我投】
shiloh00 发表于 2016-10-22 21:57
LZ收到dropbox的信儿了么

并没有。根据dropbox过了面试发邮件很快的尿性,目测已跪
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
1peter 发表于 2016-10-23 23:51:08 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
yxyxyx 发表于 2016-10-23 23:41
恩一般来说应该是说每次只读一列然后去做,如果一列一列读还是太占内存的话就一个一个小矩形的读。。。意 ...

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

使用道具 举报

我的人缘0
jjson 发表于 2018-2-22 10:15:33 | 显示全部楼层
  此人我要顶:
 
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...
来源一亩.三分地论坛. The running time is no different ... because you need mn cells processing any how...

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.
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-6-18 21:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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