面試ack

A. 尋求文思和華為關於軟體工程師的面試題目

華為從事通信網路技術與產品的研究、開發、生產與銷售，是中國電信市場的主要供應商之一，並已成功進入全球電信市場。每年華為都要在各大高校招聘大批的應界生，特別是華中科技大學。公司網址是：http://www.huawei.com
下面據說是華為公司的筆試題，其實我想它一次筆試不可能出這么多題，也許是多年筆試題的合集，或者也包括了其他公司的筆試內容。最近國際商用工程集團（http://www.ibegroup.com/）的網管告訴我這是他們的題目，是網上以訛傳訛的說成是華為的題目了，我想應該是這樣的，畢竟題目中赫然出現了他們公司的網址呢（見題2），希望大家轉貼的時候也能寫上這段聲明。
另外我發現白雲黃鶴有人不聲不響的貼出我做的答案，還沒有聲明出處，俺很嚴肅的告訴他，俺很生氣angry，後果很嚴重。
個人答案，僅供參考。呵呵，不過保證絕大多數答案的准確性。
1.寫出判斷ABCD四個表達式的是否正確, 若正確, 寫出經過表達式中 a的值(3分)
int a = 4;
(A)a += (a++); (B) a += (++a) ;(C) (a++) += a;(D) (++a) += (a++);
a = ?
答：C錯誤，左側不是一個有效變數，不能賦值，可改為(++a) += a;
改後答案依次為9,10,10,11

2.某32位系統下, C++程序，請計算sizeof 的值(5分).
char str[] = 「www.ibegroup.com」
char *p = str ;
int n = 10;
請計算
sizeof (str ) = ？（1）
sizeof ( p ) = ？（2）
sizeof ( n ) = ？（3）
void Foo ( char str[100]){
請計算
sizeof( str ) = ？（4）
}
void *p = malloc( 100 );
請計算
sizeof ( p ) = ？（5）
答：（1）17 （2）4 （3） 4 （4）4 （5）4

3. 回答下面的問題. (4分)
(1).頭文件中的 ifndef/define/endif 干什麼用？預處理
答：防止頭文件被重復引用
(2). #include 和 #include 「filename.h」 有什麼區別？
答：前者用來包含開發環境提供的庫頭文件，後者用來包含自己編寫的頭文件。
(3).在C++ 程序中調用被 C 編譯器編譯後的函數，為什麼要加 extern 「C」聲明？
答：函數和變數被C++編譯後在符號庫中的名字與C語言的不同，被extern "C"修飾的變數和函數是按照C語言方式編譯和連接的。由於編譯後的名字不同，C++程序不能直接調用C 函數。C++提供了一個C 連接交換指定符號extern「C」來解決這個問題。
(4). switch()中不允許的數據類型是?
答：實型

4. 回答下面的問題(6分)
(1).

Void GetMemory(char **p, int num){
*p = (char *)malloc(num);
}
void Test(void){
char *str = NULL;
GetMemory(&str, 100);
strcpy(str, "hello");
printf(str);
}
請問運行Test 函數會有什麼樣的結果？
答：輸出「hello」
(2).

void Test(void){
char *str = (char *) malloc(100);
strcpy(str, 「hello」);
free(str);
if(str != NULL){
strcpy(str, 「world」);
printf(str);
}
}
請問運行Test 函數會有什麼樣的結果？
答：輸出「world」，因為free(str)後並未改變str所指的內存內容。
(3).

char *GetMemory(void){
char p[] = "hello world";
return p;
}
void Test(void){
char *str = NULL;
str = GetMemory();
printf(str);
}
請問運行Test 函數會有什麼樣的結果？
答：無效的指針，輸出不確定

5. 編寫strcat函數(6分)
已知strcat函數的原型是char *strcat (char *strDest, const char *strSrc);
其中strDest 是目的字元串，strSrc 是源字元串。
（1）不調用C++/C 的字元串庫函數，請編寫函數 strcat
答：
VC源碼：

char * __cdecl strcat (char * dst, const char * src)
{
char * cp = dst;
while( *cp )
cp++; /* find end of dst */
while( *cp++ = *src++ ) ; /* Copy src to end of dst */
return( dst ); /* return dst */
}
（2）strcat能把strSrc 的內容連接到strDest，為什麼還要char * 類型的返回值？
答：方便賦值給其他變數

6.MFC中CString是類型安全類么？
答：不是，其它數據類型轉換到CString可以使用CString的成員函數Format來轉換

7.C++中為什麼用模板類。
答：(1)可用來創建動態增長和減小的數據結構
（2）它是類型無關的，因此具有很高的可復用性。
（3）它在編譯時而不是運行時檢查數據類型，保證了類型安全
（4）它是平台無關的，可移植性
（5）可用於基本數據類型

8.CSingleLock是干什麼的。
答：同步多個線程對一個數據類的同時訪問

9.NEWTEXTMETRIC 是什麼。
答：物理字體結構，用來設置字體的高寬大小

10.程序什麼時候應該使用線程，什麼時候單線程效率高。
答：1．耗時的操作使用線程，提高應用程序響應
2．並行操作時使用線程，如C/S架構的伺服器端並發線程響應用戶的請求。
3．多CPU系統中，使用線程提高CPU利用率
4．改善程序結構。一個既長又復雜的進程可以考慮分為多個線程，成為幾個獨立或半獨立的運行部分，這樣的程序會利於理解和修改。
其他情況都使用單線程。

