一道Google面试题，怎么做？（题目描述有误，已修改） - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道Google面试题，怎么做？（题目描述有误，已修改）

一道Google面试题，怎么做？（题目描述有误，已修改）# JobHunting - 待字闺中

m*02016-02-27 08:02

1 楼

我之前的描述有问题，现在补充一下描述：
define: a distinct character in returned string means the character's number
of appearance equals one.
Given a string, find the length of longest sub-string(s) which contain at
most K distinct characters.
for example,
given string="AABBCC", K=1, return="AABBCC"
given string="AAXBBYCCC", K=1, return="BBYCCC"
想了半天只想到了O(n^2)的解法。各位有更好的办法没

b*62016-02-27 08:02

2 楼

Leetcode原题，有O(n)解。问题简化成，对于一个已知的subtring，怎么快速地查找
substring的下一个字母是不是在substring里，不在的话就增加substring，在的话就
要更新substring和最长substring的长度。
用一个256的整形数组保存上次发现这个字母的位置，然后用一个变量start保存当前
substring的起始位置。如果上次发现字母的位置在start之前，就扩展substring，如
果在start之后就要更新start
这个算法把整个string遍历一次O(n)，中间的查找是O(1)，总共耗时O(n)

s*92016-02-27 08:02

3 楼

invariable:
p1: start of substring,
p2: end of substring,
hashset: set of chars in substring.
pmax: start of answer so far
lmax: size of answer so far
forword p2, update hashset, pmax, lmax. depending on size of hashset,
forward p1 or p2.

【在 b********6 的大作中提到】

: Leetcode原题，有O(n)解。问题简化成，对于一个已知的subtring，怎么快速地查找
: substring的下一个字母是不是在substring里，不在的话就增加substring，在的话就
: 要更新substring和最长substring的长度。
: 用一个256的整形数组保存上次发现这个字母的位置，然后用一个变量start保存当前
: substring的起始位置。如果上次发现字母的位置在start之前，就扩展substring，如
: 果在start之后就要更新start
: 这个算法把整个string遍历一次O(n)，中间的查找是O(1)，总共耗时O(n)

m*02016-02-27 08:02

4 楼

thanks！
我之前的描述有问题，现在补充一下描述。已经修改了题目。

【在 b********6 的大作中提到】

s*y2016-02-27 08:02

5 楼

K=1?

number

【在 m******0 的大作中提到】

: 我之前的描述有问题，现在补充一下描述：
: define: a distinct character in returned string means the character's number
: of appearance equals one.
: Given a string, find the length of longest sub-string(s) which contain at
: most K distinct characters.
: for example,
: given string="AABBCC", K=1, return="AABBCC"
: given string="AAXBBYCCC", K=1, return="BBYCCC"
: 想了半天只想到了O(n^2)的解法。各位有更好的办法没

b*62016-02-27 08:02

6 楼

思路差不多，可以用array[queue]来解决，同样的O(n)
queue里存对应字母的所有位置，substring用start和end来标定，end每进一位，就把
位置存到对应字母的queue里。如果最小重复的要求被打破，就把start进位，start每
进一位就把start经过的那个字母的queue里pop。直到有一个pop以后变成distinct字母。
array的查找是O(1)，queue的push pop操作是O(1)，整个数组遍历下来，pop和push的
次数不超过string长度。用queue而不用多重array或vector是因为要可变数组和删头节
点。

【在 m******0 的大作中提到】

: thanks！
: 我之前的描述有问题，现在补充一下描述。已经修改了题目。

m*02016-02-27 08:02

7 楼

这个办法不work，因为无法确定right pointer停止的位置。如果你扫到的distinct
char多于K，于是就停止，但如果你继续向右扫，distinct char可能就小于K了。
e.g.
ABB, K=1. in your method, when end points to index=1 it will stop, since
there are two distinct chars (A, B), but you should go on, since when you
have ABB, distinct char drops to one.

母。

【在 b********6 的大作中提到】

: 思路差不多，可以用array[queue]来解决，同样的O(n)
: queue里存对应字母的所有位置，substring用start和end来标定，end每进一位，就把
: 位置存到对应字母的queue里。如果最小重复的要求被打破，就把start进位，start每
: 进一位就把start经过的那个字母的queue里pop。直到有一个pop以后变成distinct字母。
: array的查找是O(1)，queue的push pop操作是O(1)，整个数组遍历下来，pop和push的
: 次数不超过string长度。用queue而不用多重array或vector是因为要可变数组和删头节
: 点。

b*62016-02-27 08:02

8 楼

想错了，我的算法是at least有这么多distinct字母
我现在有个思路是先把string过一遍，保存每个字母的位置信息。整个string就被那些
只出现一次的字母分割成n < length的小区间。然后就把两头的区间砍掉，如何取舍砍
哪头，greedy algorithm不合适，我也没想出好办法，问题在于砍小区间的时候可能会
生成更多的distinct characters

【在 m******0 的大作中提到】

: 这个办法不work，因为无法确定right pointer停止的位置。如果你扫到的distinct
: char多于K，于是就停止，但如果你继续向右扫，distinct char可能就小于K了。
: e.g.
: ABB, K=1. in your method, when end points to index=1 it will stop, since
: there are two distinct chars (A, B), but you should go on, since when you
: have ABB, distinct char drops to one.
:
: 母。

