一亩三分地论坛

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

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

Snapchat OA 思路

[复制链接] |试试Instant~ |关注本帖
garderobin 发表于 2016-3-24 11:51:11 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Snapchat - 网上海投 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
还是Simple word那道题。

test cases里面有几个主要测时间复杂度,最后一个是测空间复杂度的,平常的dp过不了,DFS如果不剪枝也过不了。
楼主最后用BFS全过了,不过我的算法需要再事先把数组根据长度排序一遍,最后还原次序的时候就又要多一道了, 如果不排序的话楼主不知道该怎么把动态的复杂度降下来。

求教地里各位高人。希望能给各位提供参考。

评分

1

查看全部评分

kemeng1314 发表于 2016-3-24 11:59:08 | 显示全部楼层
他家oa怎么得的,投什么职位呢
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-24 12:04:47 | 显示全部楼层
kemeng1314 发表于 2016-3-24 11:59. more info on 1point3acres.com
他家oa怎么得的,投什么职位呢

楼主去年海投的……当时网站上我记得只有一个new grad相关的full-time可以选。
都没想到还能收到oa, 简直铁树开花.
如果找地里的内推,OA来得应该会快很多。
回复 支持 反对

使用道具 举报

moonprince0801 发表于 2016-3-25 12:26:27 | 显示全部楼层
请问楼主是每到一个新词就生成一个新的dp数组么?要是一直用一个是不是会好一些?
回复 支持 反对

使用道具 举报

moonprince0801 发表于 2016-3-25 16:36:42 | 显示全部楼层
我今天写的oa,也出现了最后一个test case不过的情况,最后用java,也是用同样的方法过了所有的testcase
个人感觉,把dp判断是否可以分割那部分写成一个额外函数,也许会有用,因为这个是我过最后一个testcase唯一的不同点。。。
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-26 10:18:54 | 显示全部楼层
moonprince0801 发表于 2016-3-25 12:26
请问楼主是每到一个新词就生成一个新的dp数组么?要是一直用一个是不是会好一些?

我没有用dp, 只有BFS。我的字典里面只存single words, 如果一个新词被bfs检查出compound,就不把它加到字典里。为了节省BFS的时候的时间和空间。
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-26 10:20:29 | 显示全部楼层
moonprince0801 发表于 2016-3-25 16:36
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴我今天写的oa,也出现了最后一个test case不过的情况,最后用java,也是用同样的方法过了所有的testcase
...
. From 1point 3acres bbs
我觉得你说的对,我也试着这样改过,就是把BFS那部分用修改过的DP来取代,理论上应该是完全没问题的,但是不知道为什么总是过不了,最后时间快到了,我只能先把BFS那个交上去了
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-26 10:21:22 | 显示全部楼层
moonprince0801 发表于 2016-3-25 16:36. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我今天写的oa,也出现了最后一个test case不过的情况,最后用java,也是用同样的方法过了所有的testcase
...

我用BFS的时候也把分割那部分拆出来了。你是DP最后全过了么?你的DP字典是动态变化的还是一开始把所有词都输进去?
回复 支持 反对

使用道具 举报

moonprince0801 发表于 2016-3-30 08:07:23 | 显示全部楼层
garderobin 发表于 2016-3-26 10:21.鐣欏璁哄潧-涓浜-涓夊垎鍦
我用BFS的时候也把分割那部分拆出来了。你是DP最后全过了么?你的DP字典是动态变化的还是一开始把所有词 ...

字典是一开始全放进去,dp最后全过了
回复 支持 反对

使用道具 举报

zhuang1234 发表于 2016-3-31 00:29:06 | 显示全部楼层
请问语言可以选择用哪些语言?test case已经指定好了是吗?谢谢!
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-31 02:15:52 | 显示全部楼层
zhuang1234 发表于 2016-3-31 00:29
请问语言可以选择用哪些语言?test case已经指定好了是吗?谢谢!
. 1point 3acres 璁哄潧
主流语言都支持的, test case是指定好的,hidden.
不需要自己处理输入输出。
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-31 02:17:36 | 显示全部楼层
moonprince0801 发表于 2016-3-30 08:07. more info on 1point3acres.com
字典是一开始全放进去,dp最后全过了

太厉害了。不需要排序对么?
我的DP真是学得不好。
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-3-31 02:21:09 | 显示全部楼层
snapchat招实习吗?
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-31 02:22:30 | 显示全部楼层
mchzh 发表于 2016-3-31 02:21
snapchat招实习吗?

最近没有听说有人拿到snapchat实习,不过应该还有机会的吧
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-3-31 02:32:37 | 显示全部楼层
garderobin 发表于 2016-3-31 02:22
最近没有听说有人拿到snapchat实习,不过应该还有机会的吧
.鐣欏璁哄潧-涓浜-涓夊垎鍦
楼主自己是海投的还是内推的?
回复 支持 反对

使用道具 举报

 楼主| garderobin 发表于 2016-3-31 02:35:29 | 显示全部楼层
mchzh 发表于 2016-3-31 02:32
楼主自己是海投的还是内推的?

我自己曾经海投过没消息,又找人内推。我也不知道这次联系我是因为海投还是内推……
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-3-31 02:44:20 | 显示全部楼层
garderobin 发表于 2016-3-31 02:35
我自己曾经海投过没消息,又找人内推。我也不知道这次联系我是因为海投还是内推……

那估计是内推起效果了,我海投了很久都没任何回复
回复 支持 反对

使用道具 举报

moonprince0801 发表于 2016-3-31 05:19:53 | 显示全部楼层
garderobin 发表于 2016-3-31 02:17
太厉害了。不需要排序对么?
我的DP真是学得不好。

不需要排序啊,我记得leetcode有类似的题,只不过那题是只对一个词查找. 鍥磋鎴戜滑@1point 3 acres
你把它扩展到所有的词就好了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 01:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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