《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 2198|回复: 10
收起左侧

Dropbox Intern OA 电面 两轮

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

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

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

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

x
OA: Frenemy. 鍥磋鎴戜滑@1point 3 acres
做之前看过面经。实际一开始dfs总是过不去(最后两个test cases超时)。最后用dp写过。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

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);
. more info on 1point3acres.com大概是说超市有不同pack的汽水,比如散装,6瓶装,12瓶装之类的。假设要买n瓶,返回所有的买法。
Sample input: sizes=[1,6,12], n=12. from: 1point3acres.com/bbs
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.... more info on 1point3acres.com
我理解的面试官的意思: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
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的开销比我这个方法要大得多。
回复 支持 反对

使用道具 举报

itgoujie2 发表于 2017-8-30 13:49:28 | 显示全部楼层
写了个dp,但是加了个丑陋的去重,所以时间复杂度也不低. Waral 鍗氬鏈夋洿澶氭枃绔,
  1. package dropbox;
  2. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  3. import java.util.*;
  4. . visit 1point3acres.com for more.
  5. public class Soda{

  6.         public static void main(String[] args){
  7.                 System.out.println(solve(new int[]{1,6,12}, 12));. visit 1point3acres.com for more.
  8.         }

  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++){
  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<>();
  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<>();
  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.         }
  44.        
  45.         private static boolean hasDup(List<List<Integer>> container, List<Integer> checker){
  46.                 for (List<Integer> list : container){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  47.                         if (list.containsAll(checker)) return true;
  48.                 }
  49.                
  50.                 return false;
  51.         }
  52. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-19 20:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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