[問題] Google Interview Question (4)

[RockLee (Now of all times)]

原始網址:
http://www.careercup.com/question?id=248673

題目:
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?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.91.210
※ 編輯: RockLee         來自: 111.252.72.25        (03/05 12:35)
推 isnoneval:這樣移動 window 的時候並不會保證變小吧
→ RockLee:是的，最小的 window 不見得是最後的 window
→ RockLee:我會回移動過程中看到的最小 window
推 Favonia:全塞到一個陣列可以嗎？ http://hpaste.org/83586
→ Favonia:啊我不小心假設文件中只有這幾個字。sorry
→ seanwu:話說樓上的第30行是不是應該是 max x cur-1 啊(?)
→ seanwu:覺得頭往後跑但尾不動有點奇怪
→ Favonia:對耶 lol 打錯了