作者stimim (qqaa)
看板Prob_Solve
標題Re: [問題] Google Interview Question (4)
時間Thu Mar 7 16:14:19 2013
※ 引述《Leon (Achilles)》之銘言：
: ※ 引述《RockLee (Now of all times)》之銘言：
: : 雖然 pseudo code 可能比較短,
: : 但由於 interview Google 時必需寫 actual code,
: : 所以我想還是直接用實際的 Java code 表達我的想法.
: : (我假設 window 長度指的是包含的字數, 與每個字的長度無關)
: : 以 Leon 大給的例子:
: : document: b b a c b b b b c b b a
: : index: 0 1 2 3 4 5 6 7 8 9 10 11
: : occurence a: 2, 11
: : occurence b: 0, 1, 4, 5, 6, 7, 9, 10
: : occurence c: 3, 8
: : 執行過程及結果會是:
: : windowBegin = 0; windowEnd = 3
: : windowBegin = 1; windowEnd = 3
: : windowBegin = 2; windowEnd = 4
: : windowBegin = 3; windowEnd = 11
: : windowBegin = 4; windowEnd = 11
: : windowBegin = 5; windowEnd = 11
: : windowBegin = 6; windowEnd = 11
: : windowBegin = 7; windowEnd = 11
: : windowBegin = 8; windowEnd = 11
: : bestBegin = 1
: : bestEnd = 3
: : -----------------------------------------------
: 我的ㄧ些習慣: (大家互相參考一下)
: 先確定演算法是對的, 作出 complexity,
: 再用 Pseudo code 寫好
: 確定結構 ( main program, and possible data structure)
: 再寫 Code.
: 我不用 Java, 所以我只是很快的掃過你的 code
: 再你的 Program 中,
: 你決定了 window start 之後用 occurance index 去找 window ending ?
: 依照我的理解, starting point has N possibility,
: and you have K different words.
: Thus, the computational complexity should be O(N* K),
: Not the O(N* lg(K)) you claim before?
RockLee 想到的方法和我一開始想的是一樣的，
我幫他加一點說明：
首先，假設每一樣 list 都是排序過的
Pseudo code 大概會長的像這樣
Given lists = {list[1], list[2], ..., list[K]}
where list[i] = {p_i1, p_i2, ...} // 每個 list 的大小不一定會一樣
for i = 1, ..., K
list_i.push_back(INF) // 這樣在處理邊界會比較簡單
rBound = -INF
S = {}
for i = 1, ..., K
S.add({listIdx = i, idx = 0, value = list[i][0]})
if rBound < list[i][0] then
rBound = list[i][0]
minWindowSize = INF
while rBound < INF
first = S.extractMin() // compare by value
next = {
listIdx = first.listIdx,
idx = first.idx + 1,
value = list[first.listIdx][first.idx + 1]
}
windowSize = rBound - first.value + 1
if windowSize < minWindowSize then
minWindowSize = windowSize
if next.value > rBound then
rBound = next.value
S.add(next)
return minWindowSize
在這裡， while loop 最多會重複 N 次 (被看過的元素就不會再看一次)
且 S 裡面最多只會有 K 個元素
複雜度：
O(N * (O(S.add) + O(S.extractMin)))
如果用 heap 來實作 => O(N logK)
=============================================================
正確性的話：
假設最小 window 長這樣：
... word_1 ... word_2 ... ... word_K ...
1. 一開始的時候，S裡存的是每個字第一次出現的位置，
每次從 S 中被踢出來的字都是還沒檢查過的字中最位置最前面的，
而我們會把同一個字下一次出現的位置加回 S 中
=> 字從 S 中被踢出來的順序就是在文件中出現的順序
所以 word_1 一定會比 word_2, ..., work_K 早被踢出來
2. 在 word_1 和 word_K 之間沒有其他的 word_K ，
不然這不是一個最小的 window ，所以，這個時候，
這個 word_K 會出現在 S 中
3. 此時 S 裡面的 word_2, word_3, ..., word_K 會是在這個 word_1 後面
第一個出現的 word_2, word_3, ..., word_K
因為 S 總是先把最前面的字踢出來， word_1 排在其他字前面，其他的字
在 word_1 被踢出來之前都還會留在 S 中
=> rBound 會是 word_K 的位置 => 我們會檢查到這個 window
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.25.107