snap 一题 过经 疑惑求解法

虚拟现场，两轮coding，两轮design，有一轮跪了，没做完。后面再分享其他design round 的体验。
问一下地里大神，这题该咋做。
[

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

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

是好像interviewer 不是很满意。最后15分钟按照我的思路写，最后一点点没有debug 完，就结束了。

https://leetcode.com/problems/sort-array-by-increasing-frequency/

如果要 O(n) 的话，bucket sort 的想法是对的。这题需要在 sorted by frequency 的基础上保证插入顺序，一个取巧的做法是用 LinkedHashMap，get 的 time complexity 是 O(1)，同时保证元素插入顺序。这样在建 bucket 的时候就可以保证相同 frequency 的元素是按看到的顺序插入的。

和楼主想的一样，freq_dict + freq_bucket，还多加了个order_list, 来记录出现的位置，开的空间比较多。
这个例子可以过，但是不知道其他的地方是不是有corner case没想道。

1. def frequent_sort(input):
   
2.     val_2_cnt = defaultdict(int)
   
3.     cnt_2_vals = defaultdict(list)
   
4.     order_list = []
   
5.     max_cnt = 0
   
6.     for v in input:
   
7.         if v not in val_2_cnt:
   
8.             order_list.append(v)
   
9.         val_2_cnt[v] += 1
   
10.         max_cnt = max(max_cnt, val_2_cnt[v])
    
11. 
    
12.     for v in order_list:
    
13.         cnt = val_2_cnt[v]
    
14.         cnt_2_vals[cnt] += [v] * cnt
    
15.         
    
16.     res = []
    
17.     for i in range(max_cnt, 0, -1):
    
18.         if i in cnt_2_vals:
    
19.             res += cnt_2_vals[i]
    
20. 
    
21. 
    
22.     return res

复制代码

我有个偷懒的办法,  python 的orderdict，非常简单明了 ，但是极大可能这个不是面试官想要的解法
另一个正常的办法是记录出现的先后顺序的list，加上一个dict （和你的想法一样）

应该是刷题网451

不让sort，我能想到的只有maxheap，但这个复杂度也是O(nlogn)，代码还更复杂

+1 感觉bucket sort
hashmap记录次数, 建一个最大次数的二维数组, 遍历原数组, 按照次数写入到新数组, 再倒序遍历新数组, 3*O(N)的感觉

原题 maximum frequencu stack

就用LinkedHashMap代替一般map，然后bucket sort 就行了

就是LFU嘛，代码比较难写就是了。amortized O(N)，worst O(NlgN)因为hashmap可能会有key collision。