金山筆試題-金山毒霸系列的筆試題

總體感覺(jué)題目還是比較簡(jiǎn)單，主要考C++里面的東西，還有一些windows進(jìn)程機(jī)制的題目，具體如下：

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

2.要你描述派生類(lèi)的內(nèi)存存儲(chǔ)方式。

3.給你一個(gè)32位的六進(jìn)制數(shù)，寫(xiě)一個(gè)程序讓它倒序輸出。

4.寫(xiě)一個(gè)冒泡或者選擇排序的程序，并在講述一個(gè)其余排序的程序，并講述其特點(diǎn)。

5.從下面5個(gè)題目中選做一題或者多題：
（1）面向?qū)ο笫鞘裁匆馑迹珻++是如何實(shí)現(xiàn)的；
（2）多線(xiàn)程中的同步機(jī)制是什么，有什么優(yōu)缺點(diǎn)？
（3）TCP與UDP有什么區(qū)別，分別有什么具體的應(yīng)用協(xié)議？
（4）（不太記得了，好像是關(guān)于hook的）
（5）同步機(jī)制的考察題。

這次面試的筆試題分為WPS軟件研發(fā)，毒霸研發(fā)以及游戲測(cè)試三個(gè)方向，WPS方向的題比較難，設(shè)計(jì)深入的C++編程問(wèn)題，游戲測(cè)試全是簡(jiǎn)答題，如列舉魔獸 世界的十大缺點(diǎn) 之類(lèi)的，都很好回答，感覺(jué)就是金山的組織還是比較混亂，大家都一頓亂搶試卷，搞得場(chǎng)面很爛，而且就只有兩個(gè)小mm在組織現(xiàn)場(chǎng)，呵呵！

筆試題-騰訊數(shù)據(jù)庫(kù)筆試題：
在一個(gè)文件中有 10G 個(gè)整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。只寫(xiě)出思路即可。

騰訊筆試題解答(Peak Wong)：

　　1，把整數(shù)分成256M段，每段可以用64位整數(shù)保存該段數(shù)據(jù)個(gè)數(shù)，256M*8 = 2G內(nèi)存，先清0

　　2，讀10G整數(shù)，把整數(shù)映射到256M段中，增加相應(yīng)段的記數(shù)

　　3，掃描256M段的記數(shù)，找到中位數(shù)的段和中位數(shù)的段前面所有段的記數(shù)，可以把其他段的內(nèi)存釋放

　　4，因中位數(shù)段的可能整數(shù)取值已經(jīng)比較小(如果是32bit整數(shù)，當(dāng)然如果是64bit整數(shù)的話(huà)，可以再次分段)，對(duì)每個(gè)整數(shù)做一個(gè)記數(shù)，再讀一次10G整數(shù)，只讀取中位數(shù)段對(duì)應(yīng)的整數(shù)，并設(shè)置記數(shù)。

　　5，對(duì)新的記數(shù)掃描一次，即可找到中位數(shù)。

　　如果是32bit整數(shù)，讀10G整數(shù)2次，掃描256M記數(shù)一次，后一次記數(shù)因數(shù)量很小，可以忽略不記。

　　解釋一下：假設(shè)是32bit整數(shù)，按無(wú)符號(hào)整數(shù)處理

　　整數(shù)分成256M段? 整數(shù)范圍是0 - 2^32 - 1 一共有4G種取值，4G/256M = 16，每16個(gè)數(shù)算一段 0-15是1段，16-31是一段，...

　　整數(shù)映射到256M段中? 如果整數(shù)是0-15，則增加第一段記數(shù)，如果整數(shù)是16-31，則增加第二段記數(shù)，...

　　其實(shí)可以不用分256M段，可以分的段數(shù)少一些，這樣在掃描記數(shù)段時(shí)會(huì)快一些，還能節(jié)省一些內(nèi)存。

Baidu面試筆試題 解答答案

一、選擇題：15分 共10題
1. 在排序方法中，關(guān)鍵碼比較次數(shù)與記錄地初始排列無(wú)關(guān)的是 .
A. Shell排序 B. 歸并排序 C. 直接插入排序 D. 選擇排序

2. 以下多線(xiàn)程對(duì)int型變量x的操作，哪幾個(gè)需要進(jìn)行同步：
A. x=y; B. x    C.    x; D. x=1;

3. 代碼
void func() {
static int val;
…
}
中，變量val的內(nèi)存地址位于：
A. 已初始化數(shù)據(jù)段 B.未初始化數(shù)據(jù)段 C.堆 D.棧

