金山笔试题-金山毒霸系列的笔试题

总体感觉题目还是比较简单，主要考C++里面的东西，还有一些windows进程机制的题目，具体如下：

1.讲述const，static，extern的作用；

2.要你描述派生类的内存存储方式。

3.给你一个32位的六进制数，写一个程序让它倒序输出。

4.写一个冒泡或者选择排序的程序，并在讲述一个其余排序的程序，并讲述其特点。

5.从下面5个题目中选做一题或者多题：
（1）面向对象是什么意思，C++是如何实现的；
（2）多线程中的同步机制是什么，有什么优缺点？
（3）TCP与UDP有什么区别，分别有什么具体的应用协议？
（4）（不太记得了，好像是关于hook的）
（5）同步机制的考察题。

这次面试的笔试题分为WPS软件研发，毒霸研发以及游戏测试三个方向，WPS方向的题比较难，设计深入的C++编程问题，游戏测试全是简答题，如列举魔兽 世界的十大缺点 之类的，都很好回答，感觉就是金山的组织还是比较混乱，大家都一顿乱抢试卷，搞得场面很烂，而且就只有两个小mm在组织现场，呵呵！

笔试题-腾讯数据库笔试题：
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

腾讯笔试题解答(Peak Wong)：

　　1，把整数分成256M段，每段可以用64位整数保存该段数据个数，256M*8 = 2G内存，先清0

　　2，读10G整数，把整数映射到256M段中，增加相应段的记数

　　3，扫描256M段的记数，找到中位数的段和中位数的段前面所有段的记数，可以把其他段的内存释放

　　4，因中位数段的可能整数取值已经比较小(如果是32bit整数，当然如果是64bit整数的话，可以再次分段)，对每个整数做一个记数，再读一次10G整数，只读取中位数段对应的整数，并设置记数。

　　5，对新的记数扫描一次，即可找到中位数。

　　如果是32bit整数，读10G整数2次，扫描256M记数一次，后一次记数因数量很小，可以忽略不记。

　　解释一下：假设是32bit整数，按无符号整数处理

　　整数分成256M段? 整数范围是0 - 2^32 - 1 一共有4G种取值，4G/256M = 16，每16个数算一段 0-15是1段，16-31是一段，...

　　整数映射到256M段中? 如果整数是0-15，则增加第一段记数，如果整数是16-31，则增加第二段记数，...

　　其实可以不用分256M段，可以分的段数少一些，这样在扫描记数段时会快一些，还能节省一些内存。

Baidu面试笔试题 解答答案

一、选择题：15分 共10题
1. 在排序方法中，关键码比较次数与记录地初始排列无关的是 .
A. Shell排序 B. 归并排序 C. 直接插入排序 D. 选择排序

2. 以下多线程对int型变量x的操作，哪几个需要进行同步：
A. x=y; B. x    C.    x; D. x=1;

3. 代码
void func() {
static int val;
…
}
中，变量val的内存地址位于：
A. 已初始化数据段 B.未初始化数据段 C.堆 D.栈

4. 同一进程下的线程可以共享以下
A. stack B. data section
C. register set D. thread ID

5. TCP和IP分别对应了 OSI中的哪几层？
A. Application layer
B. Data link layer
C. Presentation layer
D. Physical layer
E. Transport layer
F. Session layer
G. Network layer

6. short a[100]，sizeof(a)返回？
A 2 B 4 C 100 D 200 E 400

7. 以下哪种不是基于组件的开发技术_____。
A XPCOM B XP C COM D CORBA

8. 以下代码打印的结果是（假设运行在i386系列计算机上）：
struct st_t
{
int status;
short* pdata;
char errstr[32];
};

st_t st[16];
char* p = (char*)(st[2].errstr    32);
printf("%d", (p - (char*)(st)));

A 32 B 114
C 120 D 1112

9. STL中的哪种结构是连续形式的存储
A map B set C list D vector

