谷歌算法面试题，数学的威力！

引用

首先多谢评论中的几位高手提供的另外几种算法思路！我发出这个博文也就是想表达这么一个意思：不要把算法思维都禁锢在那么几种逻辑方法内，事实上还有其他很多各种奇思妙想的更有趣的算法，就比如这个用数学特性来解题的算法。

如果各位只纠结于这个算法有没有BUG、有没有局限性、效率是否达到最佳，那么我只能说很遗憾，各位没有体会到我的目的。

我的目的只有一个：条条大路通罗马，不要禁锢自己的思想，我们的算法其实可以更有趣，享受编程吧！

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

比如，如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true，所有在string2里的字母string1也都有。
如果是下面两个字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

这个算法题是我在外刊IT评论里看到的，本来题目没有什么出奇的地方，按照我的思路，也只能想到说用HashMap来查找，能实现最小的时间复杂度。
但是这篇文章里的某个面试官的算法，却让我眼前一亮，他用的是数学方法：

引用

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

看到这个算法，我想大部分人都会产生“居然还能这么干”的想法吧！
我刚刚把这个算法用java简单实现了一下，当然只是提供思路，BUG是肯定有的，局限性也肯定是有的，不过用来看看算法的思考方向还是足够了：

package com.iteye.bolide74.tester;

public class Tester {
	public static void main(String[] args) {
		int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
				53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
		String strA = "ABCDEFGHIJKLMNO";
		String strB = "AFGHIJX";
		int strAlength = strA.length(), strBlength = strB.length();
		long strA2primes = 1, strB2primes = 1;
		for (int i = 0; i < strAlength; i++) {
			strA2primes *= prime[(strA.charAt(i) - 'A')];
			if (i < strBlength) {
				strB2primes *= prime[(strB.charAt(i) - 'A')];
			}
		}
		System.out.println(strA2primes % strB2primes == 0);
	}
}

引用

(在这些陈年旧账里发现的一点技术瑕疵：字母有可能重复而字符串可能会很长，所以必须要有统计。用那个最幼稚的解决方案时，当在大字符串里找到一个字符后就把它删掉，当这样仍然是 O(n*m)次。在Hashtable里我们会有一个key->value的计数。Guy的方案在这种情况下仍然好用。)

引用自“一次谷歌面试趣事”：
http://www.aqee.net/2011/04/11/google-interviewing-story/

评论

14 楼 C.T 2011-04-29  

如果各位只纠结于这个算法有没有BUG、有没有局限性、效率是否达到最佳，那么我只能说很遗憾，各位没有体会到我的目的。

大家思考的时候都是从自身的方向出发的，不能理解你的感受很正常。大家看的方向不一样，风景不一样。

13 楼 sweat89 2011-04-19  

呵呵 有点意思····

12 楼 darren_nizna 2011-04-17  

这个算法局限性很大，字符串长了就得用大数。

11 楼 cq062364 2011-04-14  

我觉得用位图比较好，反正就26个字母，位图的大小就26，用大字符串建立位图，然后再位图中搜索小字符串中的每个字符。

10 楼 bolide74 2011-04-13  

回各位同学的各种问题：

首先多谢以上几位高手提供的另外几种算法思路！我发出这个博文也就是想表达这么一个意思：不要把算法思维都禁锢在那么几种逻辑方法内，事实上还有其他很多各种奇思妙想的更有趣的算法，就比如这个用数学特性来解题的算法。

如果各位只纠结于这个算法有没有BUG、有没有局限性、效率是否达到最佳，那么我只能说很遗憾，各位没有体会到我的目的。

我的目的只有一个：条条大路通罗马，不要禁锢自己的思想，我们的算法其实可以更有趣，享受编程吧！

9 楼 william_ai 2011-04-13  

a="ABCDEFGHIJKLMNO"  
b="AFGHIJX"  
  
ra=0  
for c in a:  
    ra|=2**(ord(c)-65)  
rb=0  
for c in b:  
    rb|=2**(ord(c)-65)  
  
r = ra|rb==ra  
print r 

8 楼 william_ai 2011-04-13  

有几个不懂的地方：

26个字母的话，用2到101的素数就ok了。103，不知道用来做什么的？

还有为什么不用两个循环来做？

if (i < strBlength) {

执行strAlength 次，执行strBlength次就ok了。

用bitmap的话是否更快些呢？

a="ABCDEFGHIJKLMNO"
b="AFGHIJX"

ra=0
for c in a:
	ra+=2**(ord(c)-65)
rb=0
for c in b:
	rb+=2**(ord(c)-65)

r = ra|rb==ra
print r

7 楼 liuyong1987 2011-04-13  

如果是这样的话，为什么不用移位来做？int[] prime = { 1, 2, 4, 8, 16,32 ... };  不是更快吗？

6 楼 liuxuejin 2011-04-13  

个人感觉，如果按照上题，bitmap更好，再说了他说的字符串。又不是只有英文字符，或许还有奇它的字符呢？例如中文？所以还是hashmap通用一点，大整数还有溢出的可能，int装不下，字符串一长，溢出很有可能！

5 楼 napoleonshow 2011-04-13  

gltop 写道

我觉得这样也可以：给两个CharSetA, CharSetB变量并赋值为0（如果都是大写字母或者不区分大小写32bit就够了），每个位对应着一个字母的索引（例如，字母A=0...Z=26）。逐个遍历两个字符串的字符，将其下标（如用当前字符-'A'）的值对应的CharSet中的数和1做逻辑或运算。
最后判断(CharSetA | CharSetB)是不是==(CharSetA)，等于就返回True，不等于返回False.

很好！！

4 楼 evanzzy 2011-04-12  

这篇外刊评伦我也看了，这个素数算法本身并不优秀，只不过提供了一种思路而已。我倒是认为把字母放在bitmap里面效率要高。用普通的hashset算法其实也不错，简单易懂。

3 楼 gltop 2011-04-12  

gltop 写道

我觉得这样也可以：给两个CharSetA, CharSetB变量并赋值为0（如果都是大写字母或者不区分大小写32bit就够了），每个位对应着一个字母的索引（例如，字母A=0...Z=26）。逐个遍历两个字符串的字符，将其下标（如用当前字符-'A'）的值对应的CharSet中的数和1做逻辑或运算。
最后判断(CharSetA | CharSetB)是不是==(CharSetA)，等于就返回True，不等于返回False.

- http://www.gltop.com

2 楼 gltop 2011-04-12  

我觉得这样也可以：给两个CharSetA, CharSetB变量并赋值为0（如果都是大写字母或者不区分大小写32bit就够了），每个位对应着一个字母的索引（例如，字母A=0...Z=26）。逐个遍历两个字符串的字符，将其下标（如用当前字符-'A'）的值对应的CharSet中的数和1做逻辑或运算。
最后判断(CharSetA | CharSetB)是不是==(CharSetA)，等于就返回True，不等于返回False.

1 楼 刀枪剑戟 2011-04-12  

别的不多说了，很给力！