Redian新闻
>
一道Google面试题,怎么做?(题目描述有误,已修改)
avatar
一道Google面试题,怎么做?(题目描述有误,已修改)# JobHunting - 待字闺中
m*0
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)的解法。各位有更好的办法没
avatar
b*6
2
Leetcode原题,有O(n)解。问题简化成,对于一个已知的subtring,怎么快速地查找
substring的下一个字母是不是在substring里,不在的话就增加substring,在的话就
要更新substring和最长substring的长度。
用一个256的整形数组保存上次发现这个字母的位置,然后用一个变量start保存当前
substring的起始位置。如果上次发现字母的位置在start之前,就扩展substring,如
果在start之后就要更新start
这个算法把整个string遍历一次O(n),中间的查找是O(1),总共耗时O(n)
avatar
s*9
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)

avatar
m*0
4
thanks!
我之前的描述有问题,现在补充一下描述。已经修改了题目。

【在 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)

avatar
s*y
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)的解法。各位有更好的办法没

avatar
b*6
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!
: 我之前的描述有问题,现在补充一下描述。已经修改了题目。

avatar
m*0
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是因为要可变数组和删头节
: 点。

avatar
b*6
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.
:
: 母。

avatar
m*0
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

avatar
c*d
10
abcdefgabcdefg k=1 return abcdefgabcdefg
是这个意思吧,感觉方法不容易想啊

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)的解法。各位有更好的办法没

avatar
b*6
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)时间可以搜索到所有情况。

avatar
c*d
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 的大作中提到】
: 我之前的描述有问题,现在补充一下描述:
: 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)的解法。各位有更好的办法没

avatar
m*0
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)

avatar
b*6
14
我又想了一下,at least也是不对的。我的那个解是假设先找到一个符合条件的
substring

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

avatar
c*d
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)

avatar
r*t
16
就用一个包含 k 个不同的 s li ding window 就好了
avatar
r*t
17
就用一个包含 k 个不同的 s li ding window 就好了
avatar
D*r
18
我遇到了这道题。以前没刷题所以没看过解法。
我很快给出了O(N^2)解法,然后做出了一些小优化,但当场没完成O(N)解法。
后来面试人说可以给每个window一个character counter,窗口移动的时候update那个
counter,其实非常简单。
要是早点看网经就好了
avatar
l*t
19
想了半天,想不出o(n)的,和leetcode原题不同
avatar
c*l
20
didn't get it. more details?

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

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。