由于太过蒟蒻，没能去thuwc2017。
从大神口中得知了一些比较有趣的面试题，于是想做个收集。
V1
来源：THUWC2017
题目
给你一个长度为 n 的 01 串，求出 1 的个数。
解法
扫一遍是 O(n) 的。忽略读入的话是可以更快的。
压位，比如我把它 16 位压一次，然后做一个 2^16 的预处理，这样时间就变成 n/16 了。
当然，作为面试你还可以这么回（zhuang）答（bi）：“我们可以使用分布式算法，有多少个 node，我们就把这个串平均分成那么多份，然后每个 node 传一份。这样时间就是 $O(\frac{n}{num(node)})。$”
V2
来源：THUWC2017
题目
给定一个随机生成器，它有 p 的概率返回 0，(1-p) 的概率返回 1，其中 p∈(0, 1)。
现在你要构造一个使用这个生成器的算法，使得返回 0 和返回 1 的概率相等。
解法
这题关键是要找到两个东西，它们发生的概率是相同的。
于是我们发现，生成 0 1 的概率跟生成 1 0 的概率是相同的，都是 p(1-p)。
因此我们随机生成两个数 x 和 y，直到 x≠y 为止，然后返回 x。
（个人感觉这个题妙啊。。。）
V3
来源：THUSC2016
题目
有一个长度为奇数的数列，其中只有 1 个数与其他不同。要求你找出这个数。
解法
最直观的是扫一遍，若当前的数与前一个不相同，则根据前后判断一下。
事实上有常数更小的方法，把序列异或起来，得到的就是答案。这样可以用位运算代替 if。