11.Windows是內核級線程么。
答：見下一題

12.Linux有內核級線程么。
答：線程通常被定義為一個進程中代碼的不同執行路線。從實現方式上劃分，線程有兩種類型：「用戶級線程」和「內核級線程」。用戶線程指不需要內核支持而在用戶程序中實現的線程，其不依賴於操作系統核心，應用進程利用線程庫提供創建、同步、調度和管理線程的函數來控制用戶線程。這種線程甚至在象 DOS 這樣的操作系統中也可實現，但線程的調度需要用戶程序完成，這有些類似 Windows 3.x 的協作式多任務。另外一種則需要內核的參與，由內核完成線程的調度。其依賴於操作系統核心，由內核的內部需求進行創建和撤銷，這兩種模型各有其好處和缺點。用戶線程不需要額外的內核開支，並且用戶態線程的實現方式可以被定製或修改以適應特殊應用的要求，但是當一個線程因 I/O 而處於等待狀態時，整個進程就會被調度程序切換為等待狀態，其他線程得不到運行的機會；而內核線程則沒有各個限制，有利於發揮多處理器的並發優勢，但卻佔用了更多的系統開支。
Windows NT和OS/2支持內核線程。Linux 支持內核級的多線程

13.C++中什麼數據分配在棧或堆中，New分配數據是在近堆還是遠堆中？
答：棧: 存放局部變數，函數調用參數,函數返回值，函數返回地址。由系統管理
堆: 程序運行時動態申請，new 和 malloc申請的內存就在堆上
近堆還是遠堆不是很清楚。

14.使用線程是如何防止出現大的波峰。
答：意思是如何防止同時產生大量的線程，方法是使用線程池，線程池具有可以同時提高調度效率和限制資源使用的好處，線程池中的線程達到最大數時，其他線程就會排隊等候。

15函數模板與類模板有什麼區別？
答：函數模板的實例化是由編譯程序在處理函數調用時自動完成的，而類模板的實例化必須由程序員在程序中顯式地指定。

16一般資料庫若出現日誌滿了，會出現什麼情況，是否還能使用？
答：只能執行查詢等讀操作，不能執行更改，備份等寫操作，原因是任何寫操作都要記錄日誌。也就是說基本上處於不能使用的狀態。

17 SQL Server是否支持行級鎖，有什麼好處？
答：支持，設立封鎖機制主要是為了對並發操作進行控制，對干擾進行封鎖，保證數據的一致性和准確性，行級封鎖確保在用戶取得被更新的行到該行進行更新這段時間內不被其它用戶所修改。因而行級鎖即可保證數據的一致性又能提高數據操作的迸發性。

18如果資料庫滿了會出現什麼情況，是否還能使用？
答：見16

19 關於內存對齊的問題以及sizof()的輸出
答：編譯器自動對齊的原因：為了提高程序的性能，數據結構（尤其是棧）應該盡可能地在自然邊界上對齊。原因在於，為了訪問未對齊的內存，處理器需要作兩次內存訪問；然而，對齊的內存訪問僅需要一次訪問。

20 int i=10, j=10, k=3; k*=i+j; k最後的值是？
答：60，此題考察優先順序，實際寫成： k*=(i+j);，賦值運算符優先順序最低

21.對資料庫的一張表進行操作,同時要對另一張表進行操作,如何實現?
答：將操作多個表的操作放入到事務中進行處理

22.TCP/IP 建立連接的過程?(3-way shake)
答：在TCP/IP協議中，TCP協議提供可靠的連接服務，採用三次握手建立一個連接。
第一次握手：建立連接時，客戶端發送syn包(syn=j)到伺服器，並進入SYN_SEND狀態，等待伺服器確認；
第二次握手：伺服器收到syn包，必須確認客戶的SYN（ack=j+1），同時自己也發送一個SYN包（syn=k），即SYN+ACK包，此時伺服器進入SYN_RECV狀態；
第三次握手：客戶端收到伺服器的SYN＋ACK包，向伺服器發送確認包ACK(ack=k+1)，此包發送完畢，客戶端和伺服器進入ESTABLISHED狀態，完成三次握手。

23.ICMP是什麼協議,處於哪一層?
答：Internet控制報文協議，處於網路層（IP層）

24.觸發器怎麼工作的?
答：觸發器主要是通過事件進行觸發而被執行的，當對某一表進行諸如UPDATE、 INSERT、 DELETE 這些操作時，資料庫就會自動執行觸發器所定義的SQL 語句，從而確保對數據的處理必須符合由這些SQL 語句所定義的規則。

25.winsock建立連接的主要實現步驟?
答：伺服器端：socker()建立套接字，綁定（bind）並監聽（listen），用accept（）等待客戶端連接。
客戶端：socker()建立套接字，連接（connect）伺服器，連接上後使用send()和recv（），在套接字上寫讀數據，直至數據交換完畢，closesocket()關閉套接字。
伺服器端：accept（）發現有客戶端連接，建立一個新的套接字，自身重新開始等待連接。該新產生的套接字使用send()和recv（）寫讀數據，直至數據交換完畢，closesocket()關閉套接字。

