一亩三分地论坛

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

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

Twitter OA 新鲜出炉

[复制链接] |试试Instant~ |关注本帖
johnjavabean 发表于 2016-1-24 08:00:39 | 显示全部楼层 |阅读模式

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

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

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

x
刚做完twitter OA,前来分享,求大米
1. 求一个数的二进制补数,从左边第一个1开始,每一位0变1,1变0
2. 给两个string s, t, 问最多能从s中删去t几次(每删除一次剩下两个字符串拼成新的s).1point3acres缃
第二题有一个case TLE但是看不到case,试过各种优化除了kmp...求过...

评分

1

查看全部评分

本帖被以下淘专辑推荐:

allenshen 发表于 2016-1-24 13:25:18 | 显示全部楼层
第二题是不是可以用DP做?
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-1-24 14:02:03 | 显示全部楼层
allenshen 发表于 2016-1-24 13:25
第二题是不是可以用DP做?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
当时没想出来转移方程......感觉状态都不是n^2的啊...
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-24 14:51:50 | 显示全部楼层
第二题楼主是用BFS做的吗?加了哪些优化?
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-1-24 14:56:22 | 显示全部楼层
dietpepsi 发表于 2016-1-24 14:51
第二题楼主是用BFS做的吗?加了哪些优化?

dfs做的,开了个全局的map做cache
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-24 15:10:00 | 显示全部楼层
感觉这题DP不可能,估计就是搜索加优化. visit 1point3acres.com for more.
能把你的Code贴上来吗?看看有没有别的优化可以做
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-1-24 15:52:55 | 显示全部楼层
dietpepsi 发表于 2016-1-24 15:10.1point3acres缃
感觉这题DP不可能,估计就是搜索加优化
能把你的Code贴上来吗?看看有没有别的优化可以做

忘了复制了不好意思...他那个系统关了就看不到代码了。
. visit 1point3acres.com for more.唯一想到的能优化的地方是查t在s中出现的所有位置可以用kmp,这样复杂度可以降一个层级,这样也许能过吧...
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-24 16:36:17 | 显示全部楼层
可以这样优化,就是比如说,上一步删除的是s[i:i+m], m是t的长度。那么下一步规定可以删除的startIndex范围是 i - m < startIndex < n - m

比如说 s = abaxxabaxxxx, t = aba-google 1point3acres
出现的位置是[0,2]和[5,7]
上一步删除了aba在[5,7]的话,下一步可以删除的位置是从3开始的
这样可以避免生成存绝大多数的重复字符串,我觉得甚至可以去掉那个全局的map。

这样在s中查找t也可以不用从头查找了,记住上一次的删除位置,从i - m + 1开始查找

查找t在s中的所有位置是不是可以preprocess并保持一个matching list。
我的意思是每一步跟前一步比,只有startIndex是[i-m+1, i]有可能出现新的Match,只要把在这里面的查找出来并插入到matching list里。
当然删除的时候也要删除matching list里受影响的部分。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

mandysz2 发表于 2016-1-26 03:50:52 | 显示全部楼层
楼主在哪里收到oa通知?我之前也是网申了,一点消息也没有,难道默据?
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-1-26 04:36:43 | 显示全部楼层
mandysz2 发表于 2016-1-26 03:50
楼主在哪里收到oa通知?我之前也是网申了,一点消息也没有,难道默据?

我也不知道...网申第二天就通知OA了...OA第二天就安排面试
回复 支持 反对

使用道具 举报

mandysz2 发表于 2016-1-26 23:38:52 | 显示全部楼层
johnjavabean 发表于 2016-1-26 04:36
我也不知道...网申第二天就通知OA了...OA第二天就安排面试

好吧,感谢,祝你成功,加油~
回复 支持 反对

使用道具 举报

mandysz2 发表于 2016-1-26 23:39:22 | 显示全部楼层
johnjavabean 发表于 2016-1-26 04:36. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我也不知道...网申第二天就通知OA了...OA第二天就安排面试

请问下你申请的是什么地点呢?
回复 支持 反对

使用道具 举报

mandysz2 发表于 2016-1-26 23:39:43 | 显示全部楼层
johnjavabean 发表于 2016-1-26 04:36
我也不知道...网申第二天就通知OA了...OA第二天就安排面试

. 1point 3acres 璁哄潧请问下你申请的是什么地点呢?
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-1-27 05:29:13 | 显示全部楼层
mandysz2 发表于 2016-1-26 23:39
请问下你申请的是什么地点呢?

三番的,一定要够八个字...
回复 支持 反对

使用道具 举报

mandysz2 发表于 2016-1-27 11:49:51 | 显示全部楼层
johnjavabean 发表于 2016-1-27 05:29
三番的,一定要够八个字...

再次感谢楼主提供信息,祝楼主顺顺利利拿到实习~
回复 支持 反对

使用道具 举报

atwoodwang0918 发表于 2016-2-4 12:29:19 | 显示全部楼层
请问楼主面试的时候是用的codepair么?需要自己写test case然后编译么??题目是直接从hackerrank题库里面调出来的还是面试官自己口述的呀??求解答 非常感谢!!!
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-2-9 05:41:17 | 显示全部楼层
第二题我知道怎么做了。类似于LeetCode 312 Burst Balloons。
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-2-9 07:19:35 | 显示全部楼层
dietpepsi 发表于 2016-2-9 05:41
第二题我知道怎么做了。类似于LeetCode 312 Burst Balloons。
. 1point3acres.com/bbs
好的谢谢,我去研究下
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-2-9 11:28:07 | 显示全部楼层
Divide and Conquer,然后加上memoization。
回复 支持 反对

使用道具 举报

 楼主| johnjavabean 发表于 2016-2-9 12:39:30 | 显示全部楼层
dietpepsi 发表于 2016-2-9 11:28. 鍥磋鎴戜滑@1point 3 acres
Divide and Conquer,然后加上memoization。

大神写一写给我们研究下?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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