一亩三分地论坛

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

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

Snapchat新鲜面经

[复制链接] |试试Instant~ |关注本帖
zhuhai_ZFC 发表于 2016-7-19 05:43:35 | 显示全部楼层 |阅读模式

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

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

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

x
一个小时前电话面完Snapchat,是个老美,但又不像小白,可能是小墨吧。首先问了问简历上的项目,主要是问了一个多线程的东西。问了个大概,不是很细(我连一个函数的名字都忘了,但是什么功能还是记得很清楚的。他说没关系,我知道你在说什么东西)。
然后是coding,我用了Java。问题很简单,但是第一次面试,毫无经验,在没有IDE的条件下各种不适应,还要手动import,而且之后还出了一个语法bug,还是面试官出手解决。所以上面经之前,首先给还没面过的各位找工友们一个建议:多练练在txt上直接写吧。。。。

题目是实现一个无向无权图(简单吧。。。。),要求能增加一条边、判断两个节点之间是否存在直接边、返回边的条数。第一次写没有import,各种undefined errors。虽然最后package的名字都是面试官告诉我的,但毕竟想到要import的是我,所以祈求少扣点分吧。。。。import之后还有个语法错误,是面试官出手解决的。这里估计大出血。但更大出血的是在我定义了一个adjList之后,面试官问我,adjList这个东西是线性的,有没有更好的方法。我当时一下就蒙了,图从来都是用adjList表达的,所以我说现在我只能想到这个方法,最多就是每个节点的adjacent nodes放到一个哈希表里面。然后写完了,自己写了个简单的test case,有个bug,主要是添加的边有重复的时候,边的数量统计会出错。改了一下改好了。面试官说我把每条边都对称的保存了一遍,有没有办法把storage砍掉一半?我就说,每次添加一条边的时候,把较小的节点挑出来,只把这条边保存在较小的节点的adjacency hashSet里面。他说OK。最后是follow up,没写完,说了个思路,而且可能不对。要写一个图的serialize和deserialize函数,要求打包到最小。我又蒙了,只搞过树的serialize,没搞过图的serialize 啊。只能说,首先把节点个数放在字符串的头部,然后把所有边保存为节点对,节点对用逗号分隔,每对节点内用空格分隔,然后所有的节点对放在一个字符串里面。这个follow up真的没想通,面试官强调压缩到最小,是不是在暗示什么特别的算法。

其实面完了,我仔细一想,这个题只要判断有没有边、有几条边什么的,又不要遍历节点,所以只要一张HashMap保存边就好了。把编号较小的节点作为key,编号较大的节点作为value就好了。根本不需要什么每个节点配一个hashset,所以现在心里更是凄凉。
. 1point3acres.com/bbs
总而言之,希望已经不大。只能贡献一下面经了。。。。


补充内容 (2016-7-19 06:15):
其实最后那个思路也不对。我觉得最正确的应该是用一个hashset,hashset的元素是Arraylist。arraylist两项是较小节点和较大节点。用adjList,每个节点一个hashset也可保证各项操作常数时间。但memory消耗太大。

评分

1

查看全部评分

daniel_hl 发表于 2016-7-19 07:54:58 | 显示全部楼层
follow up按照edge输出的话,每个node就会重复输出多次,比如 "1 2,1 3,1 4,2 3,2 4" 我觉得这个可以这样存: "1 2 3 4,2 3 4"   以逗号隔开分组,每组第一个是一个node,后面跟着的是比这个node大的所有node。
回复 支持 1 反对 0

使用道具 举报

wilbur_zzz 发表于 2016-7-19 07:23:57 | 显示全部楼层
楼主面的是SDET岗位吗?
回复 支持 反对

使用道具 举报

谎言之躯 发表于 2016-7-19 08:08:01 | 显示全部楼层
楼主能不能详细说一下这道题的题目要求?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 08:48:46 | 显示全部楼层
wilbur_zzz 发表于 2016-7-19 07:23
楼主面的是SDET岗位吗?
. 1point3acres.com/bbs
啥是SDET岗位?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 08:48:53 | 显示全部楼层
wilbur_zzz 发表于 2016-7-19 07:23
楼主面的是SDET岗位吗?

