抖音电面

抖音电面，两道题

游客，本帖隐藏的内容需要积分高于 150 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

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

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

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

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

感谢楼主分享。关于第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。

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

夏虫何以语冰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