一亩三分地论坛

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

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

Snapchat 面经

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

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

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

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

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

评分

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。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
dp的话应该是O(N^2)吧,每次只需算前面到这里的string是否在字典中

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

使用道具 举报

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

补充内容 (2015-11-23 10:33):
. From 1point 3acres bbs
对,是要生成所有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,第一个工几种切法怎么做?
回复 支持 反对

使用道具 举报

 楼主| damianbao 发表于 2015-12-2 15:46:01 | 显示全部楼层
mooc 发表于 2015-12-2 01:21
lz,第一个工几种切法怎么做?

排列组合,这样想,每个词之间可以被插入一个隔板,找有多少种插入的方式。那么就是插入0个隔板的方法数目+1个+2个+ 。。。 + n-1个。。。
. 1point3acres.com/bbs结果就是要求的了。

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 12:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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