10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 1832|回复: 10
收起左侧

Dropbox Intern OA 电面 两轮

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

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

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

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

x
OA: Frenemy. Waral 鍗氬鏈夋洿澶氭枃绔,
做之前看过面经。实际一开始dfs总是过不去(最后两个test cases超时)。最后用dp写过。
.鏈枃鍘熷垱鑷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);.1point3acres缃
大概是说超市有不同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.... 鍥磋鎴戜滑@1point 3 acres
我理解的面试官的意思:dfs的解法worst case相当于一个depth=n的tree的一部分,那么complexity在 (sizes.length)^n 级别,因为n可以非常大,所以很容易指数爆炸,但是一般来说pack sizes只有那么几种,所以她想让我写 n^(sizes.length) 级别的解法。我表示迷茫。如果没过就是这里followup跪了。

评分

3

查看全部评分

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

使用道具 举报

gjxwin 发表于 2016-3-21 09:29:28 | 显示全部楼层
fanzy 发表于 2016-3-21 06:48. Waral 鍗氬鏈夋洿澶氭枃绔,
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 ...
. from: 1point3acres.com/bbs
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?
. From 1point 3acres bbs
是的,思路是这样,空间可以再优化
回复 支持 反对

使用道具 举报

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
空间还能怎么优化啊?
. more info on 1point3acres.com
我的idea是dp结构是二维数组n*size,每个entry存布尔值,dp结构算出来之后再backtracking算结果(bottom-up)。时间的话不知道相比你给的链接如何,虽然链接里的方法一步到位,但是算了很多没必要的entry,算单个entry的开销比我这个方法要大得多。
回复 支持 反对

使用道具 举报

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

  3. import java.util.*;

  4. public class Soda{

  5.         public static void main(String[] args){
  6.                 System.out.println(solve(new int[]{1,6,12}, 12));
  7.         }

  8.         private static List<List<Integer>> solve(int[] sizes, int total){
  9.                 Map<Integer, List<List<Integer>>> hash = new HashMap<>();
  10. . Waral 鍗氬鏈夋洿澶氭枃绔,
  11.                 for (int i = 0; i <= total; i++){
  12.                         hash.put(i, new ArrayList<List<Integer>>());
  13.                 }
    -google 1point3acres

  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){. from: 1point3acres.com/bbs
  18.                                         if (hash.get(i - size).size() == 0){
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  19.                                                 List<Integer> temp = new ArrayList<>();
  20.                                                 temp.add(size);. more info on 1point3acres.com
  21.                                                 container.add(temp);. 1point 3acres 璁哄潧
  22.                                         }
  23.                                         else{
  24.                                                 for (List<Integer> list : hash.get(i - size)){
  25.                                                         List<Integer> temp = new ArrayList<>();
  26.                                                         temp.add(size);
  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.                                         }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  36.                                 }
  37.                         }
  38.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  39.                
  40.                 //System.out.println(hash.get(total));
  41.                
  42.                 return hash.get(total);
  43.         }. From 1point 3acres bbs
  44.        
  45.         private static boolean hasDup(List<List<Integer>> container, List<Integer> checker){
  46.                 for (List<Integer> list : container){. 1point 3acres 璁哄潧
  47.                         if (list.containsAll(checker)) return true;
  48.                 }
  49.                
  50.                 return false;
  51.         }
  52. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-19 23:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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