26.動態連接庫的兩種方式?
答：調用一個DLL中的函數有兩種方法：
1．載入時動態鏈接（load-time dynamic linking），模塊非常明確調用某個導出函數，使得他們就像本地函數一樣。這需要鏈接時鏈接那些函數所在DLL的導入庫，導入庫向系統提供了載入DLL時所需的信息及DLL函數定位。
2．運行時動態鏈接（run-time dynamic linking），運行時可以通過LoadLibrary或LoadLibraryEx函數載入DLL。DLL載入後，模塊可以通過調用 GetProcAddress獲取DLL函數的出口地址，然後就可以通過返回的函數指針調用DLL函數了。如此即可避免導入庫文件了。

27.IP組播有那些好處?答： Internet上產生的許多新的應用，特別是高帶寬的多媒體應用，帶來了帶寬的急劇消耗和網路擁擠問題。組播是一種允許一個或多個發送者（組播源）發送單一的數據包到多個接收者（一次的，同時的）的網路技術。組播可以大大的節省網路帶寬，因為無論有多少個目標地址，在整個網路的任何一條鏈路上只傳送單一的數據包。所以說組播技術的核心就是針對如何節約網路資源的前提下保證服務質量。

B. UDP如何轉為可靠協議面試回答了TCP和UDP

任何tcp連接都是一樣的，三次握手過程
第一次發送syn包，回復syn/ack包，再恢復ack包，然後建立連接

C. TCP/IP協議面試題目,關於UDP面試題目.

任何tcp連接都是一樣的，
三次握手
過程
第一次發送syn包，回復syn/ack包，再恢復ack包，然後建立連接

D. 各大公司筆試題及答案

