一亩三分地论坛

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

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

再次别虐的抖M之魂觉醒

[复制链接] |试试Instant~ |关注本帖
pyemma 发表于 2015-10-28 12:43:36 | 显示全部楼层 |阅读模式

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

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

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

x
今天去Snapchat onsite,体验了一下神级startup的氛围。地理位置非常的好,距离沙滩就几步远,公司隐僻在一堆厂房之中,周围没有任何明显的标志,刚到的时候完全不知道哪里是公司,后来是被保安大哥叫住然后领进“小黑屋”的。和几个工程师聊过天之后,感觉他们非常的有朝气也很有激情,给人一种非常振奋人心的感觉。闲话少说,直接上题,楼主感觉是跪了,不过体验了一次Snapchat也算是值了。

另外提一句,由于今天去onsite的人太多,楼主被挤到一个瑜伽房去面试了,没有白板只有白纸,anyway,反正都是要在电脑上编译再测试。

第一面,一个口音不是很重的三哥。上来先问了简历上的实习的project,问的比较详细。之后做题,给一个Employee类,有一个String name和一个List<Employee> directReport来表示一个公司的组织结构,然后给定一个公司的ceo和两个员工的名字,找到这两个员工的第一个common manager,给的两个员工一定存在。N-try tree的first common ancestor。楼主就用最naive的方法先找到从根到target节点的path然后在两个path中找第一个common ancestor。在电脑上写代码和测试样例,改掉测试样例的一个小bug之后通过。要求优化,说了用postorder traversal的方法来找,这样只需要遍历树一遍,说了一下整体的过程没有coding。之后问在一个很大的social network中,给两个个名字,如何快速的找到名字对应的node然后再去找他们的common friends。楼主提了一下hash,consistent hash然后就没啥了,不熟悉DHT没办法啊。还是自己准备不够充分,好多东西需要了解。

中午是一个韩国小哥带着去吃午饭,聊得很开心。

第二面,一个中年白人manager。一上来先问了问why snapchat, what's your favoriate parts of internshop in Facebook。之后做题,给定一些输入如
Employee,Manager,ItemsSold
Alice,,5. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
Bob,Alice,3
Carol,Bob,2
David,Bob,3
Eve,Alice,2
Ferris,Eve,1
要求打印出这个样子
Alice 16. more info on 1point3acres.com
    Bob 8
        Carol 2
        David 3
    Eve 3
        Ferris 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主先自己设计数据结构,和第一面那个基本一样,只是多了一个int num来记录数量,根据输入构建树,注意这里每条记录给定的顺序是随机的,所以可能先出来David,Bob,3然后才是Bob,Alice,3。不注意的话可能会有小bug报错。然后postorder算出所有node的child的数量和,然后update自己的,之后preorder打印。写的时候有个小bug,改正之后通过。follow up要求打印成这个样子
Alice 16
|-Bob 8
| |-Carol 2
| \_David 3
\_Eve 3
. 1point 3acres 璁哄潧  \_Ferris 1
然后楼主就跪在这里了,怎么改都是有bug,最后也没改出来。最后面试官说,你的大方向是对的,只是你API设计的不够好,你如果把parent需要打印的prefix也传递给child,打印起来就非常方便了。楼主终于醒悟,刷题太多导致思维僵固了,另外这一面全程要coding并且编译运行。
. visit 1point3acres.com for more.
第三面,一个年轻白人。一上来先介绍了一下Snapchat各个team什么的,然后问了问project。然后问说我们有个很huge的social network,你需要design一个system,这个system可以用来evaluate各种我们设计的朋友推荐算法,你要怎么设计。说了一下大概的设计,面试官更看重我如何准备data来做evalution,于是就也说了说这个部分。之后做题,就是根据计算机网络里面那个CIDR然后来做IP address filtering。比如给定一些rule: "7.0.0.0/8", 那么所有前8位是7的address应该全部被filter掉。楼主用hashset来存rule然后用一些位运算的方法来做filter。写完代码改了一个小bug之后测试通过。. From 1point 3acres bbs

第四面,一个年轻白人。一上来也是问了问project。然后做题,给定一个grid matrix,就是类似围棋盘那种东西。然后某些grid(放棋子的地方)上面有点,给定一个query点的位置,返回k nearest点on this grid matrix。第一开始我assume给了个list,里面是自己设计的一个结构体,记录了坐标和距离query点的距离,然后写了个comparator来sort这个list,然后返回k个node。之后要求优化到O(n),楼主就写了quick selection。之后要求再优化,然后楼主就**了,尼玛这是要让我写kd-tree的节奏,这东西曾经在普利斯顿的算法公开课写过一次,之后就再也没碰过了,果断回避之。就设计了一种逐渐膨胀的正方形的方法,不过这种方法有bug,返回的不一定是k nearest,我也指出了可能哪些情况不work,但是面试官还是让我写了,我也就写了。全程几乎在梦游,感觉这一轮和第二轮面得一样差,面完当场感觉已经和Snapchat say Goodbye了。. more info on 1point3acres.com

