一亩三分地论坛

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

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

snapchat onsite

[复制链接] |试试Instant~ |关注本帖
yuanmu 发表于 2015-11-6 23:39:59 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 内推 - Onsite |Passfresh grad应届毕业生

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

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

x
. 1point3acres.com/bbs
发面经回馈地里。楼主是10月末的onsite,面试体验还是很好地。面试地点就在沙滩旁边,每人一个小房间,在里面有准备好的interview survival小袋子,以及墙上的欢迎语。看到了感觉还是挺暖心的。楼主因为当时比较忙,只看了一部分地里的相关面经,如果下面有碰到之前的面经题目但是楼主没提出来,还请见谅。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主当天去的比较晚,到那里才发现第一轮的面试官已经在等我了,被领到房间里直接开始,电脑还临时抽风了耽误了十分钟,结果面试官在旁边安慰我说没事没事,电脑就是时不时会出问题 = =!面试官人很好嘛~~ 当天一共四轮,上午两轮下午两轮,每轮一个小时。感觉楼主运气比较好,碰到了三位国人,以及很多leetcode的题目。

第一轮. 1point3acres.com/bbs
1. find all amicable numbers
输入一个正整数,找出所有小于这个数的amicable pairs。讨论了一下时间空间复杂度以及如何tradeoff,最后写了时间复杂度O(nlogn),空间复杂度O(n)的算法。
2. leetcode原题 basic calculator II, 不需要考虑空格, 但是除法结果不限制是整数。
follow up:如果可以有括号怎么做(这个说一下思路就好,没要求我在电脑上写出来运行)

第二轮
1. 有点类似leetcode里面的 valid anagram, 直接可以用hashmap解决的那种。. 1point3acres.com/bbs
2. 基本是leetcode里面的 alien dictionary,不同的要求是如果排序结果不唯一,则直接报特殊错误(在原题基础上加一个if 判断就可以啦)。

第三轮
1. leetcode unique paths II
2. leetcode find median from data stream
(国人小哥这轮放水提前结束,让我可以多休息一下,感谢~)

第四轮
1. 输入是一串不断更新的数据流,要求输出是其中k个随机数据,每个出现过的数据被输出的概率相同。
楼主之前做过随机输出一个数据的类似题目,当时跟面试官交流的也不好,就直接照搬过来把一个随机输出复制了k遍,然后被告知输出数据不能重复。。。然后思路就卡住了,被提示后知道分两步走,第一步用随机函数得知每次一个新数据来了之后是否使用,第二步如果要使用该数据再用一个随机函数得知替换掉哪个原来存在的数据。
之后要求在电脑上自己写出来各种test case来检测函数的正确性. 1point3acres.com/bbs
2. leetcode word break II, 只需要输出一种结果就可以

感觉他们家的HR效率很高,当天面试完第二天上午就发邮件说出结果了,可以打电话聊聊。面试官人都很好,聊简历和问问题的环节也觉得挺开心的。有位面试官表示最近engineer team要扩招,正是面试的好时机。个人估计他们的bar现在应该比较低。

新人发帖,格式或者哪里有问题求指出,多多包涵~~




. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

评分

3

查看全部评分

本帖被以下淘专辑推荐:

kennethinsnow 发表于 2015-12-7 16:27:56 | 显示全部楼层
yuanmu 发表于 2015-11-23 03:30
没有那么复杂了。。我当时就输入的1-10,手动输入就好。。。
. visit 1point3acres.com for more.
请问你怎么验证概率相同?你test case测试的是什么?
回复 支持 1 反对 0

使用道具 举报

zneofrost 发表于 2015-11-9 02:43:55 | 显示全部楼层
想问一下amicable pair那一题,如何实现O(n lgn)的时间复杂度?
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-11 04:38:29 | 显示全部楼层
zneofrost 发表于 2015-11-9 02:43
想问一下amicable pair那一题,如何实现O(n lgn)的时间复杂度?

啊,不好意思,时间复杂度应该是O(n ^ 3/2). Find factor sum 是 根号n, 遍历一遍数字是n
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-11-16 14:42:59 | 显示全部楼层
楼主问下alien dictionary那题要怎么判断排序结果不唯一
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-16 22:04:29 | 显示全部楼层
ammmmy11 发表于 2015-11-16 14:42
楼主问下alien dictionary那题要怎么判断排序结果不唯一

