一亩三分地论坛

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

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

Snapchat挂经

[复制链接] |试试Instant~ |关注本帖
rasperrypie 发表于 2016-8-17 01:49:32 | 显示全部楼层 |阅读模式

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

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

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

x
第一次onsite,发个面经攒RP
. Waral 鍗氬鏈夋洿澶氭枃绔,
电面:聊天+minimum window substring

onsite:
onsite四轮,每轮都是聊天+coding。面试官会介绍自己的组和工作,然后让你介绍自己+讲一个project。聊完天后做题。做题我的流程都是,先说自己的思路,然后解法。这时候面试官可能会跟你讨论,或者让你直接写。总之交流很重要。

1. number removal:给一个数组,元素是0-9的int,remove掉其中n个数,使剩下的数在原顺序的情况下最小。e.g. 7129,去掉两个数字,最小为12。 57294,去掉两个数字,剩下的最小为294。复杂度 O(length + n)。
follow up: 如果其中有一个负数怎么办?这里你需要跟面试官clarify怎么处理负数。我clarify的结果是,负数不能在剩下数的中间,例如1 -2 9,是invalid的,负数只能在剩下数的首位。例如-2 1 3。例如:7 -1 3 4,去掉一个,剩下的最小为-134。8 6 1 -8 6,去掉两个,因为-8前面有三个数,所以必须把-8去掉。
这题我没有在面经里见过,但是和面试官一步步讨论出了结果。黑人小哥,看起来人很好,交流得很好。查了下是MIT的,看起来完全不像码农。。。聊天聊了可能二十分钟。

2. ip filter。
这轮面得不好,面试的白人小哥全程心不在焉,我超不爽!在一边玩手机,体验很差。我得一直边写边跟他讲。他就在一边,“嗯”。真是很影响心情。面经题,结果写出了bug,bug改完后没有时间follow up了。聊天聊了可能二十五分钟。最不爽的一轮。小哥indentity组的。
. visit 1point3acres.com for more.
3. 给你很多圆,用圆心和半径表示,求有没有圆是相交的。朴素解法是枚举任意两圆,复杂度O(N^2)。小哥问有没有优化。优化的思路是,每个圆的x值都是个区间,只有那些x区间相交的圆,它们才有可能相交。如果两个圆x区间相交,那么就比较圆心距离和半径和,看是不是相交。这样不用枚举任意两个圆。然而worst case还是O(N^2),比如所有圆的x区间都有覆盖。
这轮是看起来人很好的中国小哥。带了另一个shadow中国小哥。小哥全程给follow up的提示,然鹅我最后还是没有时间写完,写到一半,然后跟他讲思路。这轮感觉交流的不太好,有时候我不太懂小哥的思路,没有get到他。这轮面得不是很好。

4. meeting room。把schedule打印出来。follow up,如果每个meeting有权值,选一个没有conflict的meeting组合,使weight sum最大。. more info on 1point3acres.com
面经题,follow up要求O(NlogN),讨论了,没让写。
这轮是中国小哥,broadcasting组,人很好的样子,这轮不错。
.1point3acres缃
第一个onsite,感觉面得还不错,第二天收到拒信。还是有些表现不好的地方。比如第二轮不该写出bug,然后调很久,以至于没有follow up的时间。第三轮跟面试官交流得不太好,感觉面得有点累,脑子不转,这一轮再积极点说不定就把follow up写完了。

最后,个人觉得去Snapchat工作成长的话会很不错,就是LA这个地方有点偏。旁边就是海滩,好多好多好多肌肉男帅哥,没去有点可惜。攒RPRPRPRPRPRPRP~. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
.鐣欏璁哄潧-涓浜-涓夊垎鍦

评分

7

查看全部评分

本帖被以下淘专辑推荐:

  • · Job|主题: 65, 订阅: 3
 楼主| rasperrypie 发表于 2016-8-23 01:17:57 | 显示全部楼层
lzzhang07 发表于 2016-8-23 00:46
楼主这个number removal怎么做到O(length + n)的?我觉得需要每次找min,用heap的话应该是O(length*lg(n)) ...

用贪心,从左往右扫,遇到左边的数比右边小时,remove左边大的数。
e.g., 57294,删掉3个数
扫到5,这是第一个数,不做什么
扫到7,7比5大,不做什么. 1point3acres.com/bbs
扫到2,2比7小,删掉7,现在数变成了 5294,2比5大,删掉5,数变成了294,2变成了第一个数
扫到9,9比2大,不做什么
扫到4,4比9小,删掉9,数变成了24

所以最后答案是24,数据结构的话,可以用stack
回复 支持 2 反对 1

使用道具 举报

chenxs 发表于 2016-8-17 03:02:29 | 显示全部楼层
只是运气差了点,来战TOC
回复 支持 反对

使用道具 举报