4. 同一進(jìn)程下的線(xiàn)程可以共享以下
A. stack B. data section
C. register set D. thread ID

5. TCP和IP分別對(duì)應(yīng)了 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. 以下哪種不是基于組件的開(kāi)發(fā)技術(shù)_____。
A XPCOM B XP C COM D CORBA

8. 以下代碼打印的結(jié)果是（假設(shè)運(yùn)行在i386系列計(jì)算機(jī)上）：
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中的哪種結(jié)構(gòu)是連續(xù)形式的存儲(chǔ)
A map B set C list D vector

10. 一個(gè)棧的入棧序列是A，B，C，D，E，則棧的不可能的輸出序列是（ ）
A、EDCBA； B、DECBA； C、DCEAB； D、ABCDE

二、簡(jiǎn)答題：20分，共2題

1. （5分）重復(fù)多次fclose一個(gè)打開(kāi)過(guò)一次的FILE *fp指針會(huì)有什么結(jié)果，并請(qǐng)解釋。

考察點(diǎn)：導(dǎo)致文件描述符結(jié)構(gòu)中指針指向的內(nèi)存被重復(fù)釋放，進(jìn)而導(dǎo)致一些不可預(yù)期的異
常。

2. （15分）下面一段代碼，想在調(diào)用f2(1)時(shí)打印err1，調(diào)用f2(2)時(shí)打印err4，但是代碼
中有一些問(wèn)題，請(qǐng)做盡可能少的修改使之正確。

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題
注意：要求提供完整代碼，如果可以編譯運(yùn)行酌情加分。

1. 求符合指定規(guī)則的數(shù)。
給定函數(shù)d(n) = n    n的各位之和，n為正整數(shù)，如 d(78) = 78 7 8=93。 這樣這個(gè)函數(shù)
可以看成一個(gè)生成器，如93可以看成由78生成。
定義數(shù)A：數(shù)A找不到一個(gè)數(shù)B可以由d(B)=A，即A不能由其他數(shù)生成。現(xiàn)在要寫(xiě)程序，找出
1至10000里的所有符合數(shù)A定義的數(shù)。
輸出：
1
3
…

四、設(shè)計(jì)題：35分 共1題
注意：請(qǐng)盡可能詳細(xì)描述你的數(shù)據(jù)結(jié)構(gòu)、系統(tǒng)架構(gòu)、設(shè)計(jì)思路等。建議多寫(xiě)一些偽代碼或
者流程說(shuō)明。

1. 假設(shè)一個(gè)mp3搜索引擎收錄了2^24首歌曲，并記錄了可收聽(tīng)這些歌曲的2^30條URL，但每
首歌的URL不超過(guò)2^10個(gè)。系統(tǒng)會(huì)定期檢查這些URL，如果一個(gè)URL不可用則不出現(xiàn)在搜索結(jié)
果中。現(xiàn)在歌曲名和URL分別通過(guò)整型的SONG_ID和URL_ID唯一確定。對(duì)該系統(tǒng)有如下需求
：
1) 通過(guò)SONG_ID搜索一首歌的URL_ID，給出URL_ID計(jì)數(shù)和列表
2) 給定一個(gè)SONG_ID，為其添加一個(gè)新的URL_ID
3) 添加一個(gè)新的SONG_ID
4) 給定一個(gè)URL_ID，將其置為不可用

限制條件：內(nèi)存占用不超過(guò)1G，單個(gè)文件大小不超過(guò)2G，一個(gè)目錄下的文件數(shù)不超過(guò)128個(gè)
。

為獲得最佳性能，請(qǐng)說(shuō)明設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)、搜索算法，以及資源消耗。如果系統(tǒng)數(shù)據(jù)量擴(kuò)
大，該如何多機(jī)分布處理？

第一題
   簡(jiǎn)評(píng)
   百度的主要業(yè)務(wù)是搜索，搜索的基本原理如下
　　1．編寫(xiě)爬蟲(chóng)程序到互聯(lián)網(wǎng)上抓取網(wǎng)頁(yè)海量的網(wǎng)頁(yè)。
　　2．將抓取來(lái)的網(wǎng)頁(yè)通過(guò)抽取，以一定的格式保存在能快速檢索的文件系統(tǒng)中。
　　3．把用戶(hù)輸入的字符串進(jìn)行拆分成關(guān)鍵字去文件系統(tǒng)中查詢(xún)并返回結(jié)果。
　　由以上3點(diǎn)可見(jiàn)，字符串的分析，抽取在搜索引擎中的地位是何等重要。
　　因此，百度的筆試面試題中，出現(xiàn)這樣的題就變得理所當(dāng)然了。
import java.net.*;
import java.io.*;
import java.util.*;

