一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 762|回复: 9
收起左侧

Dropbox Intern OA 电面 两轮

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

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

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

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

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

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);. From 1point 3acres bbs
大概是说超市有不同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] ]

基本上就是leetcode的combination sum II套了个实际的场景. 我先用dfs写了。Follow up问了complexity,然后问能不能加快,我加了一些pruning。然后问能不能polynomial time...
我理解的面试官的意思:dfs的解法worst case相当于一个depth=n的tree的一部分,那么complexity在 (sizes.length)^n 级别,因为n可以非常大,所以很容易指数爆炸,但是一般来说pack sizes只有那么几种,所以她想让我写 n^(sizes.length) 级别的解法。我表示迷茫。如果没过就是这里followup跪了。.1point3acres缃

评分

1

查看全部评分

fanzy 发表于 2016-3-21 06:48:05 | 显示全部楼层
lz第二问的followup应该是用dp吧?像背包问题
回复 支持 反对

使用道具 举报

gjxwin 发表于 2016-3-21 09:29:28 | 显示全部楼层
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 ...

如果只需要结果总数,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的开销比我这个方法要大得多。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 04:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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