lzzhang07 发表于 2016-8-23 00:46:11 | 显示全部楼层
楼主这个number removal怎么做到O(length + n)的?我觉得需要每次找min,用heap的话应该是O(length*lg(n))啊。谢谢!
回复 支持 反对

使用道具 举报

prodigalr 发表于 2016-8-23 01:38:21 | 显示全部楼层
楼主IP filter具体是问什么? 有原题吗,谢谢。
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-8-23 01:47:23 | 显示全部楼层
rasperrypie 发表于 2016-8-23 01:17
用贪心,从左往右扫,遇到左边的数比右边小时,remove左边大的数。
e.g., 57294,删掉3个数
扫到5,这 ...

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴楼主,这题要求去掉n个数。比如57294,要求去掉2个数,是不是在扫描的时候,去掉了前面的5和7这两个数之后,就直接终止扫描了?
回复 支持 反对

使用道具 举报

 楼主| rasperrypie 发表于 2016-8-23 01:52:23 | 显示全部楼层
谎言之躯 发表于 2016-8-23 01:47 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主,这题要求去掉n个数。比如57294,要求去掉2个数,是不是在扫描的时候,去掉了前面的5和7这两个数之 ...

是的。。。。。。。。。。
回复 支持 反对

使用道具 举报

 楼主| rasperrypie 发表于 2016-8-23 01:56:12 | 显示全部楼层
prodigalr 发表于 2016-8-23 01:38.鏈枃鍘熷垱鑷1point3acres璁哄潧
楼主IP filter具体是问什么? 有原题吗,谢谢。
. 鍥磋鎴戜滑@1point 3 acres
比如 rules = {"7.0.0.0/8", "208.130.28.0/22", "7.7.0.0/16"};. 1point3acres.com/bbs
每个ip地址都是二进制的32位数,7.0.0.0/8 表示7.0.0.0的前八位。208.130.28.0/22表示208.130.28.0的前22位。7.7.0.0/16表示7.7.0.0的前16位。

ip 7.1.1.1符合7.0.0.0/8,因为7.1.1.1的前八位是7。
回复 支持 反对

使用道具 举报

laoxie09 发表于 2016-8-23 02:17:50 | 显示全部楼层
肌肉男 哈哈哈哈
回复 支持 反对

使用道具 举报

ginevoinee 发表于 2016-8-24 01:02:16 | 显示全部楼层
楼主,第四道题的follow up思路是什么呀,我想了半天没想明白
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-24 03:53:51 | 显示全部楼层
第三题 用  sweep line 扫x轴, 有intersetion 再判断是不是真的相交 ?
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-8-24 08:23:25 | 显示全部楼层
rasperrypie 发表于 2016-8-23 01:56
比如 rules = {"7.0.0.0/8", "208.130.28.0/22", "7.7.0.0/16"};
每个ip地址都是二进制的32位数,7.0.0. ...

所以IP filter这题该怎么做?楼主能讲下思路吗?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 10:54:54 | 显示全部楼层
rasperrypie 发表于 2016-8-23 01:56
比如 rules = {"7.0.0.0/8", "208.130.28.0/22", "7.7.0.0/16"};
每个ip地址都是二进制的32位数,7.0.0. ...

for each rule in rules, ip should match the rule?
回复 支持 反对

使用道具 举报

 楼主| rasperrypie 发表于 2016-9-5 21:44:58 | 显示全部楼层
pawprinter 发表于 2016-9-5 10:54
for each rule in rules, ip should match the rule?

ip should match one rule
回复 支持 反对

使用道具 举报

 楼主| rasperrypie 发表于 2016-9-5 21:45:15 | 显示全部楼层
iPhD 发表于 2016-8-24 08:23. Waral 鍗氬鏈夋洿澶氭枃绔,
所以IP filter这题该怎么做?楼主能讲下思路吗?

use Trie.......
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 21:56:19 | 显示全部楼层

why use trie? we could just iterate on the rules and check if the ip matches it.
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-5 22:28:02 | 显示全部楼层
rasperrypie 发表于 2016-8-23 01:56
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴比如 rules = {"7.0.0.0/8", "208.130.28.0/22", "7.7.0.0/16"};
每个ip地址都是二进制的32位数,7.0.0. ...

怎么说呢? 我连题读了两遍都没读懂。 谁能白话文再把题讲下? 扑街
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 22:53:57 | 显示全部楼层
leonardcohen 发表于 2016-9-5 22:28
怎么说呢? 我连题读了两遍都没读懂。 谁能白话文再把题讲下? 扑街

. 1point 3acres 璁哄潧google 'CIDR notation' and you will understand this question.
回复 支持 反对

使用道具 举报

tiancaihxx 发表于 2016-9-6 23:57:21 | 显示全部楼层
请问第三题圆心是都在一条线(x)上,还是在一个平面上(x,y)?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 03:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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