當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1835|回复: 8
收起左侧

Dropbox 电面

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

2017(10-12月) 码农类General 博士 全职@Dropbox - 网上海投 - 技术电面  | Pass | fresh 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。. 围观我们@1point 3 acres
// 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.
// 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..1point3acres网
// 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])

. visit 1point3acres for more.
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 发表于 2017-12-8 11:38:09 | 显示全部楼层
ReminderHan 发表于 2017-12-7 08:27
LZ什么时候去on site呀~

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

stapollozxy 发表于 2017-12-5 12:09:14 | 显示全部楼层
onsite加油!

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

可是看到楼主的讨论, 最后能work的解决方案 仍然还是每次读第一列,转置成一行, 然后一行行的做啊... 这样的话 读写指针跳转消耗的问题,并没有被解决啊.... 求指点!

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了吧

不可以的~第一列有7个值,第二列处理完是5个值,第三列就只能确定3个值了

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

ReminderHan 发表于 2017-12-7 08:27:49 | 显示全部楼层
LZ什么时候去on site呀~
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

mitchellhe 发表于 2018-2-28 09:33:58 | 显示全部楼层
楼主现在怎么样了,拿offer了吗?OA做的是啥呀?是不是只有new grad才做OA呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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