Dropbox Intern OA 电面 两轮

OA: Frenemy
做之前看过面经。实际一开始dfs总是过不去（最后两个test cases超时）。最后用dp写过。

3/14 Phone Interview 1经典题duplicate file。这题没有要求run，只要边写边解释。大概解法：dfs找文件，根据size分类得到所有同size的文件。然后拿最开始的100byte做key，放进hashmap筛选，要是再

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

plexity在 (sizes.length)^n 级别，因为n可以非常大，所以很容易指数爆炸，但是一般来说pack sizes只有那么几种，所以她想让我写 n^(sizes.length) 级别的解法。我表示迷茫。如果没过就是这里followup跪了。

这题应该是lc里的combination sum 而不是 combination sum II 吧

写了个dp，但是加了个丑陋的去重，所以时间复杂度也不低

1. package dropbox;
   
2. 
   
3. 
   
4. import java.util.*;
   
5. 
   
6. public class Soda{
   
7. 
   
8.         public static void main(String[] args){
   
9.                 System.out.println(solve(new int[]{1,6,12}, 12));
   
10.         }
    
11. 
    
12.         private static List<List<Integer>> solve(int[] sizes, int total){
    
13.                 Map<Integer, List<List<Integer>>> hash = new HashMap<>();
    
14. 
    
15.                 for (int i = 0; i <= total; i++){
    
16.                         hash.put(i, new ArrayList<List<Integer>>());
    
17.                 }
    
18. 
    
19.                 for (int i = 1; i <= total; i++){
    
20.                         List<List<Integer>> container = hash.get(i);
    
21.                         for (int size : sizes){
    
22.                                 if (size <= i){
    
23.                                         if (hash.get(i - size).size() == 0){
    
24.                                                 List<Integer> temp = new ArrayList<>();
    
25.                                                 temp.add(size);
    
26.                                                 container.add(temp);
    
27.                                         }
    
28.                                         else{
    
29.                                                 for (List<Integer> list : hash.get(i - size)){
    
30.                                                         List<Integer> temp = new ArrayList<>();
    
31.                                                         temp.add(size);
    
32.                                                         temp.addAll(list);
    
33.                                                         if (!hasDup(container, temp)){
    
34.                                                                 container.add(temp);
    
35.                                                         }
    
36.                                                        
    
37.                                                         //System.out.println("i: " + i + " size: " + size);
    
38.                                                         //System.out.println("container: " + container);
    
39.                                                 }
    
40.                                         }
    
41.                                 }
    
42.                         }
    
43.                 }
    
44.                
    
45.                 //System.out.println(hash.get(total));
    
46.                
    
47.                 return hash.get(total);
    
48.         }
    
49.        
    
50.         private static boolean hasDup(List<List<Integer>> container, List<Integer> checker){
    
51.                 for (List<Integer> list : container){
    
52.                         if (list.containsAll(checker)) return true;
    
53.                 }
    
54.                
    
55.                 return false;
    
56.         }
    
57. }

复制代码

lz第二问的followup应该是用dp吧？像背包问题

fanzy 发表于 2016-3-21 06:48
lz第二问的followup应该是用dp吧？像背包问题

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

letsdoit666 发表于 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呢？

letsdoit666 发表于 2016-3-21 09:29
我觉得如果这题DFS做的话，时间复杂度应该是O(n!), 如果dp解的话，应该是O(n * size * k)，其中k为每个li ...

如果只需要结果总数，dp的优势才明显吧= =

fanzy 发表于 2016-3-21 09:49
k为每个list的长度，这里的list指的是什么呢？我写了一下代码，dp结构的初始化需要O(n*size*size)，关键 ...

大概是这个思路吧https://leetcode.com/discuss/23818/iterative-java-dp-solution？

dp, and then back track

letsdoit666 发表于 2016-3-21 09:59
大概是这个思路吧https://leetcode.com/discuss/23818/iterative-java-dp-solution？

是的，思路是这样，空间可以再优化

fanzy 发表于 2016-3-21 10:23
是的，思路是这样，空间可以再优化

空间还能怎么优化啊？

letsdoit666 发表于 2016-3-21 12:26
空间还能怎么优化啊？

我的idea是dp结构是二维数组n*size，每个entry存布尔值，dp结构算出来之后再backtracking算结果(bottom-up)。时间的话不知道相比你给的链接如何，虽然链接里的方法一步到位，但是算了很多没必要的entry，算单个entry的开销比我这个方法要大得多。