[面试经验]讨论Nvidia coding题目

电面题目类似LRU Cache，但是capacity到达以后，会弹出最大值而不是最不常用的值。也要求O(1)的操作时间。这个题好像不能用hashtable+双链

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

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

ased sorting has a lower bound of O(nlogn)。

请问楼主面的是啥职位

补充内容 (2018-11-10 02:17):

还想问下他们家一定要用C或者C++来写算法题吗

感觉可以用treemap+单链表，map里面存链表中每个节点之前的节点

bearxiong2017 发表于 2018-11-10 02:14
请问楼主面的是啥职位

补充内容 (2018-11-10 02:17):

我面的是DL / ML相关position，具体叫啥我也不知道，所以用了python

sort-based确实不行，不过如果存的是整数的话，hash-based可以做到O(1)，方法是用radix trie

也就是把一个整数（这里假定32bit）的底层表示拆成4个byte，每个byte建一层trie节点。

注意到LeetCode题目常见的trie是每层最大26个节点对应26个小写字母，而这里说的radix trie每层最大为256个节点，对应一个byte所能表示的值域0 ~ 255。

常数因子非常高所以完全没有实用意义.. 但时间复杂度确实是O(1)就是

代码可以参考这个帖子里写的（题目是max stack，本质上与楼主的题目是一样的）：https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=298294&page=3#pid3285452

补充内容 (2018-11-13 10:59):
有个笔误.. 第一句话里应该是comparison-based而不是sort-based