2014年騰訊面試試題8道

　　1. 根據(jù)以下代碼?

　　int ack(int m,int n)

　　{

　　if(m == 0)

　　return n + 1;

　　else if(n == 0)

　　return ack(m-1,1);

　　else

　　return ack(m – 1 , ack(m , n-1));

　　}

　　如果ack(3,3),。結(jié)果為多少

　　2. A，B兩個整數(shù)集合，設(shè)計一個算法求他們的交集，盡可能的高效。

　　我的回答的：如果對于數(shù)據(jù)較小(10W以下)我會采取哈希的方法去求數(shù)集較小的那個集合的hash值存在hash表中，然后對另一個表中每一個數(shù)進行hash，如果在hash表中找到則這個數(shù)是交集的數(shù)，輸出。這個算法時間效率是O(n+m)，空間效率O(3n+m);(因為hash幾乎浪費掉一半空間)

　　對于大數(shù)據(jù)，我則先把數(shù)據(jù)hash%100的樣子分到許多個小文件中，然后對這些hash值的次數(shù)建立一顆二叉查找樹，遍歷另一個集合的數(shù)來找，找到一個就輸出一個，最后得到集合數(shù)。算法效率是O(n/100*m*log(n/100))，空間效率O(n+m)

　　3. 請設(shè)計一個排隊系統(tǒng)，能夠讓每個進入隊伍的用戶都能看到自己在隊列中所處的位置和變化，隊伍可能隨時有人加入和退出;當(dāng)有人退出影響到用戶的位置排名時需要及時反饋到用戶。

　　4.怎么在linux下查找一個文件中有多少個給定的字符串

　　答：這題本來想考察我的shell編程的能力吧，不過我說這個不會，然后他問我如果寫程序?qū)崿F(xiàn)呢

　　我答我會用trie樹去記錄字符串出現(xiàn)的次數(shù)

　　然后有被問道更深入一點的，如果文件過大呢?

　　我答，那就把文件內(nèi)容hash取模分成多個足夠小的文件，然后每個小文件trie記錄結(jié)果，輸出一個小文件，最后把所有結(jié)果文件合并就可以得到最終結(jié)果

　　5. 寫二叉查找樹的查找算法，答案就不寫了，簡單。

　　寫完之后，面試官又問我由這里到一個什么地方的，要求最短時間，怎么求

　　這個就是問最短路算法，我就答了這個，然后他又問我怎么知道去的路徑通不通，我答用傳遞閉包去計算，

　　他問我如何傳遞閉包，然后我就畫圖演示了一下這個過程

　　6. 進程與線程的區(qū)別

　　這題我答得非常不好，我只答了進程有資源，線程沒資源，進程個數(shù)有限，而線程的個數(shù)幾乎不限，進程的調(diào)度慢，線程的調(diào)度快這些基礎(chǔ)點

　　但是被問到為什么進程調(diào)度比線程慢時，我答不出，我答是因為用戶態(tài)和內(nèi)核態(tài)的轉(zhuǎn)換造成的，但是百度一下，答案應(yīng)該是因為線程調(diào)度是在進程中進行，在同一存儲區(qū)內(nèi)操作，而進程則在不同存儲區(qū)操作，所以進程調(diào)度數(shù)度比線程慢

　　7. 問我TCP/IP有多少層

　　我答OSI標準有7層，但是目前工業(yè)大多使用5層的標準，然后回答了一下這些標準，我只會答5層標準的那一個。。。

　　接著又問我IP層(網(wǎng)絡(luò)層)的作用，

　　我答了很多，又說了什么TCP、UDP的，然后在面試官的知道下，我才答出，網(wǎng)絡(luò)層的作用是映射作用，主要是IP和MAC地址、端口的映射(我不知道對不對。。)

　　接著又問我TCP和UDP的區(qū)別

　　我就答，TCP是有連接的，UDP是無連接的，TCP通過三次握手保證數(shù)據(jù)的可靠性，UDP則沒有

　　最后還問我滑動窗口的東西，我就答了滑動窗口是為了保證數(shù)據(jù)被客戶端正確接收了，他又問我為什么能保證，然后我就畫圖演示滑動窗口的發(fā)送、接收、移動過程

　　8：寫一個函數(shù)，計算給定的一個整數(shù)中有多少個0