10. 一个栈的入栈序列是A，B，C，D，E，则栈的不可能的输出序列是（ ）
A、EDCBA； B、DECBA； C、DCEAB； D、ABCDE

二、简答题：20分，共2题

1. （5分）重复多次fclose一个打开过一次的FILE *fp指针会有什么结果，并请解释。

考察点：导致文件描述符结构中指针指向的内存被重复释放，进而导致一些不可预期的异
常。

2. （15分）下面一段代码，想在调用f2(1)时打印err1，调用f2(2)时打印err4，但是代码
中有一些问题，请做尽可能少的修改使之正确。

1 static int f1(const char *errstr, unsigned int flag) {
2 int copy, index, len;
3 const static char **__err = {“err1”, “err2”, “err3”, “err4”};
4
5 if(flag & 0x10000)
6 copy = 1;
7 index = (flag & 0x300000) >> 20;
8
9 if(copy) {
10 len = flag & 0xF;
11 errstr = malloc(len);
12 if(errstr = NULL)
13 return -1;
14 strncpy(errstr, __err[index], sizeof(errstr));
15 } else
16 errstr = __err    index;
17 }
18
19 void f2(int c) {
20 char *err;
21
22 swtch(c) {
23 case 1:
24 if(f1(err, 0x110004) != -1)
25 printf(err);
26 case 2:
27 if(f2(err, 0x30000D) != -1)
28 printf(err);
29 }
30 }

三、编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。

1. 求符合指定规则的数。
给定函数d(n) = n    n的各位之和，n为正整数，如 d(78) = 78 7 8=93。 这样这个函数
可以看成一个生成器，如93可以看成由78生成。
定义数A：数A找不到一个数B可以由d(B)=A，即A不能由其他数生成。现在要写程序，找出
1至10000里的所有符合数A定义的数。
输出：
1
3
…

四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或
者流程说明。

1. 假设一个mp3搜索引擎收录了2^24首歌曲，并记录了可收听这些歌曲的2^30条URL，但每
首歌的URL不超过2^10个。系统会定期检查这些URL，如果一个URL不可用则不出现在搜索结
果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求
：
1) 通过SONG_ID搜索一首歌的URL_ID，给出URL_ID计数和列表
2) 给定一个SONG_ID，为其添加一个新的URL_ID
3) 添加一个新的SONG_ID
4) 给定一个URL_ID，将其置为不可用

限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个
。

为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩
大，该如何多机分布处理？

第一题
   简评
   百度的主要业务是搜索，搜索的基本原理如下
　　1．编写爬虫程序到互联网上抓取网页海量的网页。
　　2．将抓取来的网页通过抽取，以一定的格式保存在能快速检索的文件系统中。
　　3．把用户输入的字符串进行拆分成关键字去文件系统中查询并返回结果。
　　由以上3点可见，字符串的分析，抽取在搜索引擎中的地位是何等重要。
　　因此，百度的笔试面试题中，出现这样的题就变得理所当然了。
import java.net.*;
import java.io.*;
import java.util.*;

/** * @author tzy * 在j2sdk1.4.2下测试通过 */

public class FileNameStat{
   private String srcPath;//要统计的文件路径
   private Map statMap;//用于统计的map
 
   public FileNameStat(String srcPath)
   {
     this.srcPath=srcPath;
     statMap=new TreeMap();
   }
 
