PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者stimim (qqaa)時間11年前 (2013/03/07 16:14)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串6/13 (看更多)

※ 引述《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