IT智力测试题3.doc

2011年校园招聘笔试题（一）
一：编程题
现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找不到输出-1。要求：
1，时间复杂度最优，能够在短时间内对大量输入逐个输出
2，实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。
3，给出时间复杂度和空间复杂度。
TERM组合集合的文件格式举例：
TERM_1 空格 TERM_2
TERM_1 空格 TERM_3
TERM_1 空格 TERM_3 TERM_4
输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）

二：算法题
你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是你知道一个整数M,这些记录满足R1<R2<...<RM以及RM+1<RM+2<...RN.
1,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2',<…<,RN',算法或程序读取文件的次数为O(N),不限内存使用，
2,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2'<...<RN',算法或程序读写文件的次数为O(N)，空间复杂度为O(1)，(亦即，你使用的内存大小和M,N均无关。)

三：系统设计题
网络上所有的链接都可以用以下的三元素进行描述：
From_url（链接所在页面的URL）
to_url（链接所指向的URL）
anchor（链接在页面上所显示的内容）
现在假设所有的网页链接信息（from_url \ to_url \anchor）按from_url为轴都存储在M个（M：1k以内）巨型数据库中：
1，链接存储形式：from_url to_url anchor；
2，一个from_url的所有的to_url都存储在同一个数据库中；
3，假设每个数据库存储的数据量相同
4，要求设计一个获取所有链接分发程序，将这些数据均匀分发到N个远程数据库中（N:100以内）要求做到：1所有to_url相同的链接需要分到同一个远程数据库，2所有to_url的站点相同的需要分发到同一个远程数据库，3每个远程数据库获取的链接总数要尽量均匀，4每台数据库完成时间尽量保持一致5，获取网页的速度尽量快（从数据库中）

　　百度笔试1.某服务器流量统计器，每天有1000亿的访问记录数据，包括时间、url、ip。设计系统实现记录数据的保存、管理、查询。要求能实现一下功能：

　　(1)计算在某一时间段(精确到分)时间内的，某url的所有访问量。

　　(2)计算在某一时间段(精确到分)时间内的，某ip的所有访问量。

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

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

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

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

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

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

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

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

二、填空题
1、http属于（应用层）协议，ICMP属于（网络层）协议

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

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

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

三、综合题
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
#define ALIGNBYTES(P，ALGNBYTES) ((P+ALGNBYTES-1)&~(ALGNBYTES-1))
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的作用是？
利用union的特性，看到cache_line_align的大小已经扩展到sizeof(erts_smp_rwmtx_t) 向上对齐了，这样寻址都是sizeof(long)的倍数地址上，寻址快，有利于下边数组erts_meta_main_tab_lock_t main_tab_lock[16];
的访问速度。

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

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

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

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

1. 网络编程经验：
如何判断一个http请求，一个客户端请求已经结束；如何处理服务器多线程
获得一个http请求后，是如何处理的？返回什么？有没有试过返回图片？
服务器给客户端请求时，是用什么函数写？服务器如何获取客户端请求，用什么函数
（需要函数级别的连接有一个认识）

2. pv操作是什么函数 pv_init, pv_wait, pv_signal

3. 有一些关键词点击次数的文件，如何输出最多点击的一百个（当时应该回答，组织一个
100个元素的最大堆）

4. 相交链表，如何找相交点（不能要标记）

5. 有些文件，频繁访问在磁盘里头的，现在要放到内存中了。采用什么策略来决定哪些放
到内存中？

6. c语言相关：内联函数的好处？非内联函数被调用的过程是怎么样的？
int,short,char的struct，这几个数应该怎么放，内存小？怎么防止头文件被include
多次？

7. 有没有什么问题想问的
8 linux 网络查看的命令

1. 介绍一个项目

2. 2.5亿个int数，可能有相同的。统计出这里头不同的数有多少个？只有2g内存。
（2.5*1000 000 000 * 4 =1GB）

3. 海量数据，在mysql中，cpu占用率很高。如何解决？
1.show processlist，看哪个sql查询的多，建索引（问：建立联合索引时，要考虑什么，
怎么建（哪个在前，哪个列在后？）
2.如果老是在拷贝到临时表，就改配置，把临时表内存改大些
3.还有什么方法：
1）分布式数据库 （问：如果你来设计分布式数据库，你会怎么设计？）
2）使用缓存 （问：如果缓存中的数据，被删除或跟新了，数据库怎么判断这个缓存的
数据不能用了，是脏数据？）（不懂）
问：什么情况下cpu会高？（内存不足）为什么内存不足cpu会高（频繁io读写）

4. n个无序int，（有正有负），给一个数v，如何找出其中的a+b=v的两个数

5. 网络相册，一个人可以有多个相册，一个相册有多个图片，如何快速实现增删查移动等
操作。web页面上，图片是翻页显示。

第五题我想不出好办法，我觉得一般他们都show thumbnail
就是预览小图片不把原始图片show在页面上，点击后才能看单个图片

6. Unix系统里，一个简单的print hello world的c程序，从./a.out执行到屏幕打印出来
这句话，是什么过程
问：哪个进程来调用的main？（不知道）