啥是SDET岗位?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 08:49:14 | 显示全部楼层
daniel_hl 发表于 2016-7-19 07:54
follow up按照edge输出的话,每个node就会重复输出多次,比如 "1 2,1 3,1 4,2 3,2 4" 我觉得这个可以这样存 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
说的对啊!
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 08:50:29 | 显示全部楼层
谎言之躯 发表于 2016-7-19 08:08
楼主能不能详细说一下这道题的题目要求?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
定义一个UndirectedUnweightedGraph类,首先要自己定义构造函数的参数,然后定义以下函数:addEdge(), hasEdge(), numberOfEdges()
回复 支持 反对

使用道具 举报

xl7 发表于 2016-7-19 10:19:24 | 显示全部楼层
zhuhai_ZFC 发表于 2016-7-19 08:50
定义一个UndirectedUnweightedGraph类,首先要自己定义构造函数的参数,然后定义以下函数:addEdge(), ha ...

楼主,请问下input是什么呀?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 10:21:07 | 显示全部楼层
xl7 发表于 2016-7-19 10:19
楼主,请问下input是什么呀?

其实这是面试官要我自己想清楚的,不是他告诉我的。
回复 支持 反对

使用道具 举报

wilbur_zzz 发表于 2016-7-19 10:22:57 | 显示全部楼层

Test 那看来不是了……还考多线程啊??
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 10:24:34 | 显示全部楼层
wilbur_zzz 发表于 2016-7-19 10:22.1point3acres缃
Test 那看来不是了……还考多线程啊??

是我的项目经历里面涉及到了,所以就问了一下。考得非常浅显,死锁、互斥这种多线程的关键问题统统没问。
回复 支持 反对

使用道具 举报

waikai 发表于 2016-7-19 13:03:28 | 显示全部楼层
无相无权图,用Union-Find 那种保存应该可以吧。这样好像压缩了空间.图除了adjList表示,还能matrix 表示,面试官要这个?
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 13:08:35 | 显示全部楼层
waikai 发表于 2016-7-19 13:03 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
无相无权图,用Union-Find 那种保存应该可以吧。这样好像压缩了空间.图除了adjList表示,还能matrix 表示, ...

额,UnionFind是用来找最大连通集的,没法具体体现各个节点之间的连接关系啊。比如说,1-2和2-3,与1-3和2-3在union-find看上去是一样的,因为1、2、3都是在同一个连通集里。应该不是matrix,其实感觉就是hash表,就是用一个哈希表把边存下来就好了。
回复 支持 反对

使用道具 举报

 楼主| zhuhai_ZFC 发表于 2016-7-19 22:19:01 | 显示全部楼层
顺便问一下,snapchat一般多长时间出结果?
回复 支持 反对

使用道具 举报

wilbur_zzz 发表于 2016-7-20 09:10:44 | 显示全部楼层
zhuhai_ZFC 发表于 2016-7-19 10:24
是我的项目经历里面涉及到了,所以就问了一下。考得非常浅显,死锁、互斥这种多线程的关键问题统统没问。
. from: 1point3acres.com/bbs
所以他会就简历的内容提一些技术问题咯?. 1point 3acres 璁哄潧

谢谢楼主!
回复 支持 反对

使用道具 举报

zihongc 发表于 2016-8-17 04:18:43 | 显示全部楼层
求问一下HackerRank中codePair有官方的Test Case吗? 还是只是自己想而已?
回复 支持 反对

使用道具 举报

wilbur_zzz 发表于 2016-8-18 11:12:59 | 显示全部楼层
zihongc 发表于 2016-8-17 04:18
求问一下HackerRank中codePair有官方的Test Case吗? 还是只是自己想而已?

没有官方,他会给你一些case 可能也需要你自己想
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-5 11:39:55 | 显示全部楼层
请问什么叫直接边?
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-10 01:31:03 | 显示全部楼层
同问啊, 啥叫增加一条边。。那我直接增加和目标节点的一条边不就好了?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 12:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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