   /*获得要统计的URL的文件名*/
   public String getFileName(String urlString)
   {
     URL url=null;
     String filePath=null;
     String fileName=null;
     try
     {
       url=new URL(urlString);
       filePath=url.getPath();
       int index=0;
       if ((index=filePath.lastIndexOf(\"/\"))!=-1)
       {
       fileName=filePath.substring(index+1);
       }
       else
       {
         fileName=\"\";
       }
     }
     catch(MalformedURLException e)
     {
     }
     return fileName;
   }
 
   /*统计指定文件名的个数*/
   public void stat(String filename)
   {
     Integer count=null;
     if(statMap.get(filename)!=null)
     {
       count=(Integer)statMap.get(filename);
       count=new Integer(count.intValue()+1);
     }
     else
     {
       count=new Integer(1);
     }
     statMap.put(filename,count);
   }
 
   /*统计的主方法*/
   public void start() throws FileNotFoundException,IOException
   {
     BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
     String temp=null;
     while((temp=bfin.readLine())!=null)
     {
       stat(getFileName(temp));
     }
   }
 
   /*输出统计结果*/
   public void result()
   {
     Iterator it=statMap.entrySet().iterator();
     while(it.hasNext())
     {
       Map.Entry entry=(Map.Entry)(it.next());
       System.out.println((entry.getKey().equals(\"\")?\"空文件名\":entry.getKey()) + \"的个数是\" + entry.getValue());
     }
   }
 
   public static void main(String[] args) throws Exception
   {
     FileNameStat fns=new FileNameStat(\"src.txt\");//指定成待统计文件
     fns.start();
     fns.result();
   }
}

　　第二题

　　简评：

　　这道题也与百度的业务有关，百度现在除了搜索外，还有贴吧，知道，博客等重要产品。　　同时也在积极的探索社区化，包括前不久宣布进军电子商务领域， 搜索之外的这些产品，其主要功能的实现主要是对数据库的操作。　　因此，想进入百度，也需要对数据库有一定的认识。 　　实现思路及数据库设计：　　1，该论坛主要有两个实体对象，用户和帖子;对于帖子对象，有一个问题：回复的帖子是否应该跟主题帖子存放在同一个表里?

　　考虑到每天更新10万帖子，说明帖子数比较多，为了方便主题的呈现，我一般都把主题贴和回帖分别放在不同的表中，把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。

　　2，按照1中的思路，该论坛由两个对象(用户和帖子)变成三个实体对象，分别是用户，主题帖子，回复帖子;

　　3，上述三个对象存在三个关系，分别是：

　　用户--主题帖，一个用户可以发0个或多个帖子，一个帖子对应一个用户(一对多关系)，

　　主题帖--回复帖：一个主题有0个或多个回复帖子，一个回复帖子对应一个主题(一对多关系);

　　用户--回复贴：一个用户可以回0个或多个帖，一个帖子对应一个用户(一对多关系)。

　　还存在对回复贴的回复，这个考虑用fatherId来表示。

　　4，由于三个关系 “用户--主题帖，主题帖--回复帖，用户--回复贴” 都是一对多关系，根据表设计一般原则，可以将这两个关系独立建立表，也可以不另外建表而将一对多的关系体现在实体表中;然而，表间的连接查询是非常耗资源 的，所以应尽量减少表间连接，那么对三个关系不应该分别建表，而是把用户的id作为主题表和回帖表的外键，把主题贴id作为回帖表的外键。

　　5，鉴于以上考虑，该论坛的三个表如下所示

　　表名：t_user_info (用户信息表)

字段名   类型   缺省值   中文含义   约束   备注 
id   Int     用户编号   PRI   Auto_increment
Name   Varchar(30)     用户名    
Email   Varchar(50)        
Phone   Varchar(30)          
Addr   Varchar(200)        

　　其他字段略，根据需要添加　　表名：main_content_info (主题帖信息表)

字段名   类型   缺省值   中文含义   约束   备注
id   Int     贴编号   PRI   Auto_increment
Title   Varchar(200)     发帖标题    
Content   Text     发帖内容    
UserID   Int     用户编号     外键

　　其他字段略，根据需要添加

　　表名：sub_content_info (回复贴信息表)

字段名 类型   缺省值   中文含义 约束   备注 
id   Int     贴编号   PRI   Auto_increment
Title   Varchar(200)     发帖标题    
Content   Text     发帖内容    
UserID   Int     用户编号     外键
FatherID   Int     父编号    
MainID   Int     主题帖编号     外键

　　其他字段略，根据需要添加

　　6，符合范式分析：

　　上述表中每个字段不可再分，首先满足1NF;

　　然后数据库表中的每个实例或行都是可以被惟一地区分(id)，不存在部分依赖，因此满足2NF;

　　t_user_info (用户信息表)和main_content_info (主题帖信息表)不存在任何传递依赖，至少属于BCNF;

　　但是sub_content_info (回复贴信息表)不满足3NF,因为存在如下传递依赖：id-->FatherID,FatherID-->MainID。

　　范式并不是越高越好，sub_content_info表只满足2NF却更有效率，也是当今论坛较主流的设计。

　　第三题

　　简评：

　　如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。　　因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。　　　思路及解决方案如下：

　　1: 设计用TRIE树实现关键词到其对应id的快速词典查找

　　TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点

　　节点定义如下：

struct trienode
{
   int   id;
   struct trienode *child[256];
}TRIENODE;

　　如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件B中的一个关键词，

　　在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷大的整数，标志从根节点

　　到当前节点的路径不是一个完整的关键词。

　　将关键词转化为二进制无符号char型数组，即对于汉字等双字节字符视为两个无符号char型整数，

　　每个元素的取值范围在0到255之间。

　　2：生成文件b的TRIE树

　　步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5

　　步骤2：读取关键词id和关键词，令为key

　　步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4;

　　步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;

　　步骤5：为当前节点的对应字符id置为关键词id

　　3：根据A文件生成C文件

　　步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5

　　步骤2：分别获取当前行关键词、ip地址和时间

　　步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4

　　步骤4：获取根节点的第c1个元素指针，转移到节点node1，

　　根据node1的第c2个元素指针，转移到node2...

　　根据nodem的第cm个元素，获取关键词的id

　　步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间

　　4：复杂度分析

　　生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。

　　生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大长度，因为有了TRIE树之后，给定一个关键词获得其id的时间 复杂度为关键词长度。生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)，由于系统有1G的可用内存，TRIE占用的 空间在几十兆到200M之间(与关键词集合有关)，因此本方法完全可行。

　2、八个人乘两只船：船1和船2，每只船只能且必须坐4人，8人中有3个大人：F、G、H，5个小孩：M、N、X、Y、Z。坐船的规则如下：
　　
　　 i. 每条船上至少有一个大人；如果F在船2，则G也分到船2；
　　
　　 ii.如果M分到船1，则N坐船2，X、Z必须分乘不同的船。
　　
　　a．下列哪组人员可以坐船1？（ ）
　　
　　 A． F、G、H、X B． F、H、N、Y
　　
　　 C． F、H、Y、 Z D． F、M、N、X
　　
　　b．如果F坐船2，下列哪一对可以坐在同一条船上？（ ）
　　
　　 A．F和Y B．G和Y C．M和N D．Y和Z
　　
　　c．如果船1上已经坐了3个小孩，下列哪一对可以坐到船2？（ ）
　　
　　 A．F和H B．G和Y C．H和N D．M和N
　　
　　
　　d．如果G在船1，下列哪个说法是正确的？（ ）
　　
　　 A．H坐船2 B．M坐船2
　　
　　 C．船1上有一个大人 D．船2上有2个大人
　　
　　e．如果M和N在一船上，下列哪一对也必须在一条船上？（ ）
　　
　　 A．F和H B．F和Y C．G和X D．N和X
　　
　　
　　f．如果H与Y乘坐不同的船，下列哪个必须在船1上？（ ）
　　
　　 A． F B． G C． H D． M
　　
　　g．如果船1上只有1个大人，下列哪个说法是正确的？（ ）
　　
　　 A．F在船1上 B．G在船2上
　　
　　 C．H在船2上 D．M在船1上

 from: http://blog.chinaunix.net/u2/76292/showart_1327403.html