作者RockLee (Now of all times)
看板Prob_Solve
标题Re: [问题] Google Interview Question (4)
时间Tue Mar 5 18:11:15 2013
※ 引述《Leon (Achilles)》之铭言：
: 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] ?
虽然 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
-----------------------------------------------
import java.util.*;
class Data
{
public String word;
public int index;
public Data(String w, int i) {word = w; index = i;}
}
class FindWindow
{
public static int[] findWindow(HashMap<String, ArrayList<Integer>> document,
String[] query)
{
// 一开始将每个 occurrrences list 最小的丢入 TreeMap 就可得到第一个 window
TreeMap<Integer, Data> map = new TreeMap<Integer, Data>();
for (String s : query)
{
ArrayList<Integer> occurrrencesList = document.get(s);
if (null == occurrrencesList) {return null;}
map.put(occurrrencesList.get(0), new Data(s, 0));
}
int windowBegin = map.firstKey();
int windowEnd = map.lastKey();
int windowLength = windowEnd - windowBegin + 1;
int bestBegin = windowBegin;
int bestEnd = windowEnd;
int bestLength = windowLength;
while (true)
{
System.out.println("windowBegin = " + windowBegin + "; windowEnd = " +
windowEnd);
// 之後将 TreeMap 最小的移除并加入同一个 occurrrences list 的下一个即可移动
window
Data data = map.remove(windowBegin);
ArrayList<Integer> occurrrencesList = document.get(data.word);
// 直到任一个 occurrrences list 耗完
if (data.index == (occurrrencesList.size() - 1)) {break;}
map.put(occurrrencesList.get(data.index + 1), new Data(data.word,
data.index + 1));
windowBegin = map.firstKey();
windowEnd = map.lastKey();
windowLength = windowEnd - windowBegin + 1;
if (windowLength < bestLength)
{
bestBegin = windowBegin;
bestEnd = windowEnd;
bestLength = windowLength;
}
}
int[] result = new int[2];
result[0] = bestBegin;
result[1] = bestEnd;
return result;
}
public static void main(String[] args)
{
int[] a = {2, 11};
int[] b = {0, 1, 4, 5, 6, 7, 9, 10};
int[] c = {3, 8};
ArrayList<Integer> listA = new ArrayList<Integer>();
ArrayList<Integer> listB = new ArrayList<Integer>();
ArrayList<Integer> listC = new ArrayList<Integer>();
for (int i : a) {listA.add(i);}
for (int i : b) {listB.add(i);}
for (int i : c) {listC.add(i);}
HashMap<String, ArrayList<Integer>> document = new HashMap<String,
ArrayList<Integer>>();
document.put("a", listA);
document.put("b", listB);
document.put("c", listC);
String[] query = {"a", "b", "c"};
int[] window = findWindow(document, query);
System.out.println("bestBegin = " + window[0]);
System.out.println("bestEnd = " + window[1]);
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.252.72.25