[問題] Google Interview Question (4)
看板Prob_Solve (計算數學 Problem Solving)作者RockLee (Now of all times)時間11年前 (2013/03/04 18:51)推噓2(2推 0噓 6→)留言8則, 4人參與討論串1/13 (看更多)
原始網址:
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)
推
03/05 15:26, , 1F
03/05 15:26, 1F
→
03/05 18:08, , 2F
03/05 18:08, 2F
→
03/05 18:08, , 3F
03/05 18:08, 3F
推
03/06 22:24, , 4F
03/06 22:24, 4F
→
03/07 00:50, , 5F
03/07 00:50, 5F
→
03/07 01:13, , 6F
03/07 01:13, 6F
→
03/07 01:15, , 7F
03/07 01:15, 7F
→
03/07 11:11, , 8F
03/07 11:11, 8F
討論串 (同標題文章)
完整討論串 (本文為第 1 之 13 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
