美国卖车经历分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 4836|回复: 31
收起左侧

snapchat新鲜昂赛跪经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
xiaoyehhuang23 发表于 2016-10-26 14:05:38 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

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

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

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

x
昨天刚面的今天就知道跪了。。发个跪经回报社会也自己总结一下。
我们昨天的流程和之前面经里的很不一样,11点半一到就让吃饭。。明明都还没饿。。而且吃完就是毫无间隔的连面4场真是惨绝人寰。。。. 围观我们@1point 3 acres
一面就是写一个topological sort。竟然还写的磕磕绊绊,还是要多刷经典题啊。。以及白板上写和电脑上码代码也是很不一样,没有那种纵览全局的感觉,如果字丑还很容易把自己绕进去。。。followup就是问时间复杂度。
二面也是面经里出现过的题,是从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,但题目的描述有点绕,到下午最后一场的时候脑子实在有点跑不动了。。。

评分

参与人数 5大米 +17 收起 理由
真淘蛮 + 3 感谢分享!
kradnangel + 1 感谢分享!
神罗天征 + 5 感谢分享!
runningMajia + 3 感谢分享!
leixiang5 + 5 欢迎来一亩三分地论坛!

查看全部评分


上一篇:10/25/2016 Coursera OA Intern
下一篇:GoDaddy OA
我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-26 14:06:05 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
顺便求大米求大米求大米
回复 支持 反对

使用道具 举报

我的人缘0
runningMajia 发表于 2016-10-26 14:19:03 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-26 14:25:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
runningMajia 发表于 2016-10-26 14:19
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?
. 留学申请论坛-一亩三分地
那天我们在的房子网很差,加上有的题要跑的话还要创建图啥的太复杂,就白板了。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-26 15:26:39 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
神罗天征 发表于 2016-10-26 15:00.本文原创自1point3acres论坛
请问第四题,给定string,找到它的前缀是不是就是直接把string遍历一下,然后后面的字母改成*呀?然后第二 ...
. 1point 3acres 论坛
第一个问题:遍历一遍倒是可以,但是复杂度好像就会比较高,用trie会比较好。
第二个问题:加入前缀的意思是,因为如果你调用function1(加入string),那么就要找到所有match的加入过的前缀,包括在调用function1前因为调用function2而加入的前缀,所以我的想法是是不是对string和前缀分别要维护一个trie。. 牛人云集,一亩三分地
然后其实我题目还没有说完整,除了这两个功能以外还要有一个modify string的function和一个删除string的function。。
回复 支持 反对

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-10-26 23:47:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
楼主二面和三面follow up啥思路?
回复 支持 反对

使用道具 举报

我的人缘0
神罗天征 发表于 2016-10-26 23:57:25 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaoyehhuang23 发表于 2016-10-26 15:26
第一个问题:遍历一遍倒是可以,但是复杂度好像就会比较高,用trie会比较好。
第二个问题:加入前缀的意 ...

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 00:32:23 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
神罗天征 发表于 2016-10-26 23:57. more info on 1point3acres
哦哦,多谢楼主解释,那就是说调用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,将所有匹配的前缀传进去。
回复 支持 反对

使用道具 举报

我的人缘0
神罗天征 发表于 2016-10-27 00:47:11 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaoyehhuang23 发表于 2016-10-27 00:32. more info on 1point3acres
这两个函数也是我和面试官讨论之后抽象出来的两个最重要的功能,我感觉应该就要两个trie吧?。。。实际上 ...

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

使用道具 举报

我的人缘0
keytion 发表于 2016-10-27 01:07:51 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
一个trie,每个节点两个状态, isPrefix, isWord;
再加个遍历输出所有prefix,或者word应该就可以了吧。。
回复 支持 反对

使用道具 举报

我的人缘0
clxy2008 发表于 2016-10-27 03:16:59 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
求问楼主,青蛙跳河二维怎么跳,我只能想到用memorization了,dp[][][][] 前两维是上一个点坐标,后两维是x跳了多少,y跳了多少 才跳到这个点的
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 03:57:16 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
clxy2008 发表于 2016-10-27 03:16.1point3acres网
求问楼主,青蛙跳河二维怎么跳,我只能想到用memorization了,dp[][][][] 前两维是上一个点坐标,后两维是x ...

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 03:58:09 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
keytion 发表于 2016-10-27 01:07
一个trie,每个节点两个状态, isPrefix, isWord;. from: 1point3acres
再加个遍历输出所有prefix,或者word应该就可以了吧。。
.留学论坛-一亩-三分地
你这么做和用两个trie并没有本质差别吧?空间复杂度应该是一样的吧?但是还要加上判断什么的反而更复杂了?
回复 支持 反对

使用道具 举报

我的人缘0
keytion 发表于 2016-10-27 04:06:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiaoyehhuang23 发表于 2016-10-27 03:58
你这么做和用两个trie并没有本质差别吧?空间复杂度应该是一样的吧?但是还要加上判断什么的反而更复杂了 ...

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

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

使用道具 举报

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

使用道具 举报

我的人缘0
linweihua0 发表于 2016-10-27 07:59:28 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
青蛙跳这题肯定不是polynomial  比较loose的bound应该是O(3^n) 每个Stone triple possible steps
回复 支持 反对

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 08:33:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
keytion 发表于 2016-10-27 08:26
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);.本文原创自1point3acres论坛
所以在每个节点,需要check O ...

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 08:42:18 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
keytion 发表于 2016-10-27 08:26
1维青蛙跳,DP的话:.留学论坛-一亩-三分地
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);. 1point 3acres 论坛
所以在每个节点,需要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。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-21 04:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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