騰訊筆試題：const的含義及實現機制
const的含義及實現機制，比如：const int i,是怎麼做到i只可讀的？
const用來說明所定義的變數是只讀的。
這些在編譯期間完成，編譯器可能使用常數直接替換掉對此變數的引用。
更多閱讀：
http://www.92ask.net/Archive/?action=show&id=18
初探編譯器static、const之實現原理
騰訊筆試題：買200返100優惠券，實際上折扣是多少？
到商店裡買200的商品返還100優惠券（可以在本商店代替現金）。請問實際上折扣是多少？
由於優惠券可以代替現金，所以可以使用200元優惠券買東西，然後還可以獲得100元的優惠券。
假設開始時花了x元，那麼可以買到 x + x/2 + x/4 + ...的東西。所以實際上折扣是50%.（當然，大部分時候很難一直兌換下去，所以50%是折扣的上限）
如果使用優惠券買東西不能獲得新的優惠券，那麼
總過花去了200元，可以買到200+100元的商品，所以實際折扣為 200/300 = 67%.
騰訊筆試題：tcp三次握手的過程，accept發生在三次握手哪個階段？
accept發生在三次握手之後。
第一次握手：客戶端發送syn包(syn=j)到伺服器。
第二次握手：伺服器收到syn包，必須確認客戶的SYN（ack=j+1），同時自己也發送一個ASK包（ask=k）。
第三次握手：客戶端收到伺服器的SYN＋ACK包，向伺服器發送確認包ACK(ack=k+1)。
三次握手完成後，客戶端和伺服器就建立了tcp連接。這時可以調用accept函數獲得此連接。
騰訊筆試題：用UDP協議通訊時怎樣得知目標機是否獲得了數據包
用UDP協議通訊時怎樣得知目標機是否獲得了數據包？
可以在每個數據包中插入一個唯一的ID，比如timestamp或者遞增的int。
發送方在發送數據時將此ID和發送時間記錄在本地。
接收方在收到數據後將ID再發給發送方作為回應。
發送方如果收到回應，則知道接收方已經收到相應的數據包；如果在指定時間內沒有收到回應，則數據包可能丟失，需要重復上面的過程重新發送一次，直到確定對方收到。
關於UDP協議的簡單介紹，可以參考
http://ke..com/view/30509.htm
騰訊筆試題：統計論壇在線人數分布
求一個論壇的在線人數，假設有一個論壇，其注冊ID有兩億個，每個ID從登陸到退出會向一個日誌文件中記下登陸時間和退出時間，要求寫一個演算法統計一天中論壇的用戶在線分布，取樣粒度為秒。
一天總共有 3600*24 = 86400秒。
定義一個長度為86400的整數數組int delta[86400]，每個整數對應這一秒的人數變化值，可能為正也可能為負。開始時將數組元素都初始化為0。
然後依次讀入每個用戶的登錄時間和退出時間，將與登錄時間對應的整數值加1，將與退出時間對應的整數值減1。
這樣處理一遍後數組中存儲了每秒中的人數變化情況。
定義另外一個長度為86400的整數數組int online_num[86400]，每個整數對應這一秒的論壇在線人數。
假設一天開始時論壇在線人數為0，則第1秒的人數online_num[0] = delta[0]。第n+1秒的人數online_num[n] = online_num[n-1] + delta[n]。
這樣我們就獲得了一天中任意時間的在線人數。
騰訊筆試題：從10G個數中找到中數
在一個文件中有 10G 個整數，亂序排列，要求找出中位數。內存限制為 2G。
不妨假設10G個整數是64bit的。
2G內存可以存放256M個64bit整數。
我們可以將64bit的整數空間平均分成256M個取值范圍，用2G的內存對每個取值范圍內出現整數個數進行統計。這樣遍歷一邊10G整數後，我們便知道中數在那個范圍內出現，以及這個范圍內總共出現了多少個整數。
如果中數所在范圍出現的整數比較少，我們就可以對這個范圍內的整數進行排序，找到中數。如果這個范圍內出現的整數比較多，我們還可以採用同樣的方法將此范圍再次分成多個更小的范圍（256M=2^28，所以最多需要3次就可以將此范圍縮小到1，也就找到了中數）。
騰訊筆試題：兩個整數集合A和B，求其交集
兩個整數集合A和B，求其交集。
1. 讀取整數集合A中的整數，將讀到的整數插入到map中，並將對應的值設為1。
2. 讀取整數集合B中的整數，如果該整數在map中並且值為1，則將此數加入到交集當中，並將在map中的對應值改為2。
通過更改map中的值，避免了將同樣的值輸出兩次。
騰訊筆試題：找出1到10w中沒有出現的兩個數字
有1到10w這10w個數，去除2個並打亂次序，如何找出那兩個數？
申請10w個bit的空間，每個bit代表一個數字是否出現過。
開始時將這10w個bit都初始化為0，表示所有數字都沒有出現過。
然後依次讀入已經打亂循序的數字，並將對應的bit設為1。
當處理完所有數字後，根據為0的bit得出沒有出現的數字。
首先計算1到10w的和，平方和。
然後計算給定數字的和，平方和。
兩次的到的數字相減，可以得到這兩個數字的和，平方和。
所以我們有
x + y = n
x^2 + y^2 = m
解方程可以得到x和y的值。
騰訊筆試題：需要多少只小白鼠才能在24小時內找到毒葯
有1000瓶水，其中有一瓶有毒，小白鼠只要嘗一點帶毒的水24小時後就會死亡，至少要多少只小白鼠才能在24小時時鑒別出那瓶水有毒？
最容易想到的就是用1000隻小白鼠，每隻喝一瓶。但顯然這不是最好答案。
既然每隻小白鼠喝一瓶不是最好答案，那就應該每隻小白鼠喝多瓶。那每隻應該喝多少瓶呢？
首先讓我們換種問法，如果有x只小白鼠，那麼24小時內可以從多少瓶水中找出那瓶有毒的？
由於每隻小白鼠都只有死或者活這兩種結果，所以x只小白鼠最大可以表示2^x種結果。如果讓每種結果都對應到某瓶水有毒，那麼也就可以從2^x瓶水中找到有毒的那瓶水。那如何來實現這種對應關系呢？
第一隻小白鼠喝第1到2^(x-1)瓶，第二隻小白鼠喝第1到第2^(x-2)和第2^(x-1)+1到第2^(x-1) + 2^(x-2)瓶....以此類推。
回到此題，總過1000瓶水，所以需要最少10隻小白鼠。
騰訊筆試題：根據上排的數填寫下排的數，並滿足要求。
根據上排給出十個數，在其下排填出對應的十個數, 要求下排每個數都是上排對應位置的數在下排出現的次數。上排的數：0，1，2，3，4，5，6，7，8，9。
騰訊筆試題：判斷數字是否出現在40億個數中？
給40億個不重復的unsigned int的整數，沒排過序的，然後再給幾個數，如何快速判斷這幾個數是否在那40億個數當中?
答案：
unsigned int 的取值范圍是0到2^32-1。我們可以申請連續的2^32/8=512M的內存，用每一個bit對應一個unsigned int數字。首先將512M內存都初始化為0，然後每處理一個數字就將其對應的bit設置為1。當需要查詢時，直接找到對應bit，看其值是0還是1即 可。
1、請定義一個宏，比較兩個數a、b的大小，不能使用大於、小於、if語句#define Max(a,b) ( a/b)?a:b
2、如何輸出源文件的標題和目前執行行的行數
int line = __LINE__;
char *file = __FILE__;
cout<<"file name is "<<(file)<<",line is "<
3、兩個數相乘，小數點後位數沒有限制，請寫一個高精度演算法
4、寫一個病毒
while (1)
{
int *p = new int[10000000];
}
5、不使用額外空間,將 A,B兩鏈表的元素交*歸並
6、將樹序列化 轉存在數組或 鏈表中
struct st{
int i;
short s;
char c;
};
sizeof(struct st)；
7、
char * p1;
void * p2;
int p3;
char p4[10];
sizeof(p1...p4) =?
8、
4，4，4，10
二分查找
快速排序
雙向鏈表的刪除結點
面試基本上都是和項目相關的，並當場說幾個程序題的輸出，不能用草稿紙