7. socket编程，要注意什么问题

1,void remove（node *p）
从单链表中删除节点P，不知首节点，补全代码
2.char * strcpy（…）写！
3.从10亿个64位整数中，找出不重复的数，写代码
4.从1亿个32位整数中，找第K大的数。
5.设计系统。ID与名字一一对应，叫你设计系统，以便通过ID快速查询名字以及增删。
1000万个ID，ID唯一。

面试：
1.介绍了其中一个项目。
2.说了个题叫你给思路。
两个无序数组，让你合并相同的项到第三个数组。
再深入问，假如数组很大，内存放不下，如何做？
3.问了C/C++ ，static 用法
4.有无socket程序经验。

总结：腾讯喜欢考/问大数据量的题
考官对socket方向，较感兴趣，问你这方面经验如何

面试例题1：100美元哪里去了？

3个朋友住进了一家宾馆。结账时，账单总计3 000美元。3个朋友每人分摊1 000美元，并把这3 000美元如数交给了服务员，委托他代到总台交账。但在交账时，正逢宾馆实施价格优惠，总台退还给服务员500美元，实收2 500美元。服务员从这500美元退款中扣下了200美元，只退还3个客人300美元。3个客人平分了这300美元，每人取回了100美元。这样，3个客人每人实际支付900美元，共支付2 700美元，加上服务员扣的200美元，共计2 900美元，那么这100美元的差额到哪里去了？

答案：这道题纯粹是文字游戏，但是如果你的头脑不够清晰，很可能把你搞糊涂了。客人实际支付2 700美元，就等于总台实际结收的2 500美元加上服务员克扣的200美元。在这2 700美元上加上200美元是毫无道理的，而在这2 700美元上加退回的300美元，这是有道理的，因为这等于客人原先交给服务员的3 000美元。

面试例题2：击鼠标比赛现在开始！参赛者有拉尔夫、威利和保罗。

拉尔夫10秒钟能击10下鼠标，威利20秒钟能击20下鼠标，保罗5秒钟能击5下鼠标。以上各人所用的时间是这样计算的：从第一击开始，到最后一击结束。

他们是否打平手？如果不是，谁最先击完40下鼠标？

解析：n秒钟击n下鼠标其实是击第一下鼠标时才开始计时的，实际上击n-1下需要n秒钟，那么若击40下鼠标，拉尔夫需要 (40-1)/(9/10)=39/0.9秒，威利需要(40-1)/(19/20)=39/0.95秒，保罗需要(40-1)/(4/5)=39 /0.8秒，因此威利先击完。

答案：威利先击完。

面试例题3：父亲打电话给女儿，要她替自己买一些生活用品，同时告诉她，钱放在书桌上的一个信封里。女儿找到信封，看见上面写着98，以为信封内有98元，就把钱拿出来，数也没数放进书包里。在商店里，她买了90元的东西，付款时才发现，她不仅没有剩下8 元，反而差了4元。回到家里，她把这事告诉了父亲，怀疑父亲把钱点错了。父亲笑着说，他并没有数错，错在女儿身上。

问：女儿错在什么地方？

答案：拿倒了，86看成是98了。

面试例题4：3个孩子翻衣兜，他们把兜里所有的钱都掏出来，看看一共有多少钱。结果一共有320日元。其中有两枚硬币是100日元的，两枚是50日元的，两枚是10日元的。每一个孩子所带的硬币中没有相同的。而且，没带100日元硬币的孩子也没带10日元的硬币，没带50日元硬币的孩子也没带100日元的硬币。你能弄清楚这3个日本孩子原来各自带了什么硬币吗？

答案：第一个小孩：100，50，10；第二个小孩：100，50；第三个小孩：10。

面试例题5：有一种小虫，每隔2秒钟分裂一次。分裂后的2只新的小虫经过2秒钟后又会分裂。如果最初某瓶中只有一只小虫，那么2秒后变2只，再过2秒后就变4只……2分钟后，正好满满一瓶小虫。假设这个瓶内最初放入2只这样的小虫。

问：经过多少时间后，正巧也是满满的一瓶？

答案：经过1分58秒时间，也正巧是满满一瓶。因为从一只虫蜕变为2只虫只需2秒钟。在瓶内只有一只虫子的情况下，经过2秒钟后就变成2 只。这时的情况和瓶内一开始就有2只虫子的情况是一样的。出现这两种情况的时间差是2秒钟。所以，经过1分58秒后，也正好是满满一瓶。

面试例题6：斯芬克斯是古代希腊神话中的带翅膀的狮子女魔。传说她在底比斯附近要人猜谜，猜不出来就要杀人。一次，她要底比斯王子猜谜：“有一种动物，早上4条腿，中午2条腿，晚上3条腿，是什么动物？”聪明的王子说：“是人。”他猜中了。

如果你是现代的斯芬克斯，会提出什么样的问题呢？比如，1和0之间加上什么符号才可以使得到的数比0大又比1小呢？你知道吗？

答案：0.1

面试智力题集锦

第一部分 反应能力 2
第二部分 分析能力 4
第三部分 6
第五部分 6
第六部分 12
第七部分 15