m*02016-02-27 08:02

9 楼

at least的话，也不对，道理是一样的，随着right pointer移动，distinct字母数既
可能增加，也可能减少。传统two pointer方法失去了basis。
我的想法是：
设置两个pointers，p11. p1=0, p2 scan from 1 to len
2. p1=1, p2 scan from len to 2
以上两步，就能得到所有[0,i], [1,i] (1<=i<=len)范围内的distinct char的个数（
pointer每移动一次，可以O(1)时间得到distinct char的个数）
然后再令p1=2, 重复上面步骤，又得到[2,i], [3,i]的distinct char个数
依次下去，O(n^2)时间可以搜索到所有情况。

【在 b********6 的大作中提到】

: 想错了，我的算法是at least有这么多distinct字母
: 我现在有个思路是先把string过一遍，保存每个字母的位置信息。整个string就被那些
: 只出现一次的字母分割成n < length的小区间。然后就把两头的区间砍掉，如何取舍砍
: 哪头，greedy algorithm不合适，我也没想出好办法，问题在于砍小区间的时候可能会
: 生成更多的distinct characters

c*d2016-02-27 08:02

10 楼

abcdefgabcdefg k=1 return abcdefgabcdefg
是这个意思吧，感觉方法不容易想啊

number

【在 m******0 的大作中提到】

b*62016-02-27 08:02

11 楼

at least是对的，你再想想
你的方法可以简化成
for i = 1 to n
scan to end，
找scan过程中的符合条件的最大string。
最后是O(n^2)

【在 m******0 的大作中提到】

: at least的话，也不对，道理是一样的，随着right pointer移动，distinct字母数既
: 可能增加，也可能减少。传统two pointer方法失去了basis。
: 我的想法是：
: 设置两个pointers，p1: 1. p1=0, p2 scan from 1 to len
: 2. p1=1, p2 scan from len to 2
: 以上两步，就能得到所有[0,i], [1,i] (1<=i<=len)范围内的distinct char的个数（
: pointer每移动一次，可以O(1)时间得到distinct char的个数）
: 然后再令p1=2, 重复上面步骤，又得到[2,i], [3,i]的distinct char个数
: 依次下去，O(n^2)时间可以搜索到所有情况。

c*d2016-02-27 08:02

12 楼

我觉得只能用递归吧
getsubstr(str,k)
{
num = number of distinct charactor in str
p = positions of distinct charactor in str
if num<=k
return str
else
str_1=str(1,p_{k+1}-1)
str_2=str(p_1+1,p_{k+2}-1)
...
str_m=str(p_{num-k-1}+1,end of str)
for all i
substr_i=getsubstr(str_i,k)
return substr_i with max length
}

number

【在 m******0 的大作中提到】

m*02016-02-27 08:02

13 楼

我仍然不觉得at least是对的，因为随着一个pointer增加，distinct char的数量可能
增加可能减少。你可以把你steps详细写出来，我帮你找一个反例
你后面summary没错，这样的确是简化了。

【在 b********6 的大作中提到】

: at least是对的，你再想想
: 你的方法可以简化成
: for i = 1 to n
: scan to end，
: 找scan过程中的符合条件的最大string。
: 最后是O(n^2)

b*62016-02-27 08:02

14 楼

我又想了一下，at least也是不对的。我的那个解是假设先找到一个符合条件的
substring

【在 m******0 的大作中提到】

: 我仍然不觉得at least是对的，因为随着一个pointer增加，distinct char的数量可能
: 增加可能减少。你可以把你steps详细写出来，我帮你找一个反例
: 你后面summary没错，这样的确是简化了。

c*d2016-02-27 08:02

15 楼

再提一下，可以建立一个nxn的table储存每次substr的搜索结果
最原始的方法相当于找出table所有的值，递归的方法只需要找出很小一部分

at

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

: 我觉得只能用递归吧
: getsubstr(str,k)
: {
: num = number of distinct charactor in str
: p = positions of distinct charactor in str
: if num<=k
: return str
: else
: str_1=str(1,p_{k+1}-1)
: str_2=str(p_1+1,p_{k+2}-1)

r*t2016-02-27 08:02

16 楼

就用一个包含 k 个不同的 s li ding window 就好了

r*t2016-02-27 08:02

17 楼

就用一个包含 k 个不同的 s li ding window 就好了

D*r2016-02-27 08:02

18 楼

我遇到了这道题。以前没刷题所以没看过解法。
我很快给出了O（N^2）解法，然后做出了一些小优化，但当场没完成O（N）解法。
后来面试人说可以给每个window一个character counter，窗口移动的时候update那个
counter，其实非常简单。
要是早点看网经就好了

l*t2016-02-27 08:02

19 楼

想了半天，想不出o（n）的，和leetcode原题不同

c*l2016-02-27 08:02

20 楼

didn't get it. more details?

【在 D***r 的大作中提到】

: 我遇到了这道题。以前没刷题所以没看过解法。
: 我很快给出了O（N^2）解法，然后做出了一些小优化，但当场没完成O（N）解法。
: 后来面试人说可以给每个window一个character counter，窗口移动的时候update那个
: counter，其实非常简单。
: 要是早点看网经就好了