微軟筆試題：寫程序找出二叉樹的深度
一個樹的深度等於max（左子樹深度，右子樹深度）+1。可以使用遞歸實現。
假設節點為定義為
1. struct Node {
2. Node* left;
3. Node* right;
4. };
5. int GetDepth(Node* root) {
6. if (NULL == root) {
7. return 0;
8. }
9. int left_depth = GetDepth(root->left);
10. int right_depth = GetDepth(root->right);
11. return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
12. }
微軟筆試題：利用天平砝碼，三次將140克的鹽 分成50、90克兩份？
有一個天平，2克和7克砝碼各一個。如何利用天平砝碼在三次內將140克鹽分成50，90克兩份。
第一種方法：
第一次:先稱 7+2克鹽 (相當於有三個法碼2,7,9)
第二次:稱2+7+9=18克鹽 (相當於有2,7,9,18四個法碼)
第三次:稱7+18=x+2,得出x是23，23+9+18=50克鹽.
剩下就是90克了.
第二種方法：
1.先把140克鹽分為兩份，每份70克
2.在把70克分為兩份，每份35克
3.然後把兩個砝碼放在天平兩邊，把35克麵粉分成兩份也放在兩邊（15+7=20+2）
現在有四堆麵粉70，35，15，20，分別組合得到
70+20=90
35+15=50
微軟筆試題：地球上有多少個滿足這樣條件的點
站在地球上的某一點，向南走一公里，然後向東走一公里，最後向北走一公里，回到了原點。地球上有多少個滿足這樣條件的點?
北極點滿足這個條件。
距離南極點很近的一個圈上也滿足這個條件。在這個圓圈上，向南走一公里，然後向東走一公里恰好繞南極點一圈，向北走一公里回到原點。
所以地球上總共有無數點滿足這個條件。
或者
首先，在地球表面上，南北走向是沿著經度方向，東西是沿著緯度方向。如果你一直往北走就會達到北極點，往南走就到了南極點。因此，向南走一公里，然 後向東走一公里，最後向北走一公里，回到了原點，一種情況就是，出發點是在北極點，這樣向南走一公里，然後向東走任意幾公里，最後向北走一公里，最後都會 回到北極點；
其次，可以這么認為如果從A點向南走一公里到達B點，那麼若向東走一公里能回到B，那麼最後向北走一公里，就能回到了原點A。這樣就可以先找出在南 北極點附近找出繞一周只有1公里的圈，那麼這個圈落在南極附近時，只要往北推1公里，此時該圈上的點都能滿足；若這個圈落在北極附近時，能不能往北推1公 里我就不分析了。反正在南極附近能找到任意多個點就能回到這個問題了
微軟筆試題：正確標注水果籃
有三個水果籃。其中一個裡面只有蘋果，一個裡面只有橘子，另外一個既有蘋果又有橘子。每個水果籃上都有標簽，但標簽都是錯的。如何檢查某個水果籃中的一個水果，然後正確標注每個水果籃？
從標注成既有蘋果也有橘子的水果籃中選取一個進行檢查。
如果是橘子，則此籃中只有橘子；標有橘子的水果籃中只有蘋果；標有蘋果的水果籃中既有蘋果也有橘子。
如果是蘋果，則此籃中只有蘋果；標有蘋果的水果籃中只有橘子；標有橘子的水果籃中既有蘋果也有橘子。
微軟筆試題：不利用浮點運算，畫一個圓
不利用浮點運算，在屏幕上畫一個圓 (x**2 + y**2 = r**2，其中 r 為正整數)。
考慮到圓的對稱性，我們只需考慮第一象限即可。
等價於找到一條連接點（0，r）到點（r，0）的一條曲線，曲線上的點距圓心（0，0）的距離最接近 r。
我們可以從點（0，r）開始，搜索右（1，r），下（0，r-1），右下（1，r-1）三個點到圓心的距離，選擇距圓心距離最接近 r 的點作為下一個點。反復進行這種運算，直至到達點（r，0）。
由於不能利用浮點運算，所以距離的比較只能在距離平方的基礎上進行。也就是比較 x**2 + y**2 和 r**2之間的差值。
微軟筆試題：將一個句子按單詞反序
將一個句子按單詞反序。比如 「hi com mianshiti」，反序後變為 「mianshiti com hi」。
可以分兩步走：
第一步按找字母反序，「hi com mianshiti」 變為 「itihsnaim moc udiab ih」。
第二部將每個單詞中的字母反序，「itihsnaim moc udiab ih」 變成 「mianshiti com hi」。
這個方法可以在原字元串上進行，只需要幾個整數變數來保持指針即可，空間復雜度低。
微軟筆試題：計算n bit的整數中有多少bit 為1
設此整數為x。
方法1：
讓此整數除以2，如果余數為1，說明最後一位是1，統計值加1。
將除得的結果進行上面運算，直到結果為0。
方法2：
考慮除法復雜度有些高，可以使用移位操作代替除法。
將 x 和 1 進行按位與操作（x&1），如果結果為1，說明最後一位是1，統計值加1。
將x 向右一位（x >> 1），重復上面過程，直到移位後結果為0。
方法3：
如果需要統計很多數字，並且內存足夠大，可以考慮將每個數對應的bit為1的數量記錄下來，這樣每次計算只是一次查找操作。
1. int n = 0;while (x)
2. {
3. xx = x & (x - 1);
4. n++;
5. }
6. return n;
微軟筆試題：快速求取一個整數的7倍
乘法相對比較慢，所以快速的方法就是將這個乘法轉換成加減法和移位操作。
可以將此整數先左移三位（×8）然後再減去原值：X << 3 - X。
微軟筆試題：判斷一個數是不是2的n次冪
設要判斷的數是無符號整數X。
首先判斷X是否為0，如果為0則不是2的n次冪，返回。
X和X-1進行按位與操作，如果結果是0，則說明這個數是2的n次冪；如果結果非0，則說明這個數不是2 的n次冪。
證明：
如果是2的n次冪，則此數用二進製表示時只有一位是1，其它都是0。減1後，此位變成0，後面的位變成1，所以按位與後結果是0。
如果不是2的n次冪，則此數用二進製表示時有多位是1。減1後，只有最後一個1變成0，前面的 1還是1，所以按位與後結果不是0。
微軟筆試題：三隻螞蟻不相撞的概率是多少
在三角形的三個頂點上各有一隻螞蟻，它們向另一個頂點運動，目標隨機（可能為另外兩個頂點的任意一個）。問三隻螞蟻不相撞的概率是多少？
如果螞蟻順時針爬行記為0，逆時針爬行記為1。那麼三隻螞蟻的狀態可能為000，001，...，110，111中的任意一個，且為每種狀態的概率相等。在這8種狀態中，只有000和111可以避免相撞，所以螞蟻不相撞的概率是1/4。
微軟筆試題：判斷數組中是否包含重復數字
給定一個長度為N的數組，其中每個元素的取值范圍都是1到N。判斷數組中是否有重復的數字。（原數組不必保留）
給定一個長度為N的數組，其中每個元素的取值范圍都是1到N。判斷數組中是否有重復的數字。（原數組不必保留）
微軟筆試題：如何將蛋糕切成相等的兩份
一塊長方形的蛋糕，其中有一個小長方形的空洞（角度任意）。使用一把直刀，如何一刀將蛋糕切成相等的兩份？
通過長方形中心的的任意直線都能將長方形等分，所以連接兩個長方形的中心點的直線可以等分這個蛋糕。
一個沒有排序的鏈表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，請去掉重復項，並保留原順序，以上鏈表去掉重復項後為newlist={a,l,x,b,e,f,g,h,m}，請寫出一個高效演算法(時間比空間更重要)。
建立一個hash_map，key為鏈表中已經遍歷的節點內容，開始時為空。
從頭開始遍歷鏈表中的節點：
- 如果節點內容已經在hash_map中存在，則刪除此節點，繼續向後遍歷；
- 如果節點內容不在hash_map中，則保留此節點，將節點內容添加到hash_map中，繼續向後遍歷。
微軟筆試題：小明一家5口如何過橋？
小明一家過一座橋，過橋時是黑夜，所以必須有燈。現在小明過橋要1秒，小明的弟弟要3秒，小明的爸爸要6秒，小明的媽媽要8秒，小明的爺爺要12秒。每次此橋最多可過兩人，而過橋的速度依過橋最慢者而定，而且燈在點燃後30秒就會熄滅。問：小明一家如何過橋？
小明與弟弟過去，小明回來，用4s；
媽媽與爺爺過去，弟弟回來，用15s；
小明與弟弟過去，小明回來，用4s；
小明與爸爸過去，用6s；
總共用29s。
題目的關鍵是讓速度差不多的一起走，免得過於拖累較快的一個人。
微軟筆試題：編一個程序求質數的和
編一個程序求質數的和，例如F(7) = 2+3+5+7+11+13+17=58。
方法1：
對於從2開始的遞增整數n進行如下操作：
用 [2，n-1] 中的數依次去除n，如果余數為0，則說明n不是質數；如果所有餘數都不是0，則說明n是質數，對其進行加和。
空間復雜度為O(1)，時間復雜度為O(n^2)，其中n為需要找到的最大質數值（例子對應的值為17）。
方法2：
可以維護一個質數序列，這樣當需要判斷一個數是否是質數時，只需判斷是否能被比自己小的質數整除即可。
對於從2開始的遞增整數n進行如下操作：
用 [2，n-1] 中的質數（2，3，5，7，開始時此序列為空）依次去除n，如果余數為0，則說明n不是質數；如果所有餘數都不是0，則說明n是質數，將此質數加入質數序列，並對其進行加和。
空間復雜度為O(m)，時間復雜度為O(mn)，其中m為質數的個數（例子對應的值為7），n為需要找到的最大質數值（例子對應的值為17）。
方法3：
也可以不用除法，而用加法。
申請一個足夠大的空間，每個bit對應一個整數，開始將所有的bit都初始化為0。
對於已知的質數（開始時只有2），將此質數所有的倍數對應的bit都改為1，那麼最小的值為0的bit對應的數就是一個質數。對新獲得的質數的倍數也進行標注。
對這樣獲得的質數序列累加就可以獲得質數和。
空間復雜度為O(n)，時間負責度為O(n)，其中n為需要找到的最大質數值（例子對應的值為17）。

