一亩三分地论坛

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

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

脸家面筋

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

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

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

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

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

想了半天暴力解的,O(N^3),中间还出了bug。然后优化也没想出来,时间到了
小哥说话也巨快,中间好几次没听清。  继续加油吧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Josh 发表于 2016-9-10 12:15:19 | 显示全部楼层
先找出每个char最后一次出现的index,然后lo = 第一个最后出现的index
再找出每个char第一次出现的index, 然后hi = 最后一个第一次出现的index
结果就是 str[lo ... hi]
.1point3acres缃
补充内容 (2016-9-10 12:20):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充一下,第一步找出lo后把string lo以前的删掉,从 str[lo ...]开始进行第二步
回复 支持 2 反对 1

使用道具 举报

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

这个做法怎么保证一定是最短的呢?
比如例子abcaabb:
第一遍
a: 0,3,4
b: 1,5,6
c: 2. Waral 鍗氬鏈夋洿澶氭枃绔,
按你的算法那lo=2,扔掉了前面的ab .鏈枃鍘熷垱鑷1point3acres璁哄潧
第二遍找caabb,结果是找到caab
但是最短的是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. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    ^        ^

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
回复 支持 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?.鏈枃鍘熷垱鑷1point3acres璁哄潧
cbbaa return abbc
if not complicated, two pointer can solve in a sliding window way.
good luck.
回复 支持 反对

使用道具 举报

alfredaria 发表于 2016-9-11 21:02:01 | 显示全部楼层
可否问楼主是哪个学校的?
. from: 1point3acres.com/bbs
补充内容 (2016-9-11 21:02):
也想拿到面试
回复 支持 反对

使用道具 举报

dhldxy 发表于 2016-9-12 02:24:26 | 显示全部楼层
daddev 发表于 2016-9-11 14:36.1point3acres缃
双指针实现O(n):  左指针初始指向位置0,右指针from 1 to len(str), 左右指针所指字符相同则左指针右移,因 ...
. visit 1point3acres.com for more.
这个不大对吧。
eg. . 1point 3acres 璁哄潧
a a b b c b a
这样按照你的意思走了一遍之后会在b b c b a停了。
所以如果按照你的意思的话,是不是得要加个循环啊。
回复 支持 反对

使用道具 举报

dhldxy 发表于 2016-9-12 02:28:12 | 显示全部楼层
Josh 发表于 2016-9-10 12:15
先找出每个char最后一次出现的index,然后lo = 第一个最后出现的index
再找出每个char第一次出现的index, ...

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

使用道具 举报

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

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这个做法好。
应该是时间O(n),空间O(1)吧?. from: 1point3acres.com/bbs
两个Map都是最多26个。
最后的return substring方法应该不在空间使用考量内。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

有道理。
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-12 08:09:06 | 显示全部楼层
jocelyna 发表于 2016-9-11 13:33. 1point 3acres 璁哄潧
扫一遍用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. From 1point 3acres bbs
比如还是用上面的例子。
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. 1point3acres.com/bbs
b: 2, 3, 5
c: 4
所以lo:
c: 4
接下来把lo之前的减掉,变成了:(a a b b ) c b a a a (括号里的被删了). 1point3acres.com/bbs
然后在扫一遍:
a: 6, 7, 8
b: 5
c: 4
所以hi:
a: 6. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这样结果就是:cba
你应该没理解对吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:20

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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