最后就是和HR简单的聊了一些东西,比如有什么offer啊,你选择offer的时候最看重哪些方面啊之类的,然后就被送出了building。

之后去沙滩上走了走,这是楼主最后的一个interveiw(其实一共也就3个面试)。感觉不能再天天刷题刷面经了,好多东西不是刷题能够弥补的,还是多去看看书,尝试尝试新技术,做一些自己的小project来增长一些实际的经验更靠谱。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷


补充内容 (2015-10-31 20:15):
楼主已挂...哎,所有面的全都挂了

评分

4

查看全部评分

 楼主| pyemma 发表于 2015-10-28 13:20:51 | 显示全部楼层
snowwolf 发表于 2015-10-27 21:13
最后一面返回k个最近的可不可以用max-heap?

max heap的时间复杂度也是O(nlogk)的,不符合要求,他最后要求时间复杂度小于O(n),意味着你连每个点到target点的距离不能计算
回复 支持 1 反对 0

使用道具 举报

snowwolf 发表于 2015-10-28 13:13:20 | 显示全部楼层
最后一面返回k个最近的可不可以用max-heap?
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-10-29 23:33:59 | 显示全部楼层
啊。。你们都木有behavior questions的?
回复 支持 反对

使用道具 举报

 楼主| pyemma 发表于 2015-10-30 00:27:47 | 显示全部楼层
kelvinzhong 发表于 2015-10-29 07:33
啊。。你们都木有behavior questions的?

就一轮有behavior,其他全都是纯技术面,被虐哭了
回复 支持 反对

使用道具 举报

juslun 发表于 2015-10-30 01:21:55 | 显示全部楼层
楼主 postorder 找 first common ancestor怎么做?
回复 支持 反对

使用道具 举报

weiwuwei 发表于 2015-10-31 13:50:16 | 显示全部楼层
楼主有3年以上经验吗?据说三年以上的才考design?
回复 支持 反对

使用道具 举报

liyanjia92 发表于 2015-11-1 10:33:24 | 显示全部楼层
请问楼主第二面那个打印的格式必须要是那样吗?能不能这样?
Alice 16
|-Bob 8
| |_Carol 2
| |_David 3
|_Eve 3
|_Ferris 1
回复 支持 反对

使用道具 举报

 楼主| pyemma 发表于 2015-11-1 12:10:49 | 显示全部楼层
liyanjia92 发表于 2015-10-31 18:33
请问楼主第二面那个打印的格式必须要是那样吗?能不能这样?
Alice 16
|-Bob 8

不能,如果当前节点是父节点的最后一个child,必须变成\_。
其实这个并不是很难,楼主当时脑残了,只需要把父节点的prefix和当前节点是否是最后节点一起传下去就好了。
回复 支持 反对

使用道具 举报

mumuzi 发表于 2015-11-7 13:30:47 | 显示全部楼层
pyemma 发表于 2015-11-1 12:10
不能,如果当前节点是父节点的最后一个child,必须变成\_。.鐣欏璁哄潧-涓浜-涓夊垎鍦
其实这个并不是很难,楼主当时脑残了,只需 ...

打印是挺tricky的,LZ能贴下打印的代码吗?下周要面了,跪谢
回复 支持 反对

使用道具 举报

ammmmy11 发表于 2015-11-15 15:03:15 | 显示全部楼层
请问楼主,像 \_Ferris 1这种情况parent也是最后一个节点,那么只同输出一个\_,可是前面为什么有空格
回复 支持 反对

使用道具 举报

 楼主| pyemma 发表于 2015-11-17 01:55:48 | 显示全部楼层
ammmmy11 发表于 2015-11-14 23:03
请问楼主,像 \_Ferris 1这种情况parent也是最后一个节点,那么只同输出一个\_,可是前面为什么有空格

nested structure, 缩进控制着谁是谁的child
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-20 13:20:29 | 显示全部楼层
最后一题可能是开始要缩小范围,先二分求一个包含至少k个点的正方形或者区域,然后已这个区域最大距离(比如对角线)为边长划定一个范围,在这个范围内在quisk selection
回复 支持 反对

使用道具 举报

maggiejiao 发表于 2016-1-27 11:22:17 | 显示全部楼层
LZ能看下你的code吗 跪谢mengjiao.nju@gmail.com
回复 支持 反对

使用道具 举报

syftalent 发表于 2016-2-15 08:48:33 | 显示全部楼层
最后一问O(n)是单指查询的复杂度还是包括了插入?
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-2-17 11:16:29 | 显示全部楼层
最后一题不是BFS吗?。。。。
回复 支持 反对

使用道具 举报

xzt8350 发表于 2016-3-17 07:03:29 | 显示全部楼层
楼主可以详细说下第三面的ip题吗?谢谢
回复 支持 反对

使用道具 举报

TsengJuiWang 发表于 2016-4-26 15:06:36 | 显示全部楼层
楼主可以详细说一下IP filter吗?7.0.0.0/8为啥是前八位是7呀?谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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