Google onsite

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

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

第三题：把乱掉的数和其index保存起来，排序后再用index 去fix 原来的array。 time: O(N +klogk + k). N 是原数组长度，k是乱掉的数的个数。
复杂度没法低于O(n) 吧，因为总需要把原来的数组扫一遍，除非事先知道k的值。

求问第三题思路

jhdyss 发表于 2022-2-16 12:14
求问第三题思路

猜测是heap？

jhdyss 发表于 2022-2-15 23:14
求问第三题思路

第三题感觉可以把乱掉的数提出来单独排序。这样有一大一小两个sorted array，然后merge

两题system design是L6面吗？

楼主面的什么level？

是用heap吗？

第一个sd有什么思路吗？完全没见过