一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 3215|回复: 27
收起左侧

脸家面筋

[复制链接] |试试Instant~ |关注本帖
sqjsbx 发表于 2016-9-9 07:22:34 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
近期脸家,面试的时候脑抽,应该妥跪,来贡献一下面筋
美国小哥一上来先介绍了一下自己,然后就直接做题了
题目:最短连续子字符串
输入: "aabbc"  输出:"abbc". visit 1point3acres.com for more.

想了半天暴力解的,O(N^3),中间还出了bug。然后优化也没想出来,时间到了. more info on 1point3acres.com
小哥说话也巨快,中间好几次没听清。  继续加油吧


补充内容 (2016-9-10 02:19):. Waral 鍗氬鏈夋洿澶氭枃绔,
不好意思  之前没有讲清楚
找出shortest continuous substring with all characters in input,这个子字符串必须含有原字符串中的所有字符

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Josh 发表于 2016-9-10 12:15:19 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
先找出每个char最后一次出现的index,然后lo = 第一个最后出现的index
再找出每个char第一次出现的index, 然后hi = 最后一个第一次出现的index
结果就是 str[lo ... hi]

补充内容 (2016-9-10 12:20):
补充一下,第一步找出lo后把string lo以前的删掉,从 str[lo ...]开始进行第二步
回复 支持 2 反对 1

使用道具 举报

kimiwang 发表于 2016-9-12 13:28:34 | 显示全部楼层
关注一亩三分地微博:
Warald
Josh 发表于 2016-9-12 09:46
复杂度确实是一样的,应该区别不大吧,这个可能好跟面试官解释一点吧。可以说因为lo后面肯定会少一个char ...

这个做法怎么保证一定是最短的呢?
比如例子abcaabb:
第一遍
a: 0,3,4-google 1point3acres
b: 1,5,6
c: 2
按你的算法那lo=2,扔掉了前面的ab
第二遍找caabb,结果是找到caab.1point3acres缃
但是最短的是abc啊?
回复 支持 2 反对 0

使用道具 举报

daddev 发表于 2016-9-11 14:36:17 | 显示全部楼层
双指针实现O(n):  左指针初始指向位置0,右指针from 1 to len(str), 左右指针所指字符相同则左指针右移,因为此时没必要保留左边的这个字符了,直到左右指针之间的子串包含所有的字符。

a   a   b   b   c
^  ^

a   a   b   b   c
    ^  ^
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
a   a   b   b   c-google 1point3acres
    ^        ^. From 1point 3acres bbs

a   a   b   b   c
    ^            ^

补充内容 (2016-9-12 16:42):
貌似不太对,呵呵。
回复 支持 1 反对 1

使用道具 举报

wtcupup 发表于 2016-9-9 07:54:44 | 显示全部楼层
其实我觉得就是minimum window substring 的变种吧,扫一遍input string 得出所有 consecutive chars -> abc, then do a min window substring S=aabbc T=abc, output abbc
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 1 反对 0

使用道具 举报

smellycat 发表于 2016-9-9 08:13:07 | 显示全部楼层
LZ我没看懂你的题是什么意思啊~可不可以讲清楚一点。
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-9-9 08:24:34 | 显示全部楼层
我也没看懂题意。。
回复 支持 反对

使用道具 举报

 楼主| sqjsbx 发表于 2016-9-10 02:18:35 | 显示全部楼层
不好意思  之前没有讲清楚
找出shortest continuous substring with all characters in input,这个子字符串必须含有原字符串中的所有字符
回复 支持 反对

使用道具 举报

apollopffd 发表于 2016-9-11 02:34:46 | 显示全部楼层
完全不知道题什么意思,最短的可以一个字符么?如果aabbccddeeffgghh....yzzz,也就最多去掉个a 和两个z?
回复 支持 反对

使用道具 举报

linbaobei001 发表于 2016-9-11 02:39:50 | 显示全部楼层
题目没看懂啊,, 求具体再说一遍~
回复 支持 反对

使用道具 举报

gamesover 发表于 2016-9-11 03:30:51 | 显示全部楼层
我觉得我没看懂lz题目,因为按照我理解,貌似线性搜索扫描一次就解决问题了
回复 支持 反对