E. 網路工程師面試題

網路工程師面試題 1: 交換機是如何轉發數據包的?

交換機通過學習數據幀中的源MAC地址生成交換機的MAC地址表，交換機查看數據幀的目標MAC地址，根據MAC地址表轉發數據，如果交換機在表中沒有找到匹配項，則向除接受到這個數據幀的埠以外的所有埠廣播這個數據幀。

2 簡述STP的作用及工作原理.

作用:(1) 能夠在邏輯上阻斷環路，生成樹形結構的拓撲;
(2) 能夠不斷的檢測網路的變化，當主要的線路出現故障斷開的時候，STP還能通過計算激活阻起到斷的埠，起到鏈路的備份作用。
工作原理: STP將一個環形網路生成無環拓樸的步驟：
選擇根網橋（Root Bridge）
選擇根埠（Root Ports）
選擇指定埠（Designated Ports）

生成樹機理
每個STP實例中有一個根網橋
每個非根網橋上都有一個根埠
每個網段有一個指定埠
非指定埠被阻塞 STP是交換網路的重點,考察是否理解.

3:簡述傳統的多層交換與基於CEF的多層交換的區別

簡單的說:傳統的多層交換:一次路由,多次交換

基於CEF的多層交換:無須路由,一直交換.

4:DHCP的作用是什麼,如何讓一個vlan中的DHCP伺服器為整個企業網路分配IP地址?

