Meta店面意外挂筋

我最近电面也被问了 kth largest这道 我就是直接说了minHeap做法 然后快速写完 跑了例子 说了时间空间复杂度 面试官也没问有没有其他做法...还有一道是一个basic sliding window 这道题问了一个follow up口述一下就行 可能因为我做的比较快 面试官又问了一个第三道  easy的tag题 口述就行 隔天就收到过了

匿名用户 发表于 2023-11-01 20:54:35
第2点完全同意，LZ也可以多分享些过程让大家帮忙复盘~

本来我只是说了一种解法，面试官一直问有没有更好的，所以才加了另外两种，TA才满意。然后问TA希望我实现哪个，TA说选一个我能按时完成的就行，也没有叫我必须最优解。

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

这道题应该用quick selection法做。 关键点有两个： （1） 如何保证复杂度在O(n)? 随机取下标；（2）如何保证尽可能的均匀划分。需要会选pivot。

补充内容 (2023-11-02 18:18 +08:00):

补充：第二点记的有点模糊，查了一下应该用three-way partition

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

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

这题一般是考quick select，不知道你有没有给这种解法

lz，别想那么多了。
这种面试过不过都是个谜 。
有可能那天面试官和ta的另一半吵架了，心情不爽。

另外说一句，只要是在面试中希望面试者每次都给出最优解的人，都是神经病。

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

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

Minheap 做法不行的,得写出quickselect，minheap和sort一下难度没什么太大的区别。