使用道具 举报

jocelyna 发表于 2016-9-11 13:33:49 | 显示全部楼层
扫一遍用set记录出现的distinct字符数(min), max = str.length(),遍历len from min to max(类似于sliding window一样遍历,同时从set中remove这个字符,如果set.size() == 0,说明是valid string, 此时return len)
回复 支持 反对

使用道具 举报

leonardcohen 发表于 2016-9-11 18:59:28 | 显示全部楼层
could you provide more test cases?
sorted or not?
cbbaa return abbc
if not complicated, two pointer can solve in a sliding window way.
good luck.
回复 支持 反对

使用道具 举报

alfredaria 发表于 2016-9-11 21:02:01 | 显示全部楼层
可否问楼主是哪个学校的?

补充内容 (2016-9-11 21:02):
也想拿到面试
回复 支持 反对

使用道具 举报

dhldxy 发表于 2016-9-12 02:24:26 | 显示全部楼层
daddev 发表于 2016-9-11 14:36
双指针实现O(n):  左指针初始指向位置0,右指针from 1 to len(str), 左右指针所指字符相同则左指针右移,因 ...

这个不大对吧。
eg.
. 1point3acres.com/bbsa a b b c b a
这样按照你的意思走了一遍之后会在b b c b a停了。
所以如果按照你的意思的话,是不是得要加个循环啊。
回复 支持 反对

使用道具 举报

dhldxy 发表于 2016-9-12 02:28:12 | 显示全部楼层
Josh 发表于 2016-9-10 12:15.1point3acres缃
先找出每个char最后一次出现的index,然后lo = 第一个最后出现的index
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷再找出每个char第一次出现的index, ...

比如还是用上面的例子。
a a b b c b a a a.
a: 0, 1, 6, 7, 8
b: 2, 3, 5.鐣欏璁哄潧-涓浜-涓夊垎鍦
c: 4. 1point3acres.com/bbs
所以lo:
a: 8. 1point3acres.com/bbs
所以hi:
c: 4
感觉不work啊。
你能用例子解释一下你的思路吗?谢谢。
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2016-9-12 04:12:06 | 显示全部楼层
Josh 发表于 2016-9-9 23:15
.1point3acres缃先找出每个char最后一次出现的index,然后lo = 第一个最后出现的index
再找出每个char第一次出现的index, ...

. 1point3acres.com/bbs
这个做法好。.1point3acres缃
应该是时间O(n),空间O(1)吧?
两个Map都是最多26个。. 1point3acres.com/bbs
最后的return substring方法应该不在空间使用考量内。
回复 支持 反对

使用道具 举报

lyoaix 发表于 2016-9-12 04:25:29 | 显示全部楼层
难道不是two pointers线性扫一遍就出来了么
回复 支持 反对

使用道具 举报

daddev 发表于 2016-9-12 05:42:00 | 显示全部楼层
dhldxy 发表于 2016-9-12 02:24
这个不大对吧。 -google 1point3acres
eg.
a a b b c b a

有道理。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-12 08:09:06 | 显示全部楼层
jocelyna 发表于 2016-9-11 13:33
扫一遍用set记录出现的distinct字符数(min), max = str.length(),遍历len from min to max(类似于sl ...

我觉得就是先扫一遍input string,取出所有distinct的字符组成一个target string,然后在原字符input string里找这个target的minimum window substring,除了一上来的预处理外,其他都和LC那道MWS一样,是这样吗?你也这么觉得?
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-12 08:22:34 | 显示全部楼层
dhldxy 发表于 2016-9-12 02:28
比如还是用上面的例子。 . visit 1point3acres.com for more.
a a b b c b a a a.
a: 0, 1, 6, 7, 8

a a b b c b a a a. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
a: 0, 1, 6, 7, 8
b: 2, 3, 5-google 1point3acres
c: 4
所以lo:
c: 4
接下来把lo之前的减掉,变成了:(a a b b ) c b a a a (括号里的被删了)
然后在扫一遍:
a: 6, 7, 8
b: 5
c: 4
所以hi:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
a: 6
这样结果就是:cba
你应该没理解对吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-2-26 15:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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