一亩三分地论坛

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

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

Twitter Code Challenge面经

[复制链接] |试试Instant~ |关注本帖
KeenWang 发表于 2015-9-7 04:08:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Twitter - 内推 - 在线笔试 |Otherfresh grad应届毕业生

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

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

x
分享十分钟前Twitter第一轮Code Challenge面经:
一小时两道题,题目不难。找工季第一面,分享攒rp,希望对需要的童鞋们有一点点用。. more info on 1point3acres.com
题目一: Delete SubStrings: 给一个String s和一个String t, 返回一共能在s中删除t多少次。 例如s = aabb, t = ab, return = 2; s = aabcbdc, t = abc, return 1;
我基本上没太思考,直接给了最直观的答案,用helperfunction1返回s中与t相同的subString的起始位置start,用helperfunction2删除s.subString(start, t.length), 外层循环终止条件是helperfunction1返回-1或s.length < t.length, 时间复杂度是O(n^2)。应该有更好的办法,懒得想了,发烧刚好,神智还不太清楚。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
题目二:Find the first repeating letter in a string : 给定一个String s,返回第一个duplicate,例如s=abcba, return = a; 这题就更简单了,用一个hashtable<key, value> = <character, index>记录出现过的char, 出现重复的时候再用一个global var记录最小的index就行了。时间和空间复杂度都是O(n)。
九月来临,找工季浩荡开幕,大家加油!!

评分

5

查看全部评分

不要说话 发表于 2015-9-7 08:14:09 | 显示全部楼层
第二题“例如s=abcba, return = a;”,为什么return a? 难道不应该return b吗?
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-7 08:24:02 | 显示全部楼层
不要说话 发表于 2015-9-7 08:14
第二题“例如s=abcba, return = a;”,为什么return a? 难道不应该return b吗?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
应该是按首次出现的顺序,而不是按照repeat出现的顺序
回复 支持 反对

使用道具 举报

 楼主| KeenWang 发表于 2015-9-7 08:44:54 | 显示全部楼层
wenqiang88 发表于 2015-9-7 08:24
应该是按首次出现的顺序,而不是按照repeat出现的顺序

对头,原题中有说明
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-9-8 00:25:02 | 显示全部楼层
楼主是怎么拿到内推的?求介绍啊。。。。
回复 支持 反对

使用道具 举报

 楼主| KeenWang 发表于 2015-9-8 01:42:58 | 显示全部楼层
jiebour 发表于 2015-9-8 00:25
楼主是怎么拿到内推的?求介绍啊。。。。

有朋友在那里做暑期实习
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-9-12 03:44:43 | 显示全部楼层
wenqiang88 发表于 2015-9-7 08:24
应该是按首次出现的顺序,而不是按照repeat出现的顺序

强哥,到处都是你的身影啊
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-12 04:31:12 | 显示全部楼层
bobzhang2004 发表于 2015-9-12 03:44
强哥,到处都是你的身影啊

哈哈,看到昵称第一眼我就猜到你是谁了
回复 支持 反对

使用道具 举报

iorisli 发表于 2015-9-21 10:32:16 | 显示全部楼层
刚做完这个OA, 第一题删子串是求最多能删多少次, 如果greedy地去删, 不能保证次数最多. 不知道楼主test cases都过了么... 写了个dfs, 有一个大case过不了..
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-21 11:31:53 | 显示全部楼层
iorisli 发表于 2015-9-21 10:32
刚做完这个OA, 第一题删子串是求最多能删多少次, 如果greedy地去删, 不能保证次数最多. 不知道楼主test cas ...
. from: 1point3acres.com/bbs
是厉害~~~
回复 支持 反对

使用道具 举报

matrixmaster 发表于 2015-9-21 11:41:53 | 显示全部楼层
关于第一题,delete substrings, 有个问题想请教下:
如果 s = "aabcbc", t = "abc";
应该返回:1还是2呀
先谢过。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-9-21 11:43:21 | 显示全部楼层
matrixmaster 发表于 2015-9-21 11:41. more info on 1point3acres.com
关于第一题,delete substrings, 有个问题想请教下:
如果 s = "aabcbc", t = "abc";
应该返回:1还是2呀 ...

应该是2吧
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-21 20:33:27 | 显示全部楼层
关于第一题,我觉得如果先去找到所有的t的起始位置,再顺次去删应该是不行的。比如.鐣欏璁哄潧-涓浜-涓夊垎鍦

s = "bab abb bab" t = "bab" (中间的空格只是为了大家看起来方便)
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
t在s中出现3次,其中1,2两次是有重叠的。如果顺次删的话,发现删完最开始的bab后,s变为"abb bab",第2个bab的b已经被删掉了,无法再删,所以就只剩下最后的一个bab可以删。总共删了2次。. 1point 3acres 璁哄潧
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
但事实上。如果从第2个bab开始删的话,是可以删三次的。

