方案 2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下： 因为 2^32 为 42 亿多，所以给定一个数可能在，也可能不在其中； 这里我们把 40 亿个数中的每一个用 32 位的二进制来表示 ，假设这 40 亿个数开始放在一个文件中。 然后将这 40 亿个数分成两类:
最高位为 0
最高位为 1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20 亿，而另一个>=20 亿（相当于折半）； 与要查找的数的最高位比较并接着进入相应的文件再查找
然后再把这个文件为又分成两类:
次最高位为 0
次最高位为 1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10 亿，而另一个>=10 亿（相当于折半）； 与要查找的数的次最高位比较并接着进入相应的文件再查找。
.....
以此类推，就可以找到了，而且时间复杂度为 O(logn)。
答：
一个 MapReduce 作业由 Map 阶段和 Reduce 阶段两部分组成，这两阶段会对数据排序，从这个意义上说，MapReduce 框架本质就是一个 Distributed Sort。
在 Map 阶段，Map Task 会在本地磁盘输出一个按照 key 排序（采用的是快速排序）的文件（中间可能产生多个文件，但最终会合并成一个），在 Reduce 阶段，每个 Reduce Task 会对收到的数据排序（采用的是归并排序），这样，数据便按照 Key 分成了若干组，之后以组为单位交给 reduce 处理。
很多人的误解在 Map 阶段，如果不使用 Combiner 便不会排序，这是错误的，不管你用不用 Combiner，Map Task 均会对产生的数据排序（如果没有 Reduce Task，则不会排序，实际上 Map 阶段的排序就是为了减轻 Reduce端排序负载）。
由于这些排序是 MapReduce 自动完成的，用户无法控制，因此，在hadoop 1.x 中无法避免，也不可以关闭，但 hadoop2.x 是可以关闭的。
第五题：大数据面试题-Kafka相关（商汤科技） 问：kafka数据分区和消费者的关系，kafka的数据offset读取流程，kafka内部如何保证顺序答：
kafka数据分区和消费者的关系：1个partition只能被同组的⼀一个consumer消费，同组的consumer则起到均衡效果
kafka的数据offset读取流程：
连接ZK集群，从ZK中拿到对应topic的partition信息和partition的Leader的相关信息
连接到对应Leader对应的broker
consumer将⾃自⼰己保存的offset发送给Leader
Leader根据offset等信息定位到segment（索引⽂文件和⽇日志⽂文件）
根据索引⽂文件中的内容，定位到⽇日志⽂文件中该偏移量量对应的开始位置读取相应⻓长度的数据并返回给consumer
kafka内部如何保证顺序：kafka只能保证partition内是有序的，但是partition间的有序是没办法的。爱奇艺的搜索架构，是从业务上把需要有序的打到同一个partition。
第六题：大数据面试题-分布式相关（阿里） 问：说说三种分布式锁？答：
基于数据库实现分布式锁：（性能较差，锁表的风险，非阻塞，失败需要轮询耗CPU）
悲观锁
利用select … where … for update 排他锁
注意: 其他附加功能与实现基本一致，这里需要注意的是“where name=lock ”，name字段必须要走索引，否则会锁表。有些情况下，比如表不大，mysql优化器会不走这个索引，导致锁表问题。
乐观锁
所谓乐观锁与悲观锁最大区别在于基于CAS思想，是不具有互斥性，不会产生锁等待而消耗资源，操作过程中认为不存在并发冲突，只有update version失败后才能觉察到。我们的抢购、秒杀就是用了这种实现以防止超卖。
乐观锁是通过增加递增的版本号字段实现的。
基于缓存（Redis等）实现分布式锁：（过期时间不好控制，非阻塞，失败需要轮询耗CPU）
获取锁的时候，使用setnx加锁，并使用expire命令为锁添加一个超时时间，超过该时间则自动释放锁，锁的value值为一个随机生成的UUID，通过此在释放锁的时候进行判断。
获取锁的时候还设置一个获取的超时时间，若超过这个时间则放弃获取锁。
释放锁的时候，通过UUID判断是不是该锁，若是该锁，则执行delete进行锁释放。
基于Zookeeper实现分布式锁：（高可用、可重入、阻塞锁）
大致思想：每个客户端对某个功能加锁时，在zookeeper上的与该功能对应的指定节点的目录下，⽣生成⼀个唯一的瞬时有序节点。判断是否获取锁的方式很简单，只需要判断有序节点中序号最小的一个。当释放锁的时候，只需将这个瞬时节点删除即可。同时，其可以避免服务宕机导致的锁无法释放，⽽而产生的死锁问题。