一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 331|回复: 7
收起左侧

Dropbox 电面

[复制链接] |试试Instant~ |关注本帖
kdzhang 发表于 2017-12-5 11:44:21 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 博士 全职@Dropbox - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
今天刚收到了onsite通知,把上周五电面的经历写一下,回馈地里~
地面的题目是老题 highest minimum sharpness,就是二维dp解决的。写的时候有一个小bug,bp[r-1][c-1]写成了bp[r-1][c],bp[r+1][c-1]写成了bp[r+1][c]。运行程序以后发现了这个bug,然后改过来了。然后面试小哥说可以优化空间,我说用一维dp保存前一列数据,没有要求实现code。
// Given a 2-d array of "sharpness" values. Find a path from the leftmost column to the rightmost column which has the highest minimum sharpness.. visit 1point3acres.com for more.
// Output the highest minimum sharpness. Each move can only move to the top right, right or bottom right grid.
// Example: 3*3 matrix
// 5 7 2
// 7 5 8
// 9 1 5. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
// The path with highest minimum sharpness is 7-->7-->8, because 7 is the highest minimum value in all the paths.. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
// Idea: Use DP dp[r][c] = min(max(dp[r-1][c-1], dp[r][c-1], dp[r+1][c-1]), grid[r][c])

.1point3acres缃
followup和之前的面经一样,问的是如果是100million * 100 million怎么办。因为看过面经,我先回答的是答案是把这个matrix翻转90度,然后一行行处理,但翻转的时候,读行输出列会有硬盘写文件耗时,读列输出行会有硬盘读文件耗时。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后又回答说可以读一个正方形,一个正方形一个正方形处理。小哥让把code写一下,我就写了一段pseudocode。
然后小哥给分析了下发现这样有问题。如果处理matrix中间5x5矩阵,已知第一列中的五个值X,第二列只能算出来中间三个值,第三列只能算出来中间一个值。最后说还是只能翻转90度再一行行的做。
X O O O O               X O O O O
X O O O O               X X O O O
X O O O O  --------> X X X O O
X O O O O               X X O O O
X O O O O               X O O O O



补充内容 (2017-12-5 11:47):
时间线:10月中下旬网上海投,11月22号收到做了OA (folders and cows),感恩节之后27号一大早收到了电面通知。Dropbox真是效率超高。感觉onsite没啥希望,就当去体验下三番第一餐厅了~

评分

2

查看全部评分

 楼主| kdzhang 发表于 6 天前 | 显示全部楼层
ReminderHan 发表于 2017-12-7 08:27
LZ什么时候去on site呀~

约了圣诞前的那一周,有一起去的小伙伴么

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stapollozxy 发表于 2017-12-5 12:09:14 | 显示全部楼层
onsite加油!
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-12-5 12:15:10 | 显示全部楼层
这道题之前看地里消息的时候 有人说 每次读一个正方形 能最大避免读写指针翻转, 我就觉得有这种5->3->1 的问题。。。。
. 1point 3acres 璁哄潧
可是看到楼主的讨论, 最后能work的解决方案 仍然还是每次读第一列,转置成一行, 然后一行行的做啊... 这样的话 读写指针跳转消耗的问题,并没有被解决啊.... 求指点!
.鏈枃鍘熷垱鑷1point3acres璁哄潧
PS 大米已加! 楼主加油!
回复 支持 反对

使用道具 举报

 楼主| kdzhang 发表于 2017-12-5 14:01:51 | 显示全部楼层
2011051305 发表于 2017-12-5 12:15
这道题之前看地里消息的时候 有人说 每次读一个正方形 能最大避免读写指针翻转, 我就觉得有这种5->3->1 的 ...

是没有办法解决,好像也没有别的办法了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sj1456 发表于 2017-12-6 05:37:51 | 显示全部楼层
只读5 * 5会有5->3->1的问题,那每次多读上下两行不就行了。。读进来7*5,只处理中间5行,就能5->5->5了吧
回复 支持 反对

使用道具 举报

 楼主| kdzhang 发表于 2017-12-6 06:06:11 | 显示全部楼层
sj1456 发表于 2017-12-6 05:37
只读5 * 5会有5->3->1的问题,那每次多读上下两行不就行了。。读进来7*5,只处理中间5行,就能5->5->5了吧
. visit 1point3acres.com for more.
不可以的~第一列有7个值,第二列处理完是5个值,第三列就只能确定3个值了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ReminderHan 发表于 7 天前 | 显示全部楼层
LZ什么时候去on site呀~
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-12-14 18:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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