一些有意思的面试题收集

最近在网上看到一些很有意思的面试题，题目一般比较短，但是分析起来很有启发性，这里做个收集，遇到好玩的就补进来。

1. 现在有100亿个数字大小为1到10亿的数字，在这100亿个数字里边只有一个数字出现的次数是奇数次的，你用什么方法，找出这个数字呢？

这个题目比较有意思的是数的个数特别大，数本身也很大，1到10亿的数字，应该可以用int存储的，int在32位机器为4字节，也就是 2^32, 大概是 4GB = 4 * 1,000,000,000， unsigned int大概就是40亿。问题是100亿个数，可能不能全部放到内存里面去（光存储这100亿个数就得至少10G空间了）。

这个题的思路肯定是不能暴力的了，最好的方法是要遍历一次就找出来。如果进行对比排序之类的操作肯定不靠谱。考虑问题的特性，只有一个数出现的次数是奇数次的，其他的数都出现过偶数次，要利用这个特性，可以考虑位操作，异或操作的特性就是，对两个相同的值取异或，结果是0，偶数次的数进行异或也会是0，一个数和0异或的结果是本身，这样就能解决了。

考虑这些数存储在文件里面，一次读取10亿个（1G内存），遍历对每个数取异或，所有数异或的结果就是要找的那个数了。

2. 找到1-100000以内的所有质数

这个问题的思路也是不能暴力去做，因为是要找出所有的质数而不是找出某个特定的质数，我们可以用标记排除法，将不是质数的数标记出来，剩下的就都是质数了。Golang 简单代码如下：

func FastPrimes(n int) []int {
  stub := make([]bool, n)
  for i := range stub {
    stub[i] = true
  }
  sq := int(math.Sqrt(float64(n)))
  var i = 2

  for i<sq {
    for j:=i+i; j<n; j += i {
      if stub[j] == true {
        stub[j] = false
      }
    }
    i++
    for stub[i] == false {
      i++
    }
  }
  // 检索出结果
  var res []int
  for i=1; i<n; i++ {
    if stub[i] == true {
      res = append(res, i)
    }
  }

  return res
}

3. 10000000个数的数组中，某一个数出现的次数超过了一般，如何快速找到这个数
通过成对处理，遍历一次就可以了，如果两个数不同则舍弃，如果相同则留下一个，再取一个处理，知道最后剩下的那个就是结果（肯定会剩下一个）

待续