推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1653|回复: 9
收起左侧

Dropbox Intern OA 电面 两轮

[复制链接] |试试Instant~ |关注本帖
Artifact 发表于 2016-3-21 05:36:19 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 实习@Dropbox - 网上海投 - 技术电面 在线笔试 |Other其他

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

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

x
OA: Frenemy
做之前看过面经。实际一开始dfs总是过不去(最后两个test cases超时)。最后用dp写过。-google 1point3acres

3/14 Phone Interview 1经典题duplicate file。这题没有要求run,只要边写边解释。大概解法:dfs找文件,根据size分类得到所有同size的文件。然后拿最开始的100byte做key,放进hashmap筛选,要是再有duplicate就用100-200byte做key来继续筛选,以此类推直到读完,返回仍旧hash到同一个bucket的文件。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
3/18 Phone Interview 2
Buy soda

List<List<Integer>> buySoda(int[] sizes, int n);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
大概是说超市有不同pack的汽水,比如散装,6瓶装,12瓶装之类的。假设要买n瓶,返回所有的买法。
Sample input: sizes=[1,6,12], n=12
Sampel output: [ [1,1,...1], [1,1,1,1,1,1,6], [6,6], [12] ]
. visit 1point3acres.com for more.
基本上就是leetcode的combination sum II套了个实际的场景. 我先用dfs写了。Follow up问了complexity,然后问能不能加快,我加了一些pruning。然后问能不能polynomial time.... From 1point 3acres bbs
我理解的面试官的意思:dfs的解法worst case相当于一个depth=n的tree的一部分,那么complexity在 (sizes.length)^n 级别,因为n可以非常大,所以很容易指数爆炸,但是一般来说pack sizes只有那么几种,所以她想让我写 n^(sizes.length) 级别的解法。我表示迷茫。如果没过就是这里followup跪了。

评分

2

查看全部评分

fanzy 发表于 2016-3-21 06:48:05 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
lz第二问的followup应该是用dp吧?像背包问题
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-21 09:29:28 | 显示全部楼层
关注一亩三分地微博:
Warald
fanzy 发表于 2016-3-21 06:48
lz第二问的followup应该是用dp吧?像背包问题

我觉得如果这题DFS做的话,时间复杂度应该是O(n!), 如果dp解的话,应该是O(n * size * k),其中k为每个list的长度,不懂为何这个是polynomial time。
回复 支持 反对

使用道具 举报

fanzy 发表于 2016-3-21 09:49:34 | 显示全部楼层
gjxwin 发表于 2016-3-21 09:29
我觉得如果这题DFS做的话,时间复杂度应该是O(n!), 如果dp解的话,应该是O(n * size * k),其中k为每个li ...

k为每个list的长度,这里的list指的是什么呢?我写了一下代码,dp结构的初始化需要O(n*size*size),关键是后面的那个结果的计算,复杂度是O(结果总数)。复杂度起码会是结果总数吧,如果结果总数是O(size^n)的话,怎么能做到polynomial呢?
回复 支持 反对

使用道具 举报

fanzy 发表于 2016-3-21 09:50:45 | 显示全部楼层
gjxwin 发表于 2016-3-21 09:29
我觉得如果这题DFS做的话,时间复杂度应该是O(n!), 如果dp解的话,应该是O(n * size * k),其中k为每个li ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果只需要结果总数,dp的优势才明显吧= =
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-21 09:59:49 | 显示全部楼层
fanzy 发表于 2016-3-21 09:49
k为每个list的长度,这里的list指的是什么呢?我写了一下代码,dp结构的初始化需要O(n*size*size),关键 ...

大概是这个思路吧https://leetcode.com/discuss/23818/iterative-java-dp-solution?
回复 支持 反对

使用道具 举报

ok123 发表于 2016-3-21 10:01:56 | 显示全部楼层
dp, and then back track
回复 支持 反对

使用道具 举报

fanzy 发表于 2016-3-21 10:23:49 | 显示全部楼层
gjxwin 发表于 2016-3-21 09:59
大概是这个思路吧https://leetcode.com/discuss/23818/iterative-java-dp-solution?

是的,思路是这样,空间可以再优化
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-21 12:26:56 | 显示全部楼层
fanzy 发表于 2016-3-21 10:23
是的,思路是这样,空间可以再优化

空间还能怎么优化啊?
回复 支持 反对

使用道具 举报

fanzy 发表于 2016-3-21 21:46:46 | 显示全部楼层
gjxwin 发表于 2016-3-21 12:26 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
空间还能怎么优化啊?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我的idea是dp结构是二维数组n*size,每个entry存布尔值,dp结构算出来之后再backtracking算结果(bottom-up)。时间的话不知道相比你给的链接如何,虽然链接里的方法一步到位,但是算了很多没必要的entry,算单个entry的开销比我这个方法要大得多。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-29 01:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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