Snowflake | 店面 hard

匿名用户 发表于 2024-6-4 07:05
这好像就是LFU那题的变体，直接加一个double linked list， node field 一个是freq，一个是set，按freq大小 ...

确实是LFU的变种，之前没做过，可惜了。

匿名用户 发表于 2024-6-4 13:05
这好像就是LFU那题的变体，直接加一个double linked list， node field 一个是freq，一个是set，按freq大小 ...

对这个才是正解

LFU/double linked list, 100% 是错的,比如你现在要+1 (add key) , 你就要把该元素往前挪(假设前面是Freq大的元素),你前面的元素可能是跟你+1以前的F相等,你就要继续往前找这是个线性的过程o(n).

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

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

匿名用户 发表于 2024-06-04 09:33:33
LFU/double linked list, 100% 是错的,比如你现在要+1 (add key) , 你就要把该元素往前挪(假设前面是Freq大的元素),

一个node里存的是所有这个freq的key的set

做过类似的, 两个HashMap:
可以做到O(1) 的时间复杂度, 空间复杂度略高, 因为 不同的freq 的 stack里会重复保存 一个key
key -> freq
freq -> stack<key>

min freq 咋做到 O(1)? pointer min_freq 变成0后就没法track next min_freq了

补充内容 (2024-06-05 12:20 +08:00):

LFU + double linked list 应该可以 好复杂

snowflake要求运行吗

谢谢分享 祝lz一切顺利！

这不就离口 丝散耳么