作者RockLee (Now of all times)
看板Prob_Solve
标题[问题] Google Interview Question (4)
时间Mon Mar 4 18:51:13 2013
原始网址:
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)
1F：推 isnoneval:这样移动 window 的时候并不会保证变小吧 03/05 15:26
2F：→ RockLee:是的，最小的 window 不见得是最後的 window 03/05 18:08
3F：→ RockLee:我会回移动过程中看到的最小 window 03/05 18:08
5F：→ Favonia:啊我不小心假设文件中只有这几个字。sorry 03/07 00:50
6F：→ seanwu:话说楼上的第30行是不是应该是 max x cur-1 啊(?) 03/07 01:13
7F：→ seanwu:觉得头往後跑但尾不动有点奇怪 03/07 01:15
8F：→ Favonia:对耶 lol 打错了 03/07 11:11