求教一道狗家的面试题

qc_james 发表于 2018-11-20 11:13
不好使，我第一个想到就是这个，结果发现时间复杂度是O(N)，被人啪啪打脸

146 的时间复杂度是O(1)..你是说放到这道题上变O(n)了嘛？

您好！
本帖隐藏的内容需要积分高于 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

qc_james 发表于 2018-11-20 13:20
可以啊，但是重点在于人家还叫你写一个size()，如果按你的思路就是O(N)，如果用BST和min heap就是O(logN) ...

个人觉得这道题做不到O(1)，可能是我水平不够吧。。不过google会用各种理由拒人。。不一定是题做的不好。。

size怎么样都做不到O(1)吧 对于当前时间 假设有k个已经过期了 你要访问这k个 肯定至少需要O(k)的时间。。感觉用那个LRU没问题啊 如果用BST 或者 minHeap 感觉复杂度是 log(n-1)(n-2).....(n-k+1) > klog(n-k+1) 啊 而不是logK啊
我不知道我想的对不对啊！ 求指教

fqbrighter 发表于 2018-11-20 23:25
size怎么样都做不到O(1)吧 对于当前时间 假设有k个已经过期了 你要访问这k个 肯定至少需要O(k)的时间。。感 ...

我觉得时间复杂度只考虑当前时间下单个call的就好了。我想过所有的数据结构，最好的也只是logN...没准有巧妙解法

louiseruiwenli 发表于 2018-11-20 13:23
个人觉得这道题做不到O(1)，可能是我水平不够吧。。不过google会用各种理由拒人。。不一定是题做的不好。 ...

谷歌的面试官大部分都是一脸嫌弃，不想和你合作...面了一天真的很不爽...所以面试他们家除了有实力之外还要有很好的心理素质...

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

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

circular array 了解一下