要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1897|回复: 8
收起左侧

Snapchat 面经

[复制链接] |试试Instant~ |关注本帖
damianbao 发表于 2015-11-18 10:37:35 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类General 博士 全职@Snapchat - 内推 - 技术电面  | Pass | fresh grad应届毕业生

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

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

x
一定要攒攒人品了,发个面经攒个人品!
Snapchat 电面是用hangouts那种面试,可以看到人。因为简历上写的是我的学校邮箱,然后chrome里面登陆的是我的gmail,一直进不去视频。
视频需要你的邮箱注册了hangouts。所以开始的时候晚了两分钟。
开始聊了很多简历的东西。
开始还问了些简单的东西,不太记得了。
两道紧密相连的题:
一个是 计算combinations. 是理论上的计算,计算有多少种组合方式。
大概类似word break,比如#Ilovenyc 有多少种分解方式,此时先不考虑字典。
一个是 word break 2,给个字典,如何break Ilovenyc
问了时间复杂度,worst case是什么时候,为什么solution会比brute force search好,大概说了一下怎么剪枝。
比如word:aaaaa
dict= {a, aa, aaa, aaaa, aaaaa}.. more info on 1point3acres

评分

4

查看全部评分

silenceleaf 发表于 2015-11-19 02:42:39 | 显示全部楼层
word break2 的时间复杂度是2^n吗?
回复 支持 反对

使用道具 举报

 楼主| damianbao 发表于 2015-11-19 04:06:15 | 显示全部楼层
silenceleaf 发表于 2015-11-19 02:42
word break2 的时间复杂度是2^n吗?

我觉得字典如果是worst case的时候,是的。correct me if I am wrong。
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-19 04:18:27 | 显示全部楼层
damianbao 发表于 2015-11-19 04:06
我觉得字典如果是worst case的时候,是的。correct me if I am wrong。

剪枝之后,比如说把不能break的index给存下来,这样的确能speedup,但是时间复杂度还是2^N吧,并没有实际的改变吧?
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 10:31:25 | 显示全部楼层
damianbao 发表于 2015-11-19 04:06
我觉得字典如果是worst case的时候,是的。correct me if I am wrong。

dp的话应该是O(N^2)吧,每次只需算前面到这里的string是否在字典中

补充内容 (2015-11-23 10:33):.1point3acres网
最后生成输出字串的时候是可能达到2^n级别,不过那个是跟答案相关的,应该已经是最优解了
回复 支持 反对

使用道具 举报

 楼主| damianbao 发表于 2015-11-23 13:59:02 | 显示全部楼层
kennethinsnow 发表于 2015-11-23 10:31
. Waral 博客有更多文章,dp的话应该是O(N^2)吧,每次只需算前面到这里的string是否在字典中

补充内容 (2015-11-23 10:33):
. 一亩-三分-地,独家发布
对,是要生成所有string。
回复 支持 反对

使用道具 举报

 楼主| damianbao 发表于 2015-11-23 13:59:32 | 显示全部楼层
silenceleaf 发表于 2015-11-19 04:18
剪枝之后,比如说把不能break的index给存下来,这样的确能speedup,但是时间复杂度还是2^N吧,并没有实际 ...

应该会有办法剪枝,但是worst case 可能没有枝可以剪。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-12-2 01:21:42 | 显示全部楼层
lz,第一个工几种切法怎么做?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| damianbao 发表于 2015-12-2 15:46:01 | 显示全部楼层
mooc 发表于 2015-12-2 01:21
lz,第一个工几种切法怎么做?
.本文原创自1point3acres论坛
排列组合,这样想,每个词之间可以被插入一个隔板,找有多少种插入的方式。那么就是插入0个隔板的方法数目+1个+2个+ 。。。 + n-1个。。。
结果就是要求的了。. Waral 博客有更多文章,

我没听得很清楚你要问什么,不知道有没有回答你的问题。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-27 05:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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