Re: [問題] Google Interview Question (4)
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/03/05 12:23)推噓1(1推 0噓 2→)留言3則, 2人參與討論串2/13 (看更多)
※ 引述《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] ?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.170.77.243
推
03/05 12:38, , 1F
03/05 12:38, 1F
→
03/05 12:39, , 2F
03/05 12:39, 2F
→
03/05 13:07, , 3F
03/05 13:07, 3F
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 2 之 13 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
