【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 4894|回复: 31
收起左侧

snapchat新鲜昂赛跪经

[复制链接] |试试Instant~
我的人缘0
xiaoyehhuang23 发表于 2016-10-26 14:05:38 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩

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

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

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

x
昨天刚面的今天就知道跪了。。发个跪经回报社会也自己总结一下。. 1point 3acres 论坛
我们昨天的流程和之前面经里的很不一样,11点半一到就让吃饭。。明明都还没饿。。而且吃完就是毫无间隔的连面4场真是惨绝人寰。。。
一面就是写一个topological sort。竟然还写的磕磕绊绊,还是要多刷经典题啊。。以及白板上写和电脑上码代码也是很不一样,没有那种纵览全局的感觉,如果字丑还很容易把自己绕进去。。。followup就是问时间复杂度。. 一亩-三分-地,独家发布
二面也是面经里出现过的题,是从binary tree里找出所有duplicate的树。return应该是一个key value pair,key是任何形式表示的树,value是这个树出现的次数。我的大致思路就是对每个node,做出以这个node为根的树的serialization。然后以这个serialization为key扔到hashtable里就可以。followup就是问时间和空间复杂度。
三面是青蛙跳河,也是面经题,我用memoization的dp做。followup1是求时间复杂度,求讨论,这个我很不确定。。followup2是把青蛙跳拓展到2维的情况,这种情况下就有可能出现在某个方向上倒着跳的可能性了。。这个我也没有想得很清楚。。. visit 1point3acres for more.
四面面试官是个烙印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% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
顺便求大米求大米求大米
回复

使用道具 举报

我的人缘0
runningMajia 发表于 2016-10-26 14:19:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (38)
 
 
5% (2)  踩
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?
回复

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-26 14:25:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
runningMajia 发表于 2016-10-26 14:19
snap家不是全都要上机写代码跑结果吗?楼主遇到的是白版?

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

使用道具 举报

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

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-26 15:26:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
神罗天征 发表于 2016-10-26 15:00
请问第四题,给定string,找到它的前缀是不是就是直接把string遍历一下,然后后面的字母改成*呀?然后第二 ...

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

使用道具 举报

我的人缘0
小A要当码农 发表于 2016-10-26 23:47:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (52)
 
 
7% (4)  踩
楼主二面和三面follow up啥思路?
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 00:32:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
神罗天征 发表于 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,将所有匹配的前缀传进去。
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
keytion 发表于 2016-10-27 01:07:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
一个trie,每个节点两个状态, isPrefix, isWord;
.本文原创自1point3acres论坛再加个遍历输出所有prefix,或者word应该就可以了吧。。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 03:58:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
keytion 发表于 2016-10-27 01:07
一个trie,每个节点两个状态, isPrefix, isWord;
再加个遍历输出所有prefix,或者word应该就可以了吧。。

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

使用道具 举报

我的人缘0
keytion 发表于 2016-10-27 04:06:04 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
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)
 
 
0% (0)   【踩】
全局: 顶  100% (53)
 
 
0% (0)  踩
这道题本质就是一个bfs,我在lc上用bfs是过了的,最差就是这个青蛙一直一步一步跳,对于每一个点,这个青蛙有可能是从前面的任何一个点跳过来的,所以我觉得是 n^2
回复

使用道具 举报

我的人缘0
linweihua0 发表于 2016-10-27 07:59:28 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (7)
 
 
0% (0)  踩
青蛙跳这题肯定不是polynomial  比较loose的bound应该是O(3^n) 每个Stone triple possible steps
回复

使用道具 举报

我的人缘0
keytion 发表于 2016-10-27 08:26:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (25)
 
 
0% (0)  踩
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);
所以在每个节点,需要check O(i^0.5) 次,假设用hashset check是O(1);. 围观我们@1point 3 acres
那么总共的cost 差不多 O(n^1.5);
回复

使用道具 举报

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

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

使用道具 举报

我的人缘0
 楼主| xiaoyehhuang23 发表于 2016-10-27 08:42:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (34)
 
 
2% (1)  踩
keytion 发表于 2016-10-27 08:26
1维青蛙跳,DP的话:
如果不能往后跳,那么i节点可能的步数最多是O(i^0.5);
所以在每个节点,需要check O ...
. 1point 3acres 论坛
那你怎么看二维的情况?主要的问题是二维的情况下允许后退,那么就有可能兜圈子导致死循环。。。其实一维的情况下如果允许后退也会发生类似的情况,比如用(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

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

GMT+8, 2018-9-23 10:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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