Snowflake | 店面 hard

店面体验不错，面试官很互动，但就是问题太难，如果之前没有写过，现场在面试写出来的概率非常低。

1. 题目描述：实现一个key和frequency的class。支持的API有
        add(key) 让一个key的frequency+1
        delete

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

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

2024-06-04 13:50 +08:00):

大家可以去看看LFU cache，确实是他的变种，确实也是hard :D

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

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

这不就离口 丝散耳么

最大可以做到o(1), 举个例子,A 是最大 Freq, A--不是最大了,你就要找Freq[A] +1是否存在,有则返回,没有就是A因为A还是最大的. 同様的如果A is最小,加1 可以找到最小.

但是减就不一样了,如果是减到0, 新的最小的 element 就要线性找. 所以最小Freq最坏情况好像不是o(1)而是o(n) 如果用无序的set

请问O(1) 的 key_with_max/min_frequency()怎么实现呢？ 我的想法是用除了一个key, frequency的map之外，维护一个链表，链表按frequency排序，每次+1或-1就把链表中元素和左右两边的比较，但是这个单个操作最坏情况可能是O(n)的，但是均摊下来应该还是O(1)的，感觉要是想严格证明的话有点难度

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

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

匿名用户 发表于 2024-06-03 16:43:58
维护两个map，一个是key to frec，另一个是frec to set of key。然后维护一个max frec，一个min frec。
add的话就通

层主正解！

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

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

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

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

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

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

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

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