一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1996|回复: 24
收起左侧

snapchat 电面

[复制链接] |试试Instant~ |关注本帖
yezhangpost 发表于 2016-10-5 23:59:44 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
昨天Snapchat 电面15 分钟的project 介绍,问道有哪些challenge 解决了。数据存在哪里,怎么保证同步。怎么保证系统的availability。
做题:  M 个数中取 N 个最大的数。类似maxheap。. 鍥磋鎴戜滑@1point 3 acres
solution: (1) brute force,sort 或者 maxheap,时间复杂度 M * logM,没写代码
                 (2) 优化solution,生成长度为N的minheap,loop 数组,one by one 的和heap 中的peek 比较。时间复杂度 M * logN。写了代码,写了几个test case,一次都run过了。.鐣欏璁哄潧-涓浜-涓夊垎鍦
                  (3)问能不能再次优化,复杂度 N * logM.
                                我回答了两种方法,但是都不能满足N * logM
                                             (1) quick sort, 复杂度 worse case: O(M * N) 或者  O((M- N) * M)   best case : O(M)
                                              ( 2 )  divide conquer and merge sort, M 个 数分成两个部分,两个部分再继续分。。。。recursive 直到  这部分只包含N 或者 小于 N个数,sort  N 或者 小于 N个数, return sorted 的                                                       N 或者 小于 N个数。两部分merge sort 前 N 个 最大数,再return 前 N 个 最大数。 。。。merge and return。 最后得到前N 个最大的数。
                                                      复杂度 M * logN + (M / N)* N, 感觉还不如minheap好。

                                 面试官让写了第二个code,写完了,没有时间run 了。面试官说明白了我的意思感觉大体是对的。我回来看了看代码,发现几个小的writting bug,其他是对的。
然后,简单的让我问了几个为题就bye了。

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

randomusername 发表于 2016-10-6 02:58:33 | 显示全部楼层
M选N问题:N*logN是可以的。。。 准备一个prioirtyQueue, 把maxHeap第一个塞进去,然后拿出来,再塞它的两个儿子,再拿最大那个出来,再把拿出来的两个儿子塞进去。。you got the idea? 我昨天snapchat onsite也被问到这题...
回复 支持 1 反对 0

使用道具 举报

小A要当码农 发表于 2016-10-6 03:30:36 | 显示全部楼层
yezhangpost 发表于 2016-10-6 03:21
首先先要heapify 吧,然后再用楼上的方法。复杂度是O(NlgN + M)

heapify的过程不就已经MlogN了么? 把M个数扔到一个容量为N的heap里?
回复 支持 1 反对 0

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 04:38:46 | 显示全部楼层
小A要当码农 发表于 2016-10-6 04:24
好的谢谢。那请问一下,这题为什么不用partition的方法做呢?

partition 的方法不就是quicksort吗,best case O(M),worse case O(M * N) 或者 O((M - N) * M)。我当时面试的时候说了,面试官觉得不满足要求, 一直强调O(NlgN)。可是现在分析我觉得最快也要 O(NlgN + M)。我也不知道面试官的心思。O(M) 和 O(NlogN)那个大呀?n << m 怎么能把O(m) 省略了。总之我觉得不可能和m无关,这样查1billion 和 查 10 个大小数组,取top3,难道复杂度一样了?这题我也是醉了。
回复 支持 1 反对 0

使用道具 举报

xiaoyehhuang23 发表于 2016-10-6 01:31:37 | 显示全部楼层
先heapify这M个,然后pop N次root,这样复杂度就是O(M+NlogM)。不知道是不是应该这样?
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-6 01:35:24 | 显示全部楼层
我现在没有能加给别人的米了。
我看到的楼主给出的最快的方法是min heap方法了。今天正在继续学习各种高级数据结构。
楼主是美国的星期一面的?
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 01:39:33 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-6 01:31
先heapify这M个,然后pop N次root,这样复杂度就是O(M+NlogM)。不知道是不是应该这样?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Heap M 个,也需要时间呀,复杂度是O(MlogM),不是O(M)
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 01:40:07 | 显示全部楼层
wcongying 发表于 2016-10-6 01:35
我现在没有能加给别人的米了。
我看到的楼主给出的最快的方法是min heap方法了。今天正在继续学习各种高级 ...
. From 1point 3acres bbs
我周二面的。
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-6 01:42:55 | 显示全部楼层

