抖音电面

抖音电面，两道题

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

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

但是这种方法复杂度很高，想了半天想不出来，最后面试官提示用PQ来解，当时没有想好该怎么处理duplicate了。
面完之后想了很久，应该是用一个map来记录每个数值的freq，先把所有的unique的num放入pq中，然后取出K个，更新map，如果map存的freq为0，则删除对应的数值。然后在把map中所有的keySet放入pq中，如果PQ取出不连续的数，则返回false

gongchen 发表于 2020-12-1 12:12
哈哈 楼主你原文说是subarray然后用PQ我都懵了

不过我用PQ和map倒是把怡二酒陆写出来了，速度>70%貌似还可以，和discussion的高票答案不是一个解法。

1. class Solution {
   
2.     public boolean isPossibleDivide(int[] nums, int k) {
   
3.         if(nums.length%k!=0) return false;
   
4.         
   
5.         PriorityQueue<Integer> pq = new PriorityQueue<>();
   
6.         Map<Integer, Integer> info = new HashMap<>();
   
7.         for(int num:nums) {
   
8.             info.put(num, info.getOrDefault(num, 0)+1);
   
9.         }
   
10.         
    
11.         pq.addAll(info.keySet());
    
12.         
    
13.         while(!pq.isEmpty()) {
    
14.             int prev = 0;
    
15.             List<Integer> list = new ArrayList<>();
    
16.             
    
17.             for(int i=0; i<k; i++) {
    
18.                 if(pq.isEmpty()) return false;
    
19.                 if(i==0) {
    
20.                     prev = pq.poll();
    
21.                     list.add(prev);
    
22.                     info.put(prev, info.get(prev)-1);
    
23.                     continue;
    
24.                 } else {
    
25.                     int tmp = pq.poll();
    
26.                     if(tmp-prev>1) return false;
    
27.                     info.put(tmp, info.get(tmp)-1);
    
28.                     prev = tmp;
    
29.                     list.add(tmp);
    
30.                 }
    
31.             }
    
32.             
    
33.             for(int num:list) {
    
34.                 if(info.get(num)>0) {
    
35.                     pq.offer(num);
    
36.                 }
    
37.             }
    
38.         }
    
39.         
    
40.         return true;
    
41.     }
    
42. }

复制代码

感谢楼主分享。关于第2题，能否再详细地说以下题意？
1. “分成多个size为K的subarray“怎么理解？
  加入n=array.length, 给的条件一定满足n%k==0吗？（也就是恰好分成a0[0]...a[k-1], a[k]...a[2*k-1], ..., a[n-k]...a[n-1]这一共n/k个部分？）
2. ”subarray中的int值是连续的“怎么定义？
  例如，n=6, k=3, array = [1, 2, 3, 3, 5, 4]。这里的[3, 5, 4]算不算int值连续的？

mchzh 发表于 2020-12-1 10:45
第二题是不是pq里面要存pair : val and idx ，两个都要排序，这题是不是还有扫描线的解法

LRU的multi thread实现可以加锁，或者使用thread safe的class都可以，网上应该有具体介绍

第二题pq我是只存num，map存num对应的freq。

谢谢楼主分享，请问面的是哪个组？

LRU的multi thread就是加锁吗？多谢

第二题是不是pq里面要存pair : val and idx ，两个都要排序，这题是不是还有扫描线的解法

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

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

夏虫何以语冰X 发表于 2020-12-1 11:14
LRU的multi thread实现可以加锁，或者使用thread safe的class都可以，网上应该有具体介绍

第二题pq我 ...

感觉map存freq会丢了index的位置信息

gongchen 发表于 2020-12-1 11:52
**** 本内容被作者隐藏 ****

哈哈是的就是这个题。

gongchen 发表于 2020-12-1 11:52
**** 本内容被作者隐藏 ****

那估计应该是subseqence，不是subarray