作者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