一亩三分地论坛

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

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

snapchat新鲜昂赛跪经

[复制链接] |试试Instant~ |关注本帖
xiaoyehhuang23 发表于 2016-10-26 14:05:38 | 显示全部楼层 |阅读模式

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

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

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

x
昨天刚面的今天就知道跪了。。发个跪经回报社会也自己总结一下。
我们昨天的流程和之前面经里的很不一样,11点半一到就让吃饭。。明明都还没饿。。而且吃完就是毫无间隔的连面4场真是惨绝人寰。。。
一面就是写一个topological sort。竟然还写的磕磕绊绊,还是要多刷经典题啊。。以及白板上写和电脑上码代码也是很不一样,没有那种纵览全局的感觉,如果字丑还很容易把自己绕进去。。。followup就是问时间复杂度。.鏈枃鍘熷垱鑷1point3acres璁哄潧
二面也是面经里出现过的题,是从binary tree里找出所有duplicate的树。return应该是一个key value pair,key是任何形式表示的树,value是这个树出现的次数。我的大致思路就是对每个node,做出以这个node为根的树的serialization。然后以这个serialization为key扔到hashtable里就可以。followup就是问时间和空间复杂度。
三面是青蛙跳河,也是面经题,我用memoization的dp做。followup1是求时间复杂度,求讨论,这个我很不确定。。followup2是把青蛙跳拓展到2维的情况,这种情况下就有可能出现在某个方向上倒着跳的可能性了。。这个我也没有想得很清楚。。
四面面试官是个烙印hiring manager,这轮估计跪大了。题描述起来很复杂,关键来说要实现一个类,一个function是不断不断地加入string,一个function是不断不断地加入前缀(表示成例如'abc*','e*'这样的形式)。然后每次call第一个function(加入string),同时要找到所有这个string符合的前缀。每次call第二个function(加入前缀),同时要找到所有符合这个前缀的string。具体的题还要稍微复杂一点,但关键是这两点。一看到前缀啥的自然想到要用trie,但题目的描述有点绕,到下午最后一场的时候脑子实在有点跑不动了。。。.1point3acres缃

评分

5

查看全部评分

 楼主| xiaoyehhuang23 发表于 2016-10-26 14:06:05 | 显示全部楼层
顺便求大米求大米求大米
回复 支持 反对

使用道具 举报

runningMajia 发表于 2016-10-26 14:19:03 | 显示全部楼层
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-26 14:25:36 | 显示全部楼层
runningMajia 发表于 2016-10-26 14:19
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?

那天我们在的房子网很差,加上有的题要跑的话还要创建图啥的太复杂,就白板了。。
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-10-26 15:00:50 | 显示全部楼层
请问第四题,给定string,找到它的前缀是不是就是直接把string遍历一下,然后后面的字母改成*呀?然后第二个function加入前缀,意思是这个前缀也要加入trie?包括*?
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-26 15:26:39 | 显示全部楼层
神罗天征 发表于 2016-10-26 15:00-google 1point3acres
请问第四题,给定string,找到它的前缀是不是就是直接把string遍历一下,然后后面的字母改成*呀?然后第二 ...

第一个问题:遍历一遍倒是可以,但是复杂度好像就会比较高,用trie会比较好。
第二个问题:加入前缀的意思是,因为如果你调用function1(加入string),那么就要找到所有match的加入过的前缀,包括在调用function1前因为调用function2而加入的前缀,所以我的想法是是不是对string和前缀分别要维护一个trie。
然后其实我题目还没有说完整,除了这两个功能以外还要有一个modify string的function和一个删除string的function。。
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-26 23:47:59 | 显示全部楼层
楼主二面和三面follow up啥思路?
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-10-26 23:57:25 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-26 15:26
第一个问题:遍历一遍倒是可以,但是复杂度好像就会比较高,用trie会比较好。
第二个问题:加入前缀的意 ...

