google 面试题第五解(十倍)

有一篇文章谷歌面试趣事中提到的面试题。


问题是这样的：


假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？


比如，如果是下面两个字符串：




String 1: ABCDEFGHLMNOPQRS


String 2: DCGSRQPOM


答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：




String 1: ABCDEFGHLMNOPQRS


String 2: DCGSRQPOZ


答案是false，因为第二个字符串里的Z字母不在第一个字符串里。


当他问题这个问题时，不夸张的说，我几乎要脱口而出。事实上，对这个问题我很有信心。(提示：我提供的答案对他来说显然是最糟糕的一种，从面试中他大量的各种细微表现中可以看出来)。


对于这种操作一种幼稚的做法是轮询第二个字符串里的每个字母，看它是否同在第一个字符串里。从算法上讲，这需要O(n*m)次操作，其中n是string1的长度，m是string2的长度。就拿上面的例子来说，最坏的情况下将会有16*8 = 128次操作。


一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n)次操作，之后的线性扫描需要O(m+n)次操作。同样拿上面的字串做例子，将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长，你会发现这个算法的效果会越来越好)


最终，我告诉了他一个最佳的算法，只需要O(n+m)次操作。方法就是，对第一个字串进行轮询，把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作)。然后轮询第二个字串，在Hashtable里查询每个字母，看能否找到。如果找不到，说明没有匹配成功。这将消耗掉8次操作 —— 这样两项操作加起来一共只有24次。不错吧，比前面两种方案都要好。


Guy没有被打动。他把他的皮裤子弄的沙沙响作为回应。”还有没有更好的？“他问道。


我的天？这个家伙究竟想要什么？我看看白板，然后转向他。”没有了，O(n+m)是你能得到的最好的结果了 —— 我是说，你至少要对每个字母至少访问一次才能完成这项操作 —— 而这个方案是刚好是对每个字母只访问一次“。我越想越确信我是对的。

他走到白板前，”如果这样呢 —— 假设我们有一个一定个数的字母组成字串 —— 我给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在我遍历第一个字串，把每个字母代表的素数相乘。你最终会得到一个很大的整数，对吧？然后 —— 轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。这样不行吗？“

我不知道这位老大是怎么实现素数乘除的，就我来说，实现后效果却大跌眼镜。

对于1000000次循环，

checkStringInByHashMap: 203ms

checkStringInByPrime: 3357ms

相差了10倍， 还是用 HashMap实现的又简单，又快

但是HashMap还是不够快，因为每次查询字符是不是包含时，都要hash 和查找。

于是我用bitset 实现了一个以位标志方法的算法，1000000次循环 只需要 11ms.

结论： 大牛的话也不能完全相信，一切优美算法都要以实际测试结果为准。

bitset 实现源码：

	public boolean checkIfIn(MyBitSet set) {
		long tmp;
		if (this == set)
			return true;

		while (wordsInUse > set.wordsInUse)
			words[--wordsInUse] = 0;

		// Perform logical AND on words in common
		for (int i = 0; i < wordsInUse; i++) {
			tmp = words[i];
			tmp &= set.words[i];
			if (tmp != words[i]) {
				return false;
			}
		}
		return true;
	}

以上的都以大字符串是多次使用为前提， 如果每次都不一样的话，简单的loop却是最佳方案。因为创建hashmap的成本也很高。