Facebook 电面2道题

昨天第一轮电面，刚开始聊10分钟开始做题。题不难，第一道立扣 溜漆，很顺利；第二题求点集合（x,y）到0点的最远距离，暴力很快写完了，让我improve时间复杂度，一直在往 binary search上想，想歪了。经提醒让我

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

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

>
用heap是为了求top k, 居然忘了说这点。。。是先求最远距离 然后求最远距离坐标 最后是求topk坐标 输出坐标list

edyyy 发表于 2017-6-10 07:56
第二题  用heap 是让你用priority_queue之类的吗？我怎么觉得复杂度还是n?

忘了提 他刚开始让我返回最大距离值 后来让我返回坐标 我就说用map 然后排序 针对map排序的优化是用heap

oldman09 发表于 2017-6-11 05:28
minHeap 里有compare function？楼主的意思是不是override priorityqueue用的comparactor？

就是把计算距离这步放到heap里做 就是heap.push(x, y)

forteller 发表于 2017-6-10 08:53
第二题能不能详细说说。谢谢。排序的？不排序的？不排序还能比O(N)低是怎么个意思？

不是sorted的 看前面我的回复

再followup 一轮店面嘛？

scredwood 发表于 2017-6-10 06:24
再followup 一轮店面嘛？

是的        

第二题  用heap 是让你用priority_queue之类的吗？我怎么觉得复杂度还是n?

第二题能不能详细说说。谢谢。排序的？不排序的？不排序还能比O(N)低是怎么个意思？

minHeap 里有compare function？楼主的意思是不是override priorityqueue用的comparactor？

觉得是comparator要自己吧

没理解用heap的好处在哪里

既然求集合中最远距离 为啥要heap啊 loop一遍不就好了吗

houqingniao 发表于 2017-6-11 07:50
既然求集合中最远距离 为啥要heap啊 loop一遍不就好了吗

面试官让提高时间复杂度