请问楼主能否把怎么解决这个问题讲得再详细一点?多谢!
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-9-22 11:08:58 | 显示全部楼层
stellari 发表于 2015-9-21 20:33
关于第一题,我觉得如果先去找到所有的t的起始位置,再顺次去删应该是不行的。比如

s = "bab abb bab" t ...

我也马上要做Twitter的OA。
我有点没读懂你的意思,删完第一个bab之后,为什么第二个bab的第一个b被删了?而且,若按你所说,第二个bab的第一个b被删了话,那你后面说的“所以就只剩下最后一个bab可以删”又是什么意思呢?最后一个bab不就是第二个bab么?如果第一个b被删了,最后一个就是ab了呀,也就删不了呀。
总之是读到这里,有点蒙的感觉,能不能再解释一下呢?
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-9-22 11:10:56 | 显示全部楼层
matrixmaster 发表于 2015-9-21 11:41
关于第一题,delete substrings, 有个问题想请教下:
如果 s = "aabcbc", t = "abc";. visit 1point3acres.com for more.
应该返回:1还是2呀 ...

我也觉得是2,我觉得题意肯定是找连续的t在s中,然后删,删完之后看能否继续找到完整的t,能,则继续删。
所以,第一次,aabcbc - > a "abc(被删)" bc -> abc
第二次, abc又满足,所以还能被删一次,
所以是两次
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-22 12:46:02 | 显示全部楼层
老冯123 发表于 2015-9-22 11:08
我也马上要做Twitter的OA。
我有点没读懂你的意思,删完第一个bab之后,为什么第二个bab的第一个b被删了 ...

不好意思,我之前没说清楚:

“babab bbab”中用strStr()查找的话,总共能够找出3个“bab”,它们的起始下标分别是[0 2 6],我分别管它们叫“第一个”,“第二个”和“第三个”

好,现在我们从左往右依次删除“bab”。
1. 删掉“第一个”(以原数组中的0位置为起始下标的)“bab”,成功。剩余"   ab bbab"。
2. 删掉“第二个”(以原数组中的2位置为起始下标),但是不成功,因为原数组中的[0 1 2]刚刚已经都被删掉了,因此“第二个”bab已经不存在了。这时只能继续往后走:
3. 删掉“第三个”,成功

因此,最后只有两次删除bab的操作能够成功进行。

但是,如果换个顺序:
1. 先删掉“第二个”bab,成功。剩下:“ba    bbab”。
2. 这时由于刚刚的删除操作,使得在得到的字符串中的0下标处又出现了一个新的bab。删除之,成功,得到“        bab”
3. 删掉“第三个”bab,成功。

所以,左到右greedy来删就只能删2次。如果换个顺序删除的话,就能够删3次。

不知这样说是否清楚?


回复 支持 反对

使用道具 举报

老冯123 发表于 2015-9-22 13:26:55 | 显示全部楼层
stellari 发表于 2015-9-22 12:46
不好意思,我之前没说清楚:

“babab bbab”中用strStr()查找的话,总共能够找出3个“bab”,它们的起 ...

啊,原来是这样,原来这是另一楼里面的说地greedy的思想,我想的简单了,就是从左到右去删,看来是不符合题目给的最多能删几次的题意了。. 1point3acres.com/bbs
那如果是这样的话,思路是不是得到了下角标【0,2,6】之后,做3个循环(分别从0,2,6开始删),分别得出三个 被删除的次数,然后比较大小。 做几个循环就取决于strStr()后得到的脚标,这样理解greedy的解法对吗?. more info on 1point3acres.com

btw, 我check的时候,用的是s.indexOf(b) 而不是strStr(), 话说你这个strStr()是需要自己写的?

回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-22 14:08:19 | 显示全部楼层
老冯123 发表于 2015-9-22 13:26
啊,原来是这样,原来这是另一楼里面的说地greedy的思想,我想的简单了,就是从左到右去删,看来是不符合 ...
. more info on 1point3acres.com
"思路是不是得到了下角标【0,2,6】之后,做3个循环(分别从0,2,6开始删),分别得出三个 被删除的次数,然后比较大小。 做几个循环就取决于strStr()后得到的脚标,这样理解greedy的解法对吗?"

可以这样做,但这就是bruteforce了。这个算法复杂度很高,因为我们第一次删除有K种方案,第二次删除至少有K-1种方案,第三次删除有K-2种方案……。那么到最后的话,复杂度不会低于O(K!)。K可以是很大的,比如从"ababababababababababababababababababa……"中找“aba”,那就恶心了。我自己觉得这题肯定有O(N^2)或以下的解法,但我现在还没想清楚,容我再想想。

我说strStr只是想表示“字符串查找函数”,和你说的indexOf()完全是一回事。
回复 支持 反对

使用道具 举报

老冯123 发表于 2015-9-22 14:17:48 | 显示全部楼层
iorisli 发表于 2015-9-21 10:32
刚做完这个OA, 第一题删子串是求最多能删多少次, 如果greedy地去删, 不能保证次数最多. 不知道楼主test cas ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想请教一下greedy的具体思路,谢谢
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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