/** * @author tzy * 在j2sdk1.4.2下測(cè)試通過(guò) */

public class FileNameStat{
   private String srcPath;//要統(tǒng)計(jì)的文件路徑
   private Map statMap;//用于統(tǒng)計(jì)的map
 
   public FileNameStat(String srcPath)
   {
     this.srcPath=srcPath;
     statMap=new TreeMap();
   }
 
   /*獲得要統(tǒng)計(jì)的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;
   }
 
   /*統(tǒng)計(jì)指定文件名的個(gè)數(shù)*/
   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);
   }
 
   /*統(tǒng)計(jì)的主方法*/
   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));
     }
   }
 
   /*輸出統(tǒng)計(jì)結(jié)果*/
   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()) + \"的個(gè)數(shù)是\" + entry.getValue());
     }
   }
 
   public static void main(String[] args) throws Exception
   {
     FileNameStat fns=new FileNameStat(\"src.txt\");//指定成待統(tǒng)計(jì)文件
     fns.start();
     fns.result();
   }
}

　　第二題

　　簡(jiǎn)評(píng)：

　　這道題也與百度的業(yè)務(wù)有關(guān)，百度現(xiàn)在除了搜索外，還有貼吧，知道，博客等重要產(chǎn)品。　　同時(shí)也在積極的探索社區(qū)化，包括前不久宣布進(jìn)軍電子商務(wù)領(lǐng)域， 搜索之外的這些產(chǎn)品，其主要功能的實(shí)現(xiàn)主要是對(duì)數(shù)據(jù)庫(kù)的操作。　　因此，想進(jìn)入百度，也需要對(duì)數(shù)據(jù)庫(kù)有一定的認(rèn)識(shí)。 　　實(shí)現(xiàn)思路及數(shù)據(jù)庫(kù)設(shè)計(jì)：　　1，該論壇主要有兩個(gè)實(shí)體對(duì)象，用戶(hù)和帖子;對(duì)于帖子對(duì)象，有一個(gè)問(wèn)題：回復(fù)的帖子是否應(yīng)該跟主題帖子存放在同一個(gè)表里?

　　考慮到每天更新10萬(wàn)帖子，說(shuō)明帖子數(shù)比較多，為了方便主題的呈現(xiàn)，我一般都把主題貼和回帖分別放在不同的表中，把主題貼和回帖分開(kāi)可以提高查詢(xún)效率(300萬(wàn)的訪(fǎng)問(wèn)量每天)。

　　2，按照1中的思路，該論壇由兩個(gè)對(duì)象(用戶(hù)和帖子)變成三個(gè)實(shí)體對(duì)象，分別是用戶(hù)，主題帖子，回復(fù)帖子;

　　3，上述三個(gè)對(duì)象存在三個(gè)關(guān)系，分別是：

　　用戶(hù)--主題帖，一個(gè)用戶(hù)可以發(fā)0個(gè)或多個(gè)帖子，一個(gè)帖子對(duì)應(yīng)一個(gè)用戶(hù)(一對(duì)多關(guān)系)，

　　主題帖--回復(fù)帖：一個(gè)主題有0個(gè)或多個(gè)回復(fù)帖子，一個(gè)回復(fù)帖子對(duì)應(yīng)一個(gè)主題(一對(duì)多關(guān)系);

　　用戶(hù)--回復(fù)貼：一個(gè)用戶(hù)可以回0個(gè)或多個(gè)帖，一個(gè)帖子對(duì)應(yīng)一個(gè)用戶(hù)(一對(duì)多關(guān)系)。

　　還存在對(duì)回復(fù)貼的回復(fù)，這個(gè)考慮用fatherId來(lái)表示。

　　4，由于三個(gè)關(guān)系 “用戶(hù)--主題帖，主題帖--回復(fù)帖，用戶(hù)--回復(fù)貼” 都是一對(duì)多關(guān)系，根據(jù)表設(shè)計(jì)一般原則，可以將這兩個(gè)關(guān)系獨(dú)立建立表，也可以不另外建表而將一對(duì)多的關(guān)系體現(xiàn)在實(shí)體表中;然而，表間的連接查詢(xún)是非常耗資源 的，所以應(yīng)盡量減少表間連接，那么對(duì)三個(gè)關(guān)系不應(yīng)該分別建表，而是把用戶(hù)的id作為主題表和回帖表的外鍵，把主題貼id作為回帖表的外鍵。

