snapchat 电面

昨天Snapchat 电面15 分钟的project 介绍，问道有哪些challenge 解决了。数据存在哪里，怎么保证同步。怎么保证系统的availability。
做题：  M 个数中取 N 个最大的数。类似maxheap。
solution： （1） brute force，sort 或者 maxheap，时间复杂度 M * logM，没写代码
                 （2） 优化solution，生成长度为N的minheap，loop 数组，one by one 的和heap 中的peek 比较。时间复杂度 M * logN。写了代码，写了几个test case，一次都run过了。
                  （3

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

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

的writting bug，其他是对的。
然后，简单的让我问了几个为题就bye了。

今天早上收到拒信，虽然是意想之中的，但是还是心里不舒服。move on

哪位高人指点我一下，用什么方法能实现 N * lgM，我想了很久，也不知道。面试官后来也被M 和 N 搞晕了，还问我能不能有 N * lg N 的方法，无解。我觉得不可能和数组的长度无关。

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

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

yezhangpost 发表于 2016-10-6 03:21
首先先要heapify 吧，然后再用楼上的方法。复杂度是O(NlgN + M)

heapify的过程不就已经MlogN了么？ 把M个数扔到一个容量为N的heap里？

先heapify这M个，然后pop N次root，这样复杂度就是O(M+NlogM)。不知道是不是应该这样？

我现在没有能加给别人的米了。
我看到的楼主给出的最快的方法是min heap方法了。今天正在继续学习各种高级数据结构。
楼主是美国的星期一面的？

xiaoyehhuang23 发表于 2016-10-6 01:31
先heapify这M个，然后pop N次root，这样复杂度就是O(M+NlogM)。不知道是不是应该这样？

Heap M 个，也需要时间呀，复杂度是O(MlogM），不是O(M)

wcongying 发表于 2016-10-6 01:35
我现在没有能加给别人的米了。
我看到的楼主给出的最快的方法是min heap方法了。今天正在继续学习各种高级 ...

我周二面的。

yezhangpost 发表于 2016-10-6 01:40
我周二面的。

您给出的用例的时间复杂度没有错。

yezhangpost 发表于 2016-10-6 01:39
Heap M 个，也需要时间呀，复杂度是O(MlogM），不是O(M)

heapify的复杂度可以是线性的，之前看到过证明，LZ可以上网查查

xiaoyehhuang23 发表于 2016-10-6 02:10
heapify的复杂度可以是线性的，之前看到过证明，LZ可以上网查查

那我更应该去好好看昨天看帖被作者强烈推荐的princeton algorithm了- -

这道题最自然的思路就是heap了，有类似的题目，或最优解吗？？谁能说下

能不能用类似于Kth Largest Number的思路做？ 其实就是一个partition