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

總體感覺題目還是比較簡單，主要考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