　　5，鑒于以上考慮，該論壇的三個(gè)表如下所示

　　表名：t_user_info (用戶(hù)信息表)

字段名   類(lèi)型   缺省值   中文含義   約束   備注 
id   Int     用戶(hù)編號(hào)   PRI   Auto_increment
Name   Varchar(30)     用戶(hù)名    
Email   Varchar(50)        
Phone   Varchar(30)          
Addr   Varchar(200)        

　　其他字段略，根據(jù)需要添加　　表名：main_content_info (主題帖信息表)

字段名   類(lèi)型   缺省值   中文含義   約束   備注
id   Int     貼編號(hào)   PRI   Auto_increment
Title   Varchar(200)     發(fā)帖標(biāo)題    
Content   Text     發(fā)帖內(nèi)容    
UserID   Int     用戶(hù)編號(hào)     外鍵

　　其他字段略，根據(jù)需要添加

　　表名：sub_content_info (回復(fù)貼信息表)

字段名 類(lèi)型   缺省值   中文含義 約束   備注 
id   Int     貼編號(hào)   PRI   Auto_increment
Title   Varchar(200)     發(fā)帖標(biāo)題    
Content   Text     發(fā)帖內(nèi)容    
UserID   Int     用戶(hù)編號(hào)     外鍵
FatherID   Int     父編號(hào)    
MainID   Int     主題帖編號(hào)     外鍵

　　其他字段略，根據(jù)需要添加

　　6，符合范式分析：

　　上述表中每個(gè)字段不可再分，首先滿(mǎn)足1NF;

　　然后數(shù)據(jù)庫(kù)表中的每個(gè)實(shí)例或行都是可以被惟一地區(qū)分(id)，不存在部分依賴(lài)，因此滿(mǎn)足2NF;

　　t_user_info (用戶(hù)信息表)和main_content_info (主題帖信息表)不存在任何傳遞依賴(lài)，至少屬于BCNF;

　　但是sub_content_info (回復(fù)貼信息表)不滿(mǎn)足3NF,因?yàn)榇嬖谌缦聜鬟f依賴(lài)：id-->FatherID,FatherID-->MainID。

　　范式并不是越高越好，sub_content_info表只滿(mǎn)足2NF卻更有效率，也是當(dāng)今論壇較主流的設(shè)計(jì)。

　　第三題

　　簡(jiǎn)評(píng)：

　　如何對(duì)海量數(shù)據(jù)進(jìn)行快速檢索，這是搜索引擎的必需考慮的問(wèn)題。這又涉及到數(shù)據(jù)結(jié)構(gòu)和算法。　　因此，要想進(jìn)入百度，就必須熟悉一些基本的算法和數(shù)據(jù)結(jié)構(gòu)。　　　思路及解決方案如下：

　　1: 設(shè)計(jì)用TRIE樹(shù)實(shí)現(xiàn)關(guān)鍵詞到其對(duì)應(yīng)id的快速詞典查找

　　TRIE樹(shù)的每一個(gè)節(jié)點(diǎn)為一個(gè)包含256個(gè)元素的數(shù)組，同時(shí)指針指向其下一級(jí)節(jié)點(diǎn)

　　節(jié)點(diǎn)定義如下：

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

　　如果TRIE樹(shù)的某個(gè)節(jié)點(diǎn)的指針為NULL，說(shuō)明從跟節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑構(gòu)成文件B中的一個(gè)關(guān)鍵詞，

　　在其節(jié)點(diǎn)的id保存該關(guān)鍵詞的id;如果指針不為NULL，則id對(duì)應(yīng)為0或者一個(gè)無(wú)窮大的整數(shù)，標(biāo)志從根節(jié)點(diǎn)

　　到當(dāng)前節(jié)點(diǎn)的路徑不是一個(gè)完整的關(guān)鍵詞。

　　將關(guān)鍵詞轉(zhuǎn)化為二進(jìn)制無(wú)符號(hào)char型數(shù)組，即對(duì)于漢字等雙字節(jié)字符視為兩個(gè)無(wú)符號(hào)char型整數(shù)，