哦哦,多谢楼主解释,那就是说调用function1(加入String)是返回已经加入的前缀,调用第二个function(加入前缀)是返回加入的string对吧?感觉这样好像需要两个trie呀,居然一共有四个函数……有点多啊
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-27 00:32:23 | 显示全部楼层
神罗天征 发表于 2016-10-26 23:57
哦哦,多谢楼主解释,那就是说调用function1(加入String)是返回已经加入的前缀,调用第二个function( ...

这两个函数也是我和面试官讨论之后抽象出来的两个最重要的功能,我感觉应该就要两个trie吧?。。。实际上的问题还要稍微复杂一点,是一共有四个函数,一个add一个modify一个delete,都是针对string。还有一个叫observe的函数,参数是一个前缀,一个callback function,call了这个函数以后,会对所有add过的string进行匹配,匹配上的就call一下callback function,参数是匹配上的那个string。在call过observe这个函数后(可以call很多次),如果再去call add或者modify或者delete,那么在做完应该的操作后,还要call一下那个callback function,将所有匹配的前缀传进去。
回复 支持 反对

使用道具 举报

神罗天征 发表于 2016-10-27 00:47:11 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-27 00:32
这两个函数也是我和面试官讨论之后抽象出来的两个最重要的功能,我感觉应该就要两个trie吧?。。。实际上 ...

这也太难了吧……一个小时能写这么多我觉得都不用去面试了……
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-27 01:07:51 | 显示全部楼层
一个trie,每个节点两个状态, isPrefix, isWord; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
再加个遍历输出所有prefix,或者word应该就可以了吧。。
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-27 03:16:59 | 显示全部楼层
求问楼主,青蛙跳河二维怎么跳,我只能想到用memorization了,dp[][][][] 前两维是上一个点坐标,后两维是x跳了多少,y跳了多少 才跳到这个点的
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-27 03:57:16 | 显示全部楼层
clxy2008 发表于 2016-10-27 03:16
求问楼主,青蛙跳河二维怎么跳,我只能想到用memorization了,dp[][][][] 前两维是上一个点坐标,后两维是x ...

我大概也是那么做的。。和一维的主要差别应该就是递推公式那里,现在有3*3=9种移动的可能性,然后这些可能性里面哪些要排除掉要想清楚(比如跳出范围了,但是出现负的速度是可以的),另外你怎么看一维情况下的复杂度?
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-27 03:58:09 | 显示全部楼层
keytion 发表于 2016-10-27 01:07
一个trie,每个节点两个状态, isPrefix, isWord;
再加个遍历输出所有prefix,或者word应该就可以了吧。。

你这么做和用两个trie并没有本质差别吧?空间复杂度应该是一样的吧?但是还要加上判断什么的反而更复杂了?
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-27 04:06:04 | 显示全部楼层
xiaoyehhuang23 发表于 2016-10-27 03:58
你这么做和用两个trie并没有本质差别吧?空间复杂度应该是一样的吧?但是还要加上判断什么的反而更复杂了 ...

BigO notation的话空间和时间复杂度没区别。

方便之处是,
1)当你做完任意一个insert prefix操作之后,就可以从这个TrieNode call 遍历的routine.不用在另一颗Trie上搜到对应节点。
2)当你做insert word的操作的同时,把路径上isPrefix true的点记下来就行了
回复 支持 反对

使用道具 举报

clxy2008 发表于 2016-10-27 04:06:28 | 显示全部楼层
这道题本质就是一个bfs,我在lc上用bfs是过了的,最差就是这个青蛙一直一步一步跳,对于每一个点,这个青蛙有可能是从前面的任何一个点跳过来的,所以我觉得是 n^2
回复 支持 反对

使用道具 举报

linweihua0 发表于 2016-10-27 07:59:28 | 显示全部楼层
青蛙跳这题肯定不是polynomial  比较loose的bound应该是O(3^n) 每个Stone triple possible steps
回复 支持 反对

使用道具 举报

keytion 发表于 2016-10-27 08:26:27 | 显示全部楼层
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);
所以在每个节点,需要check O(i^0.5) 次,假设用hashset check是O(1);
那么总共的cost 差不多 O(n^1.5);
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-27 08:33:35 | 显示全部楼层
keytion 发表于 2016-10-27 08:26
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);
所以在每个节点,需要check O ...

对我和你的复杂度算的是一样的。。。你上面那个trie说的也很有道理,厉害啊
回复 支持 反对

使用道具 举报

 楼主| xiaoyehhuang23 发表于 2016-10-27 08:42:18 | 显示全部楼层
keytion 发表于 2016-10-27 08:26.1point3acres缃
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);
所以在每个节点,需要check O ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
那你怎么看二维的情况?主要的问题是二维的情况下允许后退,那么就有可能兜圈子导致死循环。。。其实一维的情况下如果允许后退也会发生类似的情况,比如用(l,v)表示在l的位置速度为v,那么如果要做(l,0),就需要得到(l+1,1),(l+1,1)又可以通过(l+1,0)得到,(l+1,0)又可以通过(l,-1)得到,(l,-1)又可以通过(l,0)得到,这样就兜回去了,那就死循环了。。我想的是在dfs的过程中,记录下当前分支访问过的情况,如果出现了之前访问过的情况,就认为这条分支为False。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 08:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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