问个算法题3 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个算法题3

问个算法题3# JobHunting - 待字闺中

F*r2011-03-13 08:03

1 楼

版上的题，但是考古找不到讨论了。。。大家看看怎么做好？只能想到brute force的
。。。。
Given a document and a query of K words, how do u find the smallest window
that covers all the words at least once in that document? (given you know
the inverted lists of all K words, that is, for each word, you have a list
of all its occurrrences).

g*y2011-03-13 08:03

2 楼

inverted list:
A: 3, 5, 99, 21
B: 4, 23
C: 9, 20, 35
D: 1, 6, 24
Merge sort all list to produce to below sorted array:
1D 3A 4B 5A 6D 9C 20C 21A 23B 24D 35C 99A
the problem is find the smallest sub array which contains all four letters (
A, B, C, D)
It can be solved by O(n) where n is the length of the array by idea of
dynamiac progeamming and also by looking up the original inverted list:
Starting from index 0, end index 3 (we know the min lenght of the subarry is
4),
scan the four items, bookkeeping the occruences:
for eaxmple: when start index is 2, window now is 4B 5A 6D, 9C, next step is
start index = start index + 1= 3, and find next available B which is 23,
and length is 23-5, bookkeep the 5A 6D, 9C, 20C, 21A, 23B, and then slide
windows to right (by start index = start index + 1)

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

: 版上的题，但是考古找不到讨论了。。。大家看看怎么做好？只能想到brute force的
: 。。。。
: Given a document and a query of K words, how do u find the smallest window
: that covers all the words at least once in that document? (given you know
: the inverted lists of all K words, that is, for each word, you have a list
: of all its occurrrences).

F*r2011-03-13 08:03

3 楼

不是很明白startindex从0到2的过程要做些什么？这个slide window要怎么用呢？谢谢！

(

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

: inverted list:
: A: 3, 5, 99, 21
: B: 4, 23
: C: 9, 20, 35
: D: 1, 6, 24
: Merge sort all list to produce to below sorted array:
: 1D 3A 4B 5A 6D 9C 20C 21A 23B 24D 35C 99A
: the problem is find the smallest sub array which contains all four letters (
: A, B, C, D)
: It can be solved by O(n) where n is the length of the array by idea of

g*y2011-03-13 08:03

4 楼

每次start index +1，然后根据前一步的bookkeeping觉得end index move到哪儿
然后继续bookkeeping,记录上新的start index, end index直接的A, B, C, D的个数以
供下一步用。
key observation是 :这个sliding windows肯定是那个sorted arry的sub array

谢！

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

: 不是很明白startindex从0到2的过程要做些什么？这个slide window要怎么用呢？谢谢！
:
: (

F*r2011-03-13 08:03

5 楼

能给个pesudo code或是个链接么？每一步收集的sliding window对下一步有什么用呢？

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

: 每次start index +1，然后根据前一步的bookkeeping觉得end index move到哪儿
: 然后继续bookkeeping,记录上新的start index, end index直接的A, B, C, D的个数以
: 供下一步用。
: key observation是 :这个sliding windows肯定是那个sorted arry的sub array
:
: 谢！

g*r2011-03-13 08:03

6 楼

An ugly pesudo code
MinSlidingWindow(document){
number_of_words=0;
count_word={};
for(word in document){
if(word not in count_word){
count_word[word]=1;
number_of_words++;
}
}
best_interval=[1,n];
min_index=max_index=0;
count_word={};
current_words=1;
for(word in document){
if(current_words==number_of_words){
//all words are in count_word, find one candinate
if(better([min_index,max_index],best_interval){
best_interval = [min_index, max_index];
}
}
if(count_word[word]==0){
//the word never appear, add it to count_word
current_words++;
count_word[word]++;
}else{
//the word appeared before, try to delete it from front
while(count_word[document[min_index]]>1){
count_word[document[min_index]]--;
min_index++;
}
}
max_index++;
}
}

F*r2011-03-13 08:03

7 楼

这两天光顾着关注地震形势了。。。写得很明白，多谢多谢啊！

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

: An ugly pesudo code
: MinSlidingWindow(document){
: number_of_words=0;
: count_word={};
: for(word in document){
: if(word not in count_word){
: count_word[word]=1;
: number_of_words++;
: }
: }