面试题库

一、单选题
1、我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分（）
a 5瓶 b 6 c 31 d 32

2、若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间？
A 单链表 B 带头结点的非循环双链表 C 带头节点的双循环链表  D 循环链表

3、如果需要对磁盘上的1000W条记录构建索引，你认为下面哪种数据结构来存储索引最合适？（）
A Hash Table  B. AVL-Tree  C. B-Tree  D. List

4、可用来检测一个web服务器是否正常工作的命令是（）
A ping B tracert  C. telnet  D. ftp

5、下面哪个操作是Windows独有的I/O技术（）
A. Select  B.Poll  C.IOCP  D. Epoll

6、IPV6地址包含了（）位
A. 16  B. 32  C. 64   D.128

7、数据库里建索引常用的数据结构是（）
A 链表   B队列  C 树   D 哈希表

8、在公司局域网上ping www.taobao.com没有涉及到的网络协议是（）
A. ARP        B. DNS    C. TCP       D. ICMP

二、填空题
1、http属于（）协议，ICMP属于（）协议

2、深度为k的完全二叉树至少有（）个结点，至多有（）个结点

3、字节为6位的二进制有符号整数，其最小值是（）

4、设有28盏灯，拟公用一个电源，则至少需有4插头的接线板数（）个。

三、综合题
1、有一颗结构如下的树，对其做镜像反转后如下，请写出能实现该功能的代码。注意：请勿对该树做任何假设，它不一定是平衡树，也不一定有序。
        1                                                1
      /  | \                                          /  |  \
     2   3  4                                        4   3   2
    /|\  /\  |                                       |  / \ / | \
   6 5 7 8 9 10                                     10 9  8 7 5 6
 
2、假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？

四、附加题
1、写出C语言的地址对齐宏ALIGN（PALGNBYTES），其中P是要对齐的地址，ALIGNBYTES是要对齐的字节数（2的N次方），比如说：ALIGN(13,16)=16

2、在高性能服务器的代码中经常会看到类似这样的代码：
typedef union
{
  erts_smp_rwmtx_t rwmtx;
  byte cache_line_align_[ERTS_ALC_CACHE_LINE_ALIGN_SIZE(sizeof(erts_smp_rwmtx_t))];
}erts_meta_main_tab_lock_t;

erts_meta_main_tab_lock_t main_tab_lock[16];

请问其中用来填充的cache_line_align的作用是？

3、在现代web服务系统的设计中，为了减轻源站的压力，通常采用分布式缓存技术，其原理如下图所示，前端的分配器将针对不同内容的用户请求分配给不同的缓存服务器向用户提供服务。
                                   分配器
                                /    |      \
                              缓存  缓存 ...缓存
                             服务器1 服务器2 ...服务器n

1）请问如何设置分配策略，可以保证充分利用每个缓存服务器的存储空间（每个内容只在一个缓存服务器有副本）

2）当部分缓存服务器故障，或是因为系统扩容，导致缓存服务器的数量动态减少或增加时，你的分配策略是否可以保证较小的缓存文件重分配的开销，如果不能，如何改进？

3）当各个缓存服务器的存储空间存在差异时（如有4个缓存服务器，存储空间比为4：9：15：7），如何改进你的策略，按照如上的比例将内容调度到缓存服务器？

一、简答
1、系统有很多任务，任务之间有依赖，比如B依赖于A，则A执行完后B才能执行
（1）不考虑系统并行性，设计一个函数（Task Ptask,int Task_num）不考虑并行度，最快的方法完成所有任务。
（2）考虑并行度，怎么设计
typedef struct{
int ID;
int * child;
int child_num;
}Task;
提供的函数:
bool doTask(int taskID);无阻塞的运行一个任务；
int waitTask(int timeout);返回运行完成的任务id，如果没有则返回-1；
bool killTask(int taskID);杀死进程
2、堆和栈的生命周期，内存分配性能，不同处，如果一般情况下要求1KB，偶尔需要100MB的缓存空间怎么设计？
二、必答题（各种const）
1、解释下面ptr含义和不同（好像是。。。。题干了大概意思是这样。下面应该没错）
double prt = &value
const double* ptr = &value
double* const ptr=&value
const double* const ptr=&value
2、去掉const属性，例：
const double value = 0.0f;
double* ptr = NULL;
怎么才能让ptr指向value？
三、算法设计
1、一个一维数轴上有不同的线段，求重复最长的两个线段。
例：a：13
b: 27
c：2~8
最长重复是b和c
2、有向带权图最短路径
四、系统设计
大概意思是：百度内部有一个类似cs系统的计算系统，由于大并发计算很耗资源，所有要设计一个缓存系统。c做缓存，配置2.66MHZ,3G内存，大概有1000w个查询，唯一的查询大概有500w。要缓存24小时。设计这个缓存系统的运行机制，算法等等东西。。。。。记不太清了。。。