作用:動態主機配置協議,為客戶端動態分配IP地址.
配置DHCP中繼,也就是幫助地址.(因為DHCP是基於廣播的,vlan 或路由器隔離了廣播)

5:有一台交換機上的所有用戶都獲取不了IP地址,但手工配置後這台交換機上的同一vlan間的用戶之間能夠相互ping通,但ping不通外網,請說出排障思路.

1:如果其它交換機上的終端設備能夠獲取IP地址,看幫助地址是否配置正確;
2:此交換機與上連交換機間是否封裝為Trunk.
3:單臂路由實現vlan間路由的話看子介面是否配置正確,三層交換機實現vlan間路由的話看是否給vlan配置ip地址及配置是否正確.
4:再看此交換機跟上連交換機之間的級連線是否有問題;
排障思路.

6:什麼是靜態路由？什麼是動態路由？各自的特點是什麼？

靜態路由是由管理員在路由器中手動配置的固定路由，路由明確地指定了包到達目的地必須經過的路徑，除非網路管理員干預，否則靜態路由不會發生變化。靜態路由不能對網路的改變作出反應，所以一般說靜態路由用於網路規模不大、拓撲結構相對固定的網路。

靜態路由特點
1、它允許對路由的行為進行精確的控制；
2、減少了網路流量；
3、是單向的；
4、配置簡單。
動態路由是網路中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由表的過程。是基於某種路由協議來實現的。常見的路由協議類型有：距離矢量路由協議（如RIP）和鏈路狀態路由協議（如 OSPF）。路由協議定義了路由器在與其它路由器通信時的一些規則。動態路由協議一般都有路由演算法。其路由選擇演算法的必要步驟
1、向其它路由器傳遞路由信息；
2、接收其它路由器的路由信息；
3、根據收到的路由信息計算出到每個目的網路的最優路徑，並由此生成路由選擇表；
4、根據網路拓撲的變化及時的做出反應，調整路由生成新的路由選擇表，同時把拓撲變化以路由信息的形式向其它路由器宣告。
動態路由適用於網路規模大、拓撲復雜的網路。
動態路由特點：
1、無需管理員手工維護，減輕了管理員的工作負擔。
2、佔用了網路帶寬。
3、在路由器上運行路由協議，使路由器可以自動根據網路拓樸結構的變化調整路由條目；
能否根據具體的環境選擇合適的路由協議

7:簡述有類與無類路由選擇協議的區別

有類路由協議:路由更新信息中不含有子網信息的協議,如RIPV1,IGRP
無類路由協議:路由更新信息中含有子網信息的協議,如OSPF,RIPV2,IS-IS，EIGRP 是否理解有類與無類
8:簡述RIP的防環機制
1.定義最大跳數 Maximum Hop Count （15跳）
2.水平分割 Split Horizon （默認所有介面開啟，除了Frame-Relay的物理介面，可用sh ip interface 查看開啟還是關閉）
3.毒化路由 Poizoned Route
4.毒性反轉 Poison Reverse （RIP基於UDP，UDP和IP都不可靠，不知道對方收到毒化路由沒有；類似於對毒化路由的Ack機制）
5.保持計時器 hold­-down Timer （防止路由表頻繁翻動）
6.閃式更新 Flash Update
7.觸發更新 Triggered Update （需手工啟動，且兩邊都要開 Router (config-if)# ip rip triggered ）
當啟用觸發更新後，RIP不再遵循30s的周期性更新時間，這也是與閃式更新的區別所在。

RIP的4個計時器：
更新計時器（update）： 30 s
無效計時器（invalid）： 180 s （180s沒收到更新，則置為possible down狀態）
保持計時器（holddown）： 180s （真正起作用的只有60s）
刷新計時器（flush）： 240s （240s沒收到更新，則刪除這條路由）
如果路由變成possible down後，這條路由跳數將變成16跳，標記為不可達；這時holddown計時器開始計時。
在holddown時間內即使收到更優的路由，不加入路由表；這樣做是為了防止路由頻繁翻動。
什麼時候啟用holddown計時器： 「當收到一條路由更新的跳數大於路由表中已記錄的該條路由的跳數」

9:簡述電路交換和分組交換的區別及應用場合. 電路交換連接

根據需要進行連接
每一次通信會話期間都要建立、保持，然後拆除
在電信運營商網路中建立起來的專用物理電路

分組交換連接
將傳輸的數據分組
多個網路設備共享實際的物理線路
使用虛電路/虛通道（Virtual Channel）傳輸

若要傳送的數據量很大，且其傳送時間遠大於呼叫時間，則採用電路交換較為合適；當端到端的通路有很多段的鏈路組成時，採用分組交換傳送數據較為合適。

