咕果MTV onsite

昨天MTV面完发一波新鲜面经。。面试官都简单粗暴，不问简历不闲聊，上来就做题。。。咕果的题果然都没见过而且还挺有意思。。。

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

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

补充内容 (2018-11-10 02:32):
失了智，第二轮的例子写错了。。反正就是一些paths，希望大家不要在意细节。。。

第一题可以先make assumption， 考虑到score是int类型
1. 如果score在一定范围比如0-100，可以用类似counting sort的思路，update和
query都是O(1)
2. 如果score很大，比如0-65535，可以考虑用segment tree, update和query都是O(logn)

穿袈裟的流氓 发表于 2018-11-12 09:43
楼主，你的第三轮是怎么从nlogn优化成n的，可以细讲一下吗

这题就是两步，先把所有card放到suit map里，再对map的每个entry找straight flush。
1. map的entry里如果存的是ordered set，插入是O(log n)，查找是O(log n)。每次从后往前找straight flush，找到了就break。整个下来复杂度就是O(n log n)。
2. 如果是unordered set，插入O(1)，查找O(1)。每次要遍历这个set里的所有value，对每个value(Let's say x)找x-1, x-2, x-3, x-4，没法break。复杂度是O(n)。

第三轮用union find set可解吧，根设为set里最大值

请问第一轮getK是不是需要返回多个名字，因为可能多个人分数一样

这道题类似 里口 散要务 的思路，update的实现麻烦一些，getKth()和update/insert 都是logn

补充内容 (2018-11-9 21:51):
第一题

把ordered_map替换为unordered_map改善复杂度的原因是因为把(NlogN)变成了(NlogK)，但是因为K是constant = 5所以就成了O(N)?

大木虫 发表于 2018/11/09 21:51:06
这道题类似 里口 散要务 的思路，update的实现麻烦一些，getKth()和update/insert 都是logn

补充内容 (2018-11-9 21:51):
第一题

应该就是一个带左子数数量的二叉查找数。成绩是key，学号反而是value

nhqgoal 发表于 2018-11-9 17:31
请问第一轮getK是不是需要返回多个名字，因为可能多个人分数一样

当时没跟面试官讨论这个。。。我觉得应该是返回任意一个吧

大木虫 发表于 2018-11-9 21:57
把ordered_map替换为unordered_map改善复杂度的原因是因为把(NlogN)变成了(NlogK)，但是因为K是constant =  ...

对的 紫薯紫薯

foryousee 发表于 2018-11-9 22:07
应该就是一个带左子数数量的二叉查找数。成绩是key，学号反而是value

我当时想的是类似的思路，存右子树的节点数，但是没有很想清楚。。。。