题目
一、简答（30分）
1、extern “C”{}是什么含义？用来解决什么问题。（10分）
2、至少说出两种经典设计模式，并举例说明使用场景，有伪代码更加.(10分)
3、TCP连接的time_wait是什么状态，描述其发生的场景，说明它存在的好处坏处。（10分）
二、算法与程序设计（40分）
- 有一个任务执行器，每天需要定时执行很多任务（任务数N<1000）,任务执行器每次只能 执行一个任务而任务之间存在依赖关系，如A任务需要依赖于B任务完成后才能进行，虽然各 个任务之间依赖关系复杂但是各个任务之间却没有循环依赖的问题。给出一个合适的任务执行 顺序。请详细描述你的算法思路（如需要，可给出伪代码来辅助描述），并分析其时间和空间复杂度。（20分）
- 编写函数： 统计在某段英文文本完整句子的数目，文本只包括大小写英文字母、空格、点（.）、逗号（,）。 完整句子必须包含至少一个字母并以点结束。要求：请给出完整代码，在达到目标 的情况下尽量高效，简介。（20分）
三、系统设计题（30分）
某流量监控系统每天生成大量的数据记录，每条记录 包括url,访问IP,时间，这些数据记录需要进行存储和维护，并提供查询。请设计一个系统能够存储和维护1000亿条数据，实现实时监控，并能支持一下两种查询：
1.指定任意一个时间段（精确到分钟）和某个ip,查出该时段内该ip的总访问量。
2.指定任意一个时间段（精确到分钟）和某个url,查出该时段内对该url的总访问量。
参考思路
下面是当时笔试的一些思路，具体细节不太记得了。
- 很多地方都见到这道题，extern “c”是指将该段代码以C语言形式进行编译、链接。由于C不支持函数重载，C与C++对于同一函数进行编译后在符号表中保存的函数名存在差异，故当进行C、C++混编时会出现一些问题。
- 记得上学期还特意去借了一本《设计模式》书来看，翻是翻了几下，结果啥也没记住，这题直接空了。对于设计模式记得最深的一句就是“过分在意设计模式会阻碍你的创新思维”。
- 前段时间腾讯笔试时有道选择题也是考TCP的几个状态，当时做错了。回来后看了下TCP的连接和释放，这次还真用上了。time_wait是TCP释放四次握手中的一个状态，当第三次握手完成时，即客户端收到来自服务器的FIN后，再发送一个ACK，客户便开始了time_wait状态。同时一个记时器开始记时，当达到２倍一个报文段在因特网中最大的生存期时代表超时。如果在超时前客户端再次收到FIN，则表示是服务器重发的FIN，客户端需重发送ACK。
- 依题目得知是求有向图的一个拓扑序列。
- 直接扫描一遍。
int count_prefect_sentence(string str)
{
int i = 0, cnt = 0, hasOneLetter = 0;
while(str[i])
{
if(str[i] == '.')
{
if(hasOneLetter)
cnt++;
hasOneLetter = 0;
}
else if(isalpha(str[i]))
hasOneLetter = 1;
i++;
}
return cnt;
}
- 海量数据处理题，当时花了很长时间在想这两题，感觉没有想到什么好的思路。这样的系统应当是实时性优先吧，在时间空间上首先考虑时间。
- a. 建个二维映射Map[time].bitset，time代表某一时间点，将时间点表示为时间秒差数字作为映射索引。第二维考虑bitset的方式，建立一个2^32(整型的最大位数)的数组(bitset)，每一个bit位0或1代表该位上代表的IP整数是否访问过。 统计时枚举每个时间点，再按位和indexIP进行与运算进行统计，时间效率应该不差。以保存30天为例，空间为(30243600)*(2^32)bit = 2^50B= 1000TB = 1PB
- b. 时间以分钟为单位，第二维直接为IP，映射值为该分钟访问量。(302460)*(2^32)B= 2^50B = 1000TB = 1PB
- 映射Map[url][time]，将url进行字符串hash，再进行枚举统计。
这两题如果做成两维映射，内存吃不消，既然两题中的一维是已经指定的，变化的只是时间段，因此可以用一维表示，先预处理，再进行统计。