巨硬 BingAds 组电面面经

看名字很清真的大叔 口音听不出来，上来就废话不多说直接做题。
题目是如何找到离用户最近的前

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

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

04:22):
更多信息请看二楼

我先说用最小堆，把所有店的distance都放到堆里，然后pop前k个，时间复杂度建堆O(n) + 找topk O(klgn)。面试官说n很大的时候不是很有效，有没有别的方法，我就想到了可以用类似快排的算法，每次只处理一半的数据，类似蠡口贰一伍。面试官说好那你写吧，写完之后问了问时间复杂度，聊了聊简历就结束了，说recruiter会联系你。

不知道巨硬的效率大概几天recruiter会回复呢？

楼主请问你有消息了么

建堆不应该是nlgn吗？ 题目有给定已经是dreasing order了吗？

K th nearest neighbor 对吧

weisooong 发表于 2018-3-7 03:38
楼主请问你有消息了么

还没有消息 准备明天问一下啥情况

Zetecx 发表于 2018-3-7 03:52
建堆不应该是nlgn吗？ 题目有给定已经是dreasing order了吗？

建堆O(n)的 这是分析 虽然看不太懂。。。 https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

duranneji 发表于 2018-3-7 15:28
建堆O(n)的 这是分析 虽然看不太懂。。。 https://stackoverflow.com/questions/9755721/how-can-buildin ...

谢谢！ 好像就是bottom-up ／ top-down建堆的方式 导致 时间复杂度不一

LZ如果用max heap 将heap的size控制在K 复杂度如何呢？