　　每個(gè)元素的取值范圍在0到255之間。

　　2：生成文件b的TRIE樹(shù)

　　步驟1：依次讀取文件b的每一行，對(duì)每一行執(zhí)行步驟2到步驟5

　　步驟2：讀取關(guān)鍵詞id和關(guān)鍵詞，令為key

　　步驟3：依次讀取key的每一個(gè)字符，對(duì)每一個(gè)字符，執(zhí)行步驟4;

　　步驟4：如果該字符對(duì)應(yīng)的指針為NULL，則創(chuàng)建其兒子節(jié)點(diǎn);

　　步驟5：為當(dāng)前節(jié)點(diǎn)的對(duì)應(yīng)字符id置為關(guān)鍵詞id

　　3：根據(jù)A文件生成C文件

　　步驟1：依次讀取文件A的每一行，對(duì)每一行執(zhí)行步驟2到步驟5

　　步驟2：分別獲取當(dāng)前行關(guān)鍵詞、ip地址和時(shí)間

　　步驟3：令關(guān)鍵詞key=c1c2...cm，對(duì)c1到cm每個(gè)字符，執(zhí)行步驟4

　　步驟4：獲取根節(jié)點(diǎn)的第c1個(gè)元素指針，轉(zhuǎn)移到節(jié)點(diǎn)node1，

　　根據(jù)node1的第c2個(gè)元素指針，轉(zhuǎn)移到node2...

　　根據(jù)nodem的第cm個(gè)元素，獲取關(guān)鍵詞的id

　　步驟5：往文件c中寫(xiě)入一行數(shù)據(jù)，格式為關(guān)鍵詞的id、ip地址和時(shí)間

　　4：復(fù)雜度分析

　　生成文件B的TRIE樹(shù)過(guò)程時(shí)間復(fù)雜度為O(n*m)，其中n為文件b行數(shù)，m為文件b關(guān)鍵詞的最大長(zhǎng)度。TRIE的空間復(fù)雜度為O(n*m)，n和m含義同上，但由于實(shí)際應(yīng)用中關(guān)鍵詞之間可能會(huì)有很多前綴相同現(xiàn)象，所以實(shí)際耗費(fèi)空間并不會(huì)很高。

　　生成C文件的時(shí)間復(fù)雜度同樣為O(n*m)，n為文件a行數(shù)，m為文件a關(guān)鍵詞的最大長(zhǎng)度，因?yàn)橛辛薚RIE樹(shù)之后，給定一個(gè)關(guān)鍵詞獲得其id的時(shí)間 復(fù)雜度為關(guān)鍵詞長(zhǎng)度。生成C文件的過(guò)程除了TRIE樹(shù)空間外基本不需要太多額外的空間，空間復(fù)雜度為O(1)，由于系統(tǒng)有1G的可用內(nèi)存，TRIE占用的 空間在幾十兆到200M之間(與關(guān)鍵詞集合有關(guān))，因此本方法完全可行。

　2、八個(gè)人乘兩只船：船1和船2，每只船只能且必須坐4人，8人中有3個(gè)大人：F、G、H，5個(gè)小孩：M、N、X、Y、Z。坐船的規(guī)則如下：
　　
　　 i. 每條船上至少有一個(gè)大人；如果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，下列哪一對(duì)可以坐在同一條船上？（ ）
　　
　　 A．F和Y B．G和Y C．M和N D．Y和Z
　　
　　c．如果船1上已經(jīng)坐了3個(gè)小孩，下列哪一對(duì)可以坐到船2？（ ）
　　
　　 A．F和H B．G和Y C．H和N D．M和N
　　
　　
　　d．如果G在船1，下列哪個(gè)說(shuō)法是正確的？（ ）
　　
　　 A．H坐船2 B．M坐船2
　　
　　 C．船1上有一個(gè)大人 D．船2上有2個(gè)大人
　　
　　e．如果M和N在一船上，下列哪一對(duì)也必須在一條船上？（ ）
　　
　　 A．F和H B．F和Y C．G和X D．N和X
　　
　　
　　f．如果H與Y乘坐不同的船，下列哪個(gè)必須在船1上？（ ）
　　
　　 A． F B． G C． H D． M
　　
　　g．如果船1上只有1個(gè)大人，下列哪個(gè)說(shuō)法是正確的？（ ）
　　
　　 A．F在船1上 B．G在船2上
　　
　　 C．H在船2上 D．M在船1上

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