Re: [問題] Google Interview Question (4)

[Leon (Achilles)]

※ 引述《Leon (Achilles)》之銘言：
: ※ 引述《RockLee (Now of all times)》之銘言：
: : 原始網址:
: : http://www.careercup.com/question?id=15381730
: : 題目:
: : Given a document and a query of K words,
: : how do you 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).
: : Could someone propose an algorithm in O(n)?
: : 假設 occurrrences lists 是 sorted, 用 TreeMap 應可在 O(N*logK) 解決,
: : 一開始將每個 occurrrences list 最小的丟入 TreeMap 就可得到第一個 window,
: : (key = index in the document, value = the occurrrences list it belonged & its
: : index in that occurrrences list),
: : 之後將 TreeMap 最小的移除並加入同一個 occurrrences list 的下一個即可移動
: :  window,
: : 直到任一個 occurrrences list 耗完.
: : 但要在 O(N) 的時間內解決就想不出來了...
: : 不知道板上有沒有人有什麼 idea?
: Sorry, I can't understand your writing.
: Also, the link seems to be wrong...
: Can you describe it, step by step.
: For example, there are only 3 words, (a,b,c)
: how are you going to find the window, for the document
: [b b a c b b b b c b b a] ?

嗯, 剛剛想了一下.
這個題目, 是 KMP 的變形.

難的地方在於, 你怎麼想到正確的方向
(聽起來有點廢話, 哈哈..)

這裡我採用之前的定義.

For a sentance, we are given the occurance index.
Take above example, say, only 3 words {a, b, c}.
The sentance is [b b a c b a].

The the occurance index will be
a = {3, 6}.
b = {1, 2, 5}.
c = {4 }.


在開始之前, 我們先看幾個非常簡單的作法.

1. Naive: Arbitary choose 2 position from [1, N],
   then check the condition.

2. Choose one position as the left boundary, then,
   use the max-min of the rest set the decide the right boundary.

For example, if I choose 2 as my left boundary,
then I need to choose the right boundary by the max of
d(2,3) and d(2,4) which cover set {a} and set {c}

The result window is [2, 4].

And the complexity should be O(N* K).

接下來, 就是有趣的地方了.

3. Follow the previous algorithm, inspired by KMP.
When we start from 3, actually we don't need to compare all K groups.

Because from previous step, we know [2] covers {b} for sure.
And [3,4] covers {a,c} for sure.

In this case, we only need to check the condition for set {b} !
which is d(3,5).

Then the computational complexity is O(N).
I'll leave the detail for you.



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 204.140.133.209
推 ledia:I'll leave the detail for you XD
→ scwg:怎麼用 o(log K) 決定只需要檢查 b 呢
推 stimim:我不是很確定你的意思，不過 document 可能會有其他的字，
→ stimim:所以號碼不一定是連續的
→ stimim:因此下一個開始位置不一定是 3
→ fenzhang:請問這跟KMP有何關係?