10:簡述PPP協議的優點. 支持同步或非同步串列鏈路的傳輸

支持多種網路層協議
支持錯誤檢測
支持網路層的地址協商
支持用戶認證
允許進行數據壓縮

11: pap和chap認證的區別

PAP(口令驗證協議 Password Authentication Protocol)是一種簡單的明文驗證方式。NAS（網路接入伺服器，Network Access Server）要求用戶提供用戶名和口令，PAP以明文方式返回用戶信息。很明顯，這種驗證方式的安全性較差，第三方可以很容易的獲取被傳送的用戶名和口令，並利用這些信息與NAS建立連接獲取NAS提供的所有資源。所以，一旦用戶密碼被第三方竊取，PAP無法提供避免受到第三方攻擊的保障措施。

CHAP(挑戰-握手驗證協議 Challenge-Handshake Authentication Protocol)是一種加密的驗證方式，能夠避免建立連接時傳送用戶的真實密碼。NAS向遠程用戶發送一個挑戰口令（challenge），其中包括會話ID和一個任意生成的挑戰字串（arbitrary challengestring）。遠程客戶必須使用MD5單向哈希演算法（one-way hashing algorithm）返回用戶名和加密的挑戰口令，會話ID以及用戶口令，其中用戶名以非哈希方式發送。

CHAP對PAP進行了改進，不再直接通過鏈路發送明文口令，而是使用挑戰口令以哈希演算法對口令進行加密。因為伺服器端存有客戶的明文口令，所以伺服器可以重復客戶端進行的操作，並將結果與用戶返回的口令進行對照。CHAP為每一次驗證任意生成一個挑戰字串來防止受到再現攻擊（replay attack）。在整個連接過程中，CHAP將不定時的向客戶端重復發送挑戰口令，從而避免第3方冒充遠程客戶（remote client impersonation）進行攻擊。

12:ADSL是如何實現數據與語音同傳的?

物理層:頻分復用技術.(高頻傳輸數據,低頻傳輸語音)具體講解的話可以說明:調制,濾波,解調的過程.

13:OSPF中那幾種網路類型需要選擇DR,BDR?

廣播型網路和非廣播多路訪問NBMA網路需要選.

14:OSPF中完全末梢區域的特點及適用場合

特點:不能學習其他區域的路由
不能學習外部路由
完全末梢區域不僅使用預設路由到達OSPF自主系統外部的目的地址,而且使用這個預設路由到達這個區域外部的所有目的地址.一個完全末梢區域的ABR不僅阻塞AS外部LSA,而且阻塞所有匯總LSA.
適用場合:只有一出口的網路.

15:OSPF中為什麼要劃分多區域?

1、減小路由表大小
2、限制lsa的擴散
3、加快收斂
4、增強穩定性

16:NSSA區域的特點是什麼?

1.可以學習本區域連接的外部路由；
2.不學習其他區域轉發進來的外部路由

17:你都知道網路的那些冗餘技術,請說明.

交換機的冗餘性：spanning－tree、ethernet－channel
路由的冗餘性:HSRP,VRRP,GLBP.
(有必要的話可以詳細介紹)

18:HSRP的轉換時間是多長時間?

10s

19:標准訪問控制列表和擴展訪問控制列表的區別.

標准訪問控制列表:基於源進行過濾
擴展訪問控制列表: 基於源和目的地址、傳輸層協議和應用埠號進行過濾

20:NAT的原理及優缺點.

原理:轉換內部地址,轉換外部地址,PAT,解決地址重疊問題.
優點:節省IP地址,能夠處理地址重復的情況,增加了靈活性,消除了地址重新編號,隱藏了內部IP地址.
缺點:增加了延遲,丟失了端到端的IP的跟蹤過程,不能夠支持一些特定的應用(如:SNMP),需要更多的內存來存儲一個NAT表,需要更多的CPU來處理NAT的過程.

21: 對稱性加密演算法和非對稱型加密演算法的不同？

對稱性加密演算法的雙方共同維護一組相同的密鑰，並使用該密鑰加密雙方的數據，加密速度快，但密鑰的維護需要雙方的協商，容易被人竊取；非對稱型加密演算法使用公鑰和私鑰，雙方維護對方的公鑰（一對），並且各自維護自己的私鑰，在加密過程中，通常使用對端公鑰進行加密，對端接受後使用其私鑰進行解密，加密性良好，而且不易被竊取，但加密速度慢.

22: 安全關聯的作用？

SA分為兩步驟：1.IKE SA，用於雙方的對等體認證，認證對方為合法的對端；2.IPSec SA，用於雙方認證後，協商對數據保護的方式.

23: ESP和AH的區別？

ESP除了可以對數據進行認證外，還可以對數據進行加密；AH不能對數據進行加密，但對數據認證的支持更好 .

24: snmp的兩種工作方式是什麼,有什麼特點?

首先,SNMP是基於UDP的,有兩種工作方式,一種是輪詢,一種是中斷.
輪詢:網管工作站隨機開埠輪詢被管設備的UDP的161埠.
中斷:被管設備將trap報文主動發給網管工作站的UDP的162埠.
特點:輪詢一定能夠查到被管設備是否出現了故障,但實時性不好.
中斷實時性好(觸發更新),但不一定能夠將trap報文報告給網管工作站.