问一个老的google面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个老的google面试题

问一个老的google面试题# JobHunting - 待字闺中

w*t2011-02-09 08:02

1 楼

A long string text, given some characters, find the shortest
substring covering all given characters.
请问大家有没有想法，谢谢

f*42011-02-09 08:02

2 楼

quick thoughts：
两个指针p,q，先前进q直到cover了所有characters，记录当前长度
然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
maintain最短长度
需要用一个map维护出现的字符
复杂度O(n)因为相当于scan了2次

w*t2011-02-09 08:02

3 楼

谢谢，思路挺好

【在 f*******4 的大作中提到】

: quick thoughts：
: 两个指针p,q，先前进q直到cover了所有characters，记录当前长度
: 然后单步前进q，每次都尽量前进p使得pq间仍旧cover了所有characters，
: maintain最短长度
: 需要用一个map维护出现的字符
: 复杂度O(n)因为相当于scan了2次

L*Q2011-02-09 08:02

4 楼

假设str[0..n-1]表示整个字符串。基本思路是从str[0]开始，以每个位置作为substring的起点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，如何每次只用O(1)来确定substring长度。
我想可以用一个辅助数组记录每种字符出现在字符串中的位置。例如字符a出现在str[0]和str[20]两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str[1]为起点的substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字符a没被cover。这就是基本思路。
我用一个例子解释整个算法。假设字符串包括0到9的数字，整个串如下
0247324596818329654001378
第一步扫描字符串，记录下每种字符位置，如下
0：0，19，20
1：11，21
2：1，5，14
3：4，13，22
4：2，6，18
5：7，17
6：9，16
7：3，23
8：10，12，24
9：8，15
第二步，以str[0]为起点，substring的终点在str[11].
接下来，以str[1]为起点，因为丢弃了str[0]，即字符0，那么从辅助数组可以找到下一个字符0出现在str[19]，因此substring结束于str[19]。
这样每次substring起点往后一个字符，用O(1)时间可以确定结束位置。

【在 w**t 的大作中提到】

: A long string text, given some characters, find the shortest
: substring covering all given characters.
: 请问大家有没有想法，谢谢

z*c2011-02-09 08:02

5 楼

请问如何判断“pq间仍旧cover了所有characters”？是用你说的map吗？如果是的话，
key和value是什么呢？

【在 f*******4 的大作中提到】

g*e2011-02-09 08:02

6 楼

maybe by counting the number of appearance for every char in the current p
to q?
when appearance is 0, you can't move p one step further.

【在 z**c 的大作中提到】

: 请问如何判断“pq间仍旧cover了所有characters”？是用你说的map吗？如果是的话，
: key和value是什么呢？

z*c2011-02-09 08:02

7 楼

forever84说的是用map来存这个pq之间的信息,我只是不明白这个检查是O(1)的吗?
难道不需要检查每个字符都在这个map吗?那么如果那个小字符串长度是K,整个复杂度不
就是O(N*K)了?
还是我哪里理解错了?

【在 g*********e 的大作中提到】

:
: maybe by counting the number of appearance for every char in the current p
: to q?
: when appearance is 0, you can't move p one step further.

j*a2011-02-09 08:02

8 楼

substring的起
点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，
如何每次只用
O(1)来确定substring长度。
[0]和str[20]
两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str
[1]为起点的
substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字
符a没被
cover。这就是基本思路。
这个空间复杂度有点高，不如ls的想法，只需要动态更新一个histogram,时间复杂度都
是2n

【在 L***Q 的大作中提到】

: 假设str[0..n-1]表示整个字符串。基本思路是从str[0]开始，以每个位置作为substring的起点，从该位置往后直到substring能cover所有字符。那么最多就有n个起点。问题是，如何每次只用O(1)来确定substring长度。
: 我想可以用一个辅助数组记录每种字符出现在字符串中的位置。例如字符a出现在str[0]和str[20]两个地方。假设当前已经确定以str[0]为起点的substring长度。接下来应该确定以str[1]为起点的substring长度。该substring丢弃了str[0]，所以必须要至少在str[20]结束，否则字符a没被cover。这就是基本思路。
: 我用一个例子解释整个算法。假设字符串包括0到9的数字，整个串如下
: 0247324596818329654001378
: 第一步扫描字符串，记录下每种字符位置，如下
: 0：0，19，20
: 1：11，21
: 2：1，5，14
: 3：4，13，22
: 4：2，6，18