您给出的用例的时间复杂度没有错。
回复 支持 反对

使用道具 举报

xiaoyehhuang23 发表于 2016-10-6 02:10:22 | 显示全部楼层
yezhangpost 发表于 2016-10-6 01:39
Heap M 个,也需要时间呀,复杂度是O(MlogM),不是O(M)

heapify的复杂度可以是线性的,之前看到过证明,LZ可以上网查查
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-10-6 02:27:06 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-6 02:10
heapify的复杂度可以是线性的,之前看到过证明,LZ可以上网查查

那我更应该去好好看昨天看帖被作者强烈推荐的princeton algorithm了- -
回复 支持 反对

使用道具 举报

wxl3691 发表于 2016-10-6 02:44:11 | 显示全部楼层
这道题最自然的思路就是heap了,有类似的题目,或最优解吗??谁能说下
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-6 02:45:24 | 显示全部楼层
能不能用类似于Kth Largest Number的思路做? 其实就是一个partition
回复 支持 反对

使用道具 举报

ggwzjhgsq 发表于 2016-10-6 02:47:59 | 显示全部楼层
同感 partition一下找到第N大的数,然后扫一下比那个数大的就都是answer
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-6 02:51:35 | 显示全部楼层
ggwzjhgsq 发表于 2016-10-6 02:47
同感 partition一下找到第N大的数,然后扫一下比那个数大的就都是answer
. 1point 3acres 璁哄潧
但是复杂度并不是NlogM啊。。。感觉面试官是不是自己搞混了啊
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 03:21:28 | 显示全部楼层
randomusername 发表于 2016-10-6 02:58
M选N问题:N*logN是可以的。。。 准备一个prioirtyQueue, 把maxHeap第一个塞进去,然后拿出来,再塞它的两 ...

首先先要heapify 吧,然后再用楼上的方法。复杂度是O(NlgN + M)
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 03:42:50 | 显示全部楼层
小A要当码农 发表于 2016-10-6 03:30
heapify的过程不就已经MlogN了么? 把M个数扔到一个容量为N的heap里?

http://www.jiuzhang.com/solutions/heapify/  
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
O(M) 复杂度。现在为止我才明白这个题的意思。服了,电面出了这么诡异的题。move on
回复 支持 反对

使用道具 举报

 楼主| yezhangpost 发表于 2016-10-6 03:44:22 | 显示全部楼层
小A要当码农 发表于 2016-10-6 03:30-google 1point3acres
heapify的过程不就已经MlogN了么? 把M个数扔到一个容量为N的heap里?

不能直接用PriorityQueue,要自己写heapify。你在网上看看吧,heapify复杂度O(M)。
回复 支持 反对

使用道具 举报

penenda 发表于 2016-10-6 04:12:30 | 显示全部楼层
yezhangpost 发表于 2016-10-6 01:39
Heap M 个,也需要时间呀,复杂度是O(MlogM),不是O(M)
. from: 1point3acres.com/bbs
heapfy 复杂度线性时间 https://docs.python.org/2/library/heapq.html. Waral 鍗氬鏈夋洿澶氭枃绔,
heapq.heapify(x)
Transform list x into a heap, in-place, in linear time.
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-6 04:24:39 | 显示全部楼层
yezhangpost 发表于 2016-10-6 03:44. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
不能直接用PriorityQueue,要自己写heapify。你在网上看看吧,heapify复杂度O(M)。

好的谢谢。那请问一下,这题为什么不用partition的方法做呢?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 06:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表