狗家2021暑期实习面经

dragonway 发表于 2020-12-09 07:01:03
一开始把第二题理解成要求获取与输入价格最相近报价的操作优化到O(1)，想了半天才反应过来这好像不可能，因为这涉及到sorting，而sorting是Ω(k)，对吧？

可以优化到logN，如果能把报价排好序的话

wubidi666 发表于 2020-12-9 22:27
第一题直接用PQ不就行了？为什么要二分查找？

PQ的问题就是不好更改。我做成字典加数组的形式，找位置插入和更新都是logk时间复杂度也没问题。而且后续如果有新的要求，也好更新，我是这么想的。

dragonway 发表于 2020-12-9 22:56
同意~另外第二题是不是直接用Map就可以了？为什么要套两层map？

我读题是一个产品 多个报价 报价形式是id,price 所以第一层dict我用产品idx 第二层我用id 方便快速删除

zach_chen 发表于 2020-12-10 06:23
k不是固定的，是top k函数的参数

K不是固定的？为什么我读出的意思是K固定。

xiana406 发表于 2020-12-09 19:37:47
K不是固定的？为什么我读出的意思是K固定。

因为我没写清楚，抱歉

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

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

foreveriii3 发表于 2020-12-10 20:02:08
能否再详细问一句这个时候map应该长什么样？如果就只是的话，插入删除没问题，但是插入之后各个index也是需要更新的吧？
如果不是的话，那么如何实现logN的查找？

哈希表里可以使用offer id做为索引，指向每个offer所在的链表节点

zach_chen 发表于 2020-12-11 15:34
哈希表里可以使用offer id做为索引，指向每个offer所在的链表节点

谢谢您的回复。
不过还是不是很明白如何在插入的时候进行logN的二分查找。
哈希表和链表（即使有序）都不能进行二分查找吧？

foreveriii3 发表于 2020-12-11 01:57:58
谢谢您的回复。
不过还是不是很明白如何在插入的时候进行logN的二分查找。
哈希表和链表（即使有序）都不能进行二分查找吧？

抱歉，是我大意了，普通链表确实不行，那我能想到的就只有skip list了，查找删除都是log N。