北京 airbnb 电面followup 挂

北京的airbnb
oa 2，就是按照一组数据按照host_id分页。
我实现的思路能做到最坏情况下，不会遍历整个数组。
电面follow up：
优化实现，

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

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

，我也挂了。
电话follow up挂很少见吧。但我不知道我的follow up这般难。。。。

#不知道怎么修改，就采用回帖的方式详细叙述下#
是电话follow up。题目是：full-stack coding challenge 2
就是一组排序的host_id，然后分页，每页尽量不要重复host_id，如无，从数组开头填充。

我的代码能处理最坏情况，即无需每次遍历，在不同host_id寻找完后就停止。

电话follow up:
解释题目思路：大概说了下题意，说了下思路。
问时间复杂度：O（N*N)(N是个数）。
提出del a[index]，list.pop(0)的时间复杂度，我说O(N），python中没有iterator remove，可以使用链表
让我优化：开始磕磕绊绊，思路混乱，嘴快说出了好几个地方，最后想到类似 k list merge的方式。每个host_id 后面跟着对应数组中的索引队列。
又是磕磕绊绊最后算出时间复杂度（面试官说不关心page number,m为host_id的种类数量）：N*m*lg(m)。
刚写出时间复杂度，面试官又说还可以继续优化吗？
我说：可能不需要每次都排序，可以用一个堆，然后拿出page_number个，再插入page_number个。
面试官说需要拿出page_number个再插入吗？我说：需要。
面试官说时间太久（已经40分钟了），就结束了。
然后从猎头哪儿知道挂了，说算法不行。

后来知道我是第二个follow up挂的，意思是一般人不会再follow up上挂，难道airbnb面试真这么难？但一亩三分地的面经没看出来啊。

zhaoqing 发表于 2018-7-31 19:31
#不知道怎么修改，就采用回帖的方式详细叙述下#
是电话follow up。题目是：full-stack coding challenge 2 ...

感觉类似利口二流，做完后记一个长度，然后分页，复杂度应该是O(N)

什么叫利口二流？这道题目地里有，但都是n*n的复杂度，貌似他们电面也都过了

zhaoqing 发表于 2018-8-1 01:25
什么叫利口二流？这道题目地里有，但都是n*n的复杂度，貌似他们电面也都过了

我找到了那道题，不知道我的理解对不对。
题意是有一组数据，每个数据有host_id，score等等，这组数据已经按照score排好序了。然后，题目要你对这组数据进行分页，尽可能让每一页出现的host_id的次数少。
其实这很像LC26那道题，就是把重复的数据放到后面。

为了简单起见，我把一组数据抽象成了一组数字，如果是数据类型，处理方法也是一样。

1. public class DisplayPages {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[] ids1 = {1,2,3,4,5,6,7,8,9};
   
5.                 int[] ids2 = {1,2,2,2,2,2,2,2,2};
   
6.                 int[] ids3 = {1,2,2,2,3,2,1,2,1};
   
7.                 int[] ids4 = {3,2,3,2,3,2,3,2,3};
   
8. 
   
9.                 DisplayPages dp = new DisplayPages();
   
10.                 printNestedList(dp.displayPages(ids1));
    
11.                 printNestedList(dp.displayPages(ids2));
    
12.                 printNestedList(dp.displayPages(ids3));
    
13.                 printNestedList(dp.displayPages(ids4));
    
14.         }
    
15. 
    
16.         public List<List<Integer>> displayPages(int[] ids) {
    
17.                 int size = 3;
    
18.                 List<List<Integer>> res = new ArrayList<>();
    
19.                
    
20.                 int end = 0, n = ids.length;
    
21.                 Set<Integer> map = new HashSet<>();
    
22.                 for (int i = 0; i < n; i++) {
    
23.                         if (map.isEmpty() || !map.contains(ids[i])) {
    
24.                                 map.add(ids[i]);
    
25.                                 swap(ids, end++, i);
    
26.                         }
    
27.                 }
    
28.                
    
29.                 List<Integer> page = new ArrayList<>();
    
30.                 for (int id : ids) {
    
31.                         page.add(id);
    
32.                         if (page.size() == size) {
    
33.                                 res.add(page);
    
34.                                 page = new ArrayList<>();
    
35.                         }
    
36.                 }
    
37.                
    
38.                 return res;
    
39.         }
    
40.        
    
41.         private void swap(int[] nums, int i, int j) {
    
42.                 int tmp = nums[i];
    
43.                 nums[i] = nums[j];
    
44.                 nums[j] = tmp;
    
45.         }
    
46.        
    
47.         private static void printNestedList(List<List<Integer>> lists) {
    
48.                 System.out.println("*------------------------------------------------------*");
    
49.                 for (List<Integer> list : lists) {
    
50.                         System.out.print("[ ");
    
51.                         for (Integer elem : list) {
    
52.                                 System.out.print(elem + ", ");
    
53.                         }
    
54.                         System.out.print(" ]");
    
55.                         System.out.println();
    
56.                 }
    
57.         }
    
58. }

复制代码

结果：
*------------------------------------------------------*
[ 1, 2, 3,  ]
[ 4, 5, 6,  ]
[ 7, 8, 9,  ]
*------------------------------------------------------*
[ 1, 2, 2,  ]
[ 2, 2, 2,  ]
[ 2, 2, 2,  ]
*------------------------------------------------------*
[ 1, 2, 3,  ]
[ 2, 2, 2,  ]
[ 1, 2, 1,  ]
*------------------------------------------------------*
[ 3, 2, 3,  ]
[ 2, 3, 2,  ]
[ 3, 2, 3,  ]

这样复杂度就是O(n)
欢迎拍砖

zhqfox 发表于 2018-8-3 06:44
我找到了那道题，不知道我的理解对不对。
题意是有一组数据，每个数据有host_id，score等等，这组数据已 ...

不太对，先找出所有不同的id，然后不足的话再从头挨个填充，里面不同id需要保持顺序

zhaoqing 发表于 2018-8-3 09:08
不太对，先找出所有不同的id，然后不足的话再从头挨个填充，里面不同id需要保持顺序

这个其实就是数组去重问题。一遍循环就能做完，还能保证顺序。你做一下LC26就知道了。

zhqfox 发表于 2018-8-4 00:33
这个其实就是数组去重问题。一遍循环就能做完，还能保证顺序。你做一下LC26就知道了。

但你要做 总和除以每页数量 这么多次