San Jose各个房价 <1.5m 区域买房总结

一亩三分地论坛

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

Dropbox Intern OA 电面 两轮

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

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

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

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

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

3/14 Phone Interview 1经典题duplicate file。这题没有要求run,只要边写边解释。大概解法:dfs找文件,根据size分类得到所有同size的文件。然后拿最开始的100byte做key,放进hashmap筛选,要是再有duplicate就用100-200byte做key来继续筛选,以此类推直到读完,返回仍旧hash到同一个bucket的文件。. 1point 3acres 论坛
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] ]

基本上就是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跪了。

评分

3

查看全部评分

itgoujie2 发表于 2017-8-30 13:49:28 | 显示全部楼层
写了个dp,但是加了个丑陋的去重,所以时间复杂度也不低
  1. package dropbox;-google 1point3acres


  2. import java.util.*;

  3. public class Soda{
  4. . 1point 3acres 论坛
  5.         public static void main(String[] args){
  6.                 System.out.println(solve(new int[]{1,6,12}, 12));
  7.         }
  8. .1point3acres网
  9.         private static List<List<Integer>> solve(int[] sizes, int total){
  10.                 Map<Integer, List<List<Integer>>> hash = new HashMap<>();

  11.                 for (int i = 0; i <= total; i++){. 1point3acres
  12.                         hash.put(i, new ArrayList<List<Integer>>());
  13.                 }

  14.                 for (int i = 1; i <= total; i++){
  15.                         List<List<Integer>> container = hash.get(i);
  16.                         for (int size : sizes){
  17.                                 if (size <= i){
  18.                                         if (hash.get(i - size).size() == 0){
  19.                                                 List<Integer> temp = new ArrayList<>();.1point3acres网
  20.                                                 temp.add(size);
  21.                                                 container.add(temp);
  22.                                         }
  23.                                         else{
  24.                                                 for (List<Integer> list : hash.get(i - size)){
  25.                                                         List<Integer> temp = new ArrayList<>();. 1point3acres
  26.                                                         temp.add(size);. from: 1point3acres
  27.                                                         temp.addAll(list);
  28.                                                         if (!hasDup(container, temp)){
  29.                                                                 container.add(temp);
  30.                                                         }
  31.                                                        
  32.                                                         //System.out.println("i: " + i + " size: " + size);
  33.                                                         //System.out.println("container: " + container);
  34.                                                 }. 牛人云集,一亩三分地
  35.                                         }. Waral 博客有更多文章,
  36.                                 }. 留学申请论坛-一亩三分地
  37.                         }
  38.                 }. more info on 1point3acres
  39.                
  40.                 //System.out.println(hash.get(total));
  41.                
  42.                 return hash.get(total);. from: 1point3acres
  43.         }
  44.        
  45.         private static boolean hasDup(List<List<Integer>> container, List<Integer> checker){. more info on 1point3acres
  46.                 for (List<Integer> list : container){
  47.                         if (list.containsAll(checker)) return true;
  48.                 }
  49.                
  50.                 return false;
    . from: 1point3acres
  51.         }
  52. }
复制代码
回复 支持 1 反对 0

使用道具 举报

seasean 发表于 2017-11-27 09:21:12 | 显示全部楼层
这题应该是lc里的combination sum 而不是 combination sum II 吧
回复 支持 1 反对 0

使用道具 举报

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吧?像背包问题
. From 1point 3acres bbs
我觉得如果这题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?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

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的开销比我这个方法要大得多。
回复 支持 反对

使用道具 举报

hank1106 发表于 2017-12-16 15:47:06 | 显示全部楼层
seasean 发表于 2017-11-27 09:21
这题应该是lc里的combination sum 而不是 combination sum II 吧
.留学论坛-一亩-三分地
对吧。combination sum 是可以用多次
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-26 08:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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