如果在某一时刻有多个备选的字符可以作为下一个排序字符,那么结果就不唯一~
回复 支持 反对

使用道具 举报

sunxiangyu 发表于 2015-11-16 22:08:03 | 显示全部楼层
问一下楼主,onsite的时候,听说他们家是自己用电脑写test case?
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-16 22:10:18 | 显示全部楼层
sunxiangyu 发表于 2015-11-16 22:08-google 1point3acres
问一下楼主,onsite的时候,听说他们家是自己用电脑写test case?
. 1point3acres.com/bbs
恩,对的。自己带电脑,用ide写函数,然后自己来写test case证明你的函数没有问题..
回复 支持 反对

使用道具 举报

sunxiangyu 发表于 2015-11-16 22:15:58 | 显示全部楼层
yuanmu 发表于 2015-11-16 22:10
恩,对的。自己带电脑,用ide写函数,然后自己来写test case证明你的函数没有问题..

OK,谢谢楼主,下周面,希望能和楼主一样
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-11-17 02:07:55 | 显示全部楼层
yuanmu 发表于 2015-11-16 22:04
如果在某一时刻有多个备选的字符可以作为下一个排序字符,那么结果就不唯一~

哦哦懂了,楼主BFS做的
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-17 23:14:12 | 显示全部楼层
sunxiangyu 发表于 2015-11-16 22:15
OK,谢谢楼主,下周面,希望能和楼主一样

恩,加油!
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-18 10:57:21 | 显示全部楼层
楼主请问第四轮第一题输出随机数那题,所有数据输入之后都会被保存起来吗?还有你说的“替换”原来数据是什么意思呢?
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-18 11:34:59 | 显示全部楼层
silenceleaf 发表于 2015-11-18 10:57
楼主请问第四轮第一题输出随机数那题,所有数据输入之后都会被保存起来吗?还有你说的“替换”原来数据是什 ...
. visit 1point3acres.com for more.
为了优化空间,不保存所有的输入数据。如果结果要输出k个数据,那么空间就是k。在输入时先来看这个新数据要不要被保存,比如输入第m个数据的时候,就有 k/m 的概率保存它。如果要保存的话,原来应该有k个数据,再用一个随机函数来等概率的找出k个中的任意一个进行替换,把新数据插入到该位置上。这样来保证所有输入数据最后被输出的结果是一样的~
回复 支持 反对

使用道具 举报

reality 发表于 2015-11-19 05:33:03 | 显示全部楼层
楼主好厉害。。。每一轮都做两题。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-20 08:34:00 | 显示全部楼层
lz我听说他们onsite不是在白板上而是在电脑上写的是吗?
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-20 13:01:53 | 显示全部楼层
mooc 发表于 2015-11-20 08:34
lz我听说他们onsite不是在白板上而是在电脑上写的是吗?
. 1point 3acres 璁哄潧
恩,对的,电脑上写函数,然后写test case来检测
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 03:28:05 | 显示全部楼层
yuanmu 发表于 2015-11-18 11:34
为了优化空间,不保存所有的输入数据。如果结果要输出k个数据,那么空间就是k。在输入时先来看这个新数据 ...

请问你的test case怎么写的?输入10000个数,其中100个不同,统计每个数在结果中出现的频率?
回复 支持 反对

使用道具 举报

 楼主| yuanmu 发表于 2015-11-23 03:30:36 | 显示全部楼层
kennethinsnow 发表于 2015-11-23 03:28
请问你的test case怎么写的?输入10000个数,其中100个不同,统计每个数在结果中出现的频率?

没有那么复杂了。。我当时就输入的1-10,手动输入就好。。。
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-23 13:09:19 | 显示全部楼层
yuanmu 发表于 2015-11-18 11:34
为了优化空间,不保存所有的输入数据。如果结果要输出k个数据,那么空间就是k。在输入时先来看这个新数据 ...

不懂为什么第m个数据 有 k/m 的概率保存?楼主能解释一下吗?谢谢。
回复 支持 反对

使用道具 举报

no.9 发表于 2016-1-27 06:45:37 | 显示全部楼层
楼主请问你面试用的IDE写的程序还是make file,面试有要求可以用什么吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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