海量数据处理相关题目（互联网公司常问）
一：常见的题目：
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
2. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query
的频度排序
3. 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词
4. 海量日志数据，提取出某日访问百度次数最多的那个IP。
5. 2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
6. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
7. 怎么在海量数据中找出重复次数最多的一个
8. 上千万or亿数据（有重复），统计其中出现次数最多的前N个数据。 统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率，比如 出现次数>数据总数／N的一定是在前N个之内
9. 1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
10. 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。
11. 一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。
12. 有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复要按照query的频度排序
13. 100w个数中找最大的前100个数
14. 寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
15. 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)？
讯雷
一笔：C++，STL为主，少量数据结构。全是客观题
二笔：三条大题。
搜索引擎公司
笔试：
1. 图的遍历方法(广度和深度），他们的非递归方法用什么实现
2. 大型项目的编译依赖问题（考拓扑排序）
3. 给出1K内存1M的机器上，推导出非死循环程序的执行时间上限
4. 程序改错（野指针，数组越界，参数越界）
5. 100亿规模的URL记录增删改的系统设计，要求分布式设计，满足快速匹配和查询URL记录的要求
一面
C按照储存位置区分，分为哪几种变量？分别储存在哪里？
一个无序数组，找出第二大元素。（要求非常优化，很tricky的技巧）
静态变量在内存中放在哪个段？
写一个函数，决定该机器上，栈是向上还是向下生长？条件：函数入栈的方向，局部变量定义的先后都不可知
写一个脚本，批量该linux下的文件名后缀（关键是用到basename命令,就容易了）
什么是守护进程？如何写一个linux下守护进程？
快速排序的最好和最坏情况分析，以及他们的算法复杂度。
智力题：有一个迷宫MxN, 中间无障碍，从左上角走到右下角，每步只能往右走或往下走，问有多少种不同路线。
二面：
说出OOD的一些设计原则。
写出堆排序的具体思路。
给出一个链表，用堆排序变成一个有序的链表（几分钟写程序）
写SQL语句，考了group by
数据库索引有哪几种？
hash有什么缺点？hash索引在什么情况下比B+ tree索引还要慢（假设hash函数设计得很好，没有冲突）
智力题：三只青蛙的证明题（忘了）
某网络设备公司
面试：
多叉树化二叉树
STL中的vector如何实现增长
printf中，可变参列表的实现原理
TCP三次握手过程，一些细节的why
最小生成树
select函数的作用，参数
setsockopt的作用，你用过哪些参数，他们的作用
SIGPIPE什么情况下产生？如何处理？
用过哪些设计模式？讲出singleton和observer模式，以及在你项目中的应用
类构造或析构函数中，能否调用虚函数？why？
linux有哪些函数可用于线程同步？
结构中的位域问题。
不用锁，实现多线程中的链表节点删除。(一个写，多个读）
如何调试程？gdb中哪个命令查看调用栈，哪个命令设置断点
一个release版的程序崩溃了，如何定位问题所在？
看过什么技术类的经典书籍？
互联网公司(后台开发)
笔试： 计算机基础课程（网络，C++，UML，操作系统，基本数据结构，编译原理等）， 程序填空题
面试：
一面：
1. n!的二进制表示后面有多少个0
2. 讲出static函数,static变量的应用场合
3. 写一个洗牌算法
4. 估算广州有多少辆公交车
二面：
考官：你读通信的，熟悉TCP/IP？好，问几个问题：
Nagle算法你知道干什么的吗？他的实现原理是什么？
TCP协议实现中几个主要的定时器是什么？听过坚持定时器吗？干什么用的？
TCP为什么要有个TIME_WAIT状态？
TCP包头多少个字节? 分别是什么？
考官：考考你数据结构，B-树你知道吗?（给了一堆数据，好，你构造一个B-树）
考官：linux的IPC有多少种？ 用过system V的share memory函数吗？
给我讲讲socket API中的select
你的程序中，accept是阻塞还是非阻？阻塞的话，假如三次握手以后，对方发一个RST过来，你怎么处理？
非阻塞write的时候，当缓冲区满了，会返回什么错误？你是如何处理？
考官：你概率学得怎么样？（很多忘了，结果他就没再考）
二面问题（其他人提供）
两个超大文件分别储存了数亿个QQ号，请找出两个文件中相同的QQ号。
互联网公司
笔试：选择题（少量概率和推理，C++，设计模式等）
3道大题，系统设计。涉及海量访问和存储的架构设计
面试
一面：
1. 如何检测链表有环？如何找到进入环的第一个节点
2. sizeof问题
3. 写strncmp函数
4. 简历上的一些经历
二面：
问项目
三面：
1. linux下的IPC有哪几种
2. 讲讲epoll模型
3. 讲讲STL中的map和hashmap的原理和使用场合
4. 个人优缺点，工作意愿，个人性格等
互联网公司
一面：
1. 智力题。有3只白老鼠，7瓶药水，其中1瓶毒药，老鼠喝毒药后10min后立刻死亡，问用什么方法可以在10min之内找出有毒的药水是哪一瓶
2. 逆转单向链表
3. 求两个数组相同的最长子序列
select函数的作用，参数
setsockopt的作用，你用过哪些参数，他们的作用
SIGPIPE什么情况下产生？如何处理？
用过哪些设计模式？讲出singleton和observer模式，以及在你项目中的应用
类构造或析构函数中，能否调用虚函数？why？
linux有哪些函数可用于线程同步？
结构中的位域问题。
不用锁，实现多线程中的链表节点删除。(一个写，多个读）
如何调试程序？gdb中哪个命令查看调用栈，哪个命令设置断点
一个release版的程序崩溃了，如何定位问题所在？
看过什么技术类的经典书籍？