1.代碼編譯過程

1. 在cpp文件中展開include文件。
2. 將每個cpp文件編譯為一個對應(yīng)的obj文件。
3. 連接obj文件成為一個exe文件（或者其它的庫文件）

2.100W個整數(shù)中求最小的k個數(shù)，有哪些方法，優(yōu)缺點

快速排序： 分區(qū)時，根據(jù)數(shù)P將數(shù)組分為兩部分，設(shè)大于P的數(shù)個數(shù)為a，小于P的數(shù)的個數(shù)為b。如果，a>=k，則從這a個數(shù)取最大的k個數(shù)，若a<k，則從b個數(shù)取最大的k-a-1個。

3.兩個10G的文件中，求含有相同整數(shù)，有哪些方法，優(yōu)缺點

（1）快排+二分查找 （2）位圖法

位圖法的應(yīng)用

1、給40億個不重復(fù)的unsigned int的整數(shù)，沒排過序的，然后再給一個數(shù)，如何快速判斷這個數(shù)是否在那40億個數(shù)當(dāng)中 　　首先，將這40億個數(shù)字存儲到bitmap中，然后對于給出的數(shù)，判斷是否在bitmap中即可。

2、使用位圖法判斷整形數(shù)組是否存在重復(fù)       遍歷數(shù)組，一個一個放入bitmap，并且檢查其是否在bitmap中出現(xiàn)過，如果沒出現(xiàn)放入，否則即為重復(fù)的元素。

3、在2.5億個整數(shù)中找出不重復(fù)的整數(shù)，注，內(nèi)存不足以容納這2.5億個整數(shù)       參 考的一個方法是：采用2-Bitmap（每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義）。其實，這里可以使用兩個普 通的Bitmap，即第一個Bitmap存儲的是整數(shù)是否出現(xiàn)，如果再次出現(xiàn)，則在第二個Bitmap中設(shè)置即可。這樣的話，就可以使用簡單的1- Bitmap了。

hash_map:

其基本原理是：使用一個下標(biāo)范圍比較大的數(shù)組來存儲元素?？梢栽O(shè)計一個函數(shù)（哈希函數(shù)，也叫做散列函數(shù)），使得每個元素的關(guān)鍵字都與一個函數(shù)值（即數(shù)組下標(biāo)，hash值）相對應(yīng)，于是用這個數(shù)組單元來存儲這個元素；也可以簡單的理解為，按照關(guān)鍵字為每一個元素“分類”，然后將這個元素存儲在相應(yīng)“類”所對應(yīng)的地方，稱為桶。  但是，不能夠保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因此極有可能出現(xiàn)對于不同的元素，卻計算出了相同的函數(shù)值，這樣就產(chǎn)生了“沖突”，換句話說，就是把不同的元素分在了相同的“類”之中。 總的來說，“直接定址”與“解決沖突”是哈希表的兩大特點。  hash_map，首先分配一大片內(nèi)存，形成許多桶。是利用hash函數(shù)，對key進(jìn)行映射到不同區(qū)域（桶）進(jìn)行保存。

其插入過程是：    

1. 得到key    

2. 通過hash函數(shù)得到hash值    

3. 得到桶號(一般都為hash值對桶數(shù)求模)   

4. 存放key和value在桶內(nèi)。 

其取值過程是:   

1. 得到key    

2. 通過hash函數(shù)得到hash值    

3. 得到桶號(一般都為hash值對桶數(shù)求模)   

4. 比較桶的內(nèi)部元素是否與key相等，若都不相等，則沒有找到。 

5. 取出相等的記錄的value。  hash_map中直接地址用hash函數(shù)生成，解決沖突，用比較函數(shù)解決。這里可以看出，如果每個桶內(nèi)部只有一個元素，那么查找的時候只有一次比較。當(dāng)許多桶內(nèi)沒有值時，許多查詢就會更快了(指查不到的時候).  由此可見，要實現(xiàn)哈希表, 和用戶相關(guān)的是：hash函數(shù)和比較函數(shù)。這兩個參數(shù)剛好是我們在使用hash_map時需要指定的參數(shù)。

有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。

方案1：順序讀文件中，對于每個詞x，取，然后按照該值存到5000個小文件（記為）中。這樣每個文件大概是200k左右。如果其中的有的文件超過了1M大小，還可以按照類似的方法繼續(xù)往下分，知道分解得到的小文件的大小都不超過1M。對每個小文件，統(tǒng)計每個文件中出現(xiàn)的詞以及相應(yīng)的頻率（可以采用trie樹/hash_map等），并取出出現(xiàn)頻率最大的100個詞（可以用含100個結(jié)點的最小堆），并把100詞及相應(yīng)的頻率存入文件，這樣又得到了5000個文件。下一步就是把這5000個文件進(jìn)行歸并（類似與歸并排序）的過程了。

海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。

方案1：首先是這一天，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中。注意到IP是32位的，最多有個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計，然后再找出頻率最大的幾個）及相應(yīng)的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。

4.僵尸進(jìn)程產(chǎn)生的原因及解決方式：

如果子進(jìn)程先于父進(jìn)程退出， 同時父進(jìn)程又沒有調(diào)用wait/waitpid，則該子進(jìn)程將成為僵尸進(jìn)程。通過ps命令，我們可以看到該進(jìn)程的狀態(tài)為Z(表示僵死)。

一般，為了防止產(chǎn)生僵尸進(jìn)程，在fork子進(jìn)程之后我們都要wait它們；同時，當(dāng)子進(jìn)程退出的時候，內(nèi)核都會給父進(jìn)程一個SIGCHLD信號，所以我們可以建立一個捕獲SIGCHLD信號的信號處理函數(shù)，在函數(shù)體中調(diào)用wait（或waitpid），就可以清理退出的子進(jìn)程以達(dá)到防止僵尸進(jìn)程的目的。

給你一個長度為N的鏈表。N很大，但你不知道N有多大。你的任務(wù)是從這N個元素中隨機(jī)取出k個元素。你只能遍歷這個鏈表一次。你的算法必須保證取出的元素恰好有k個，且它們是完全隨機(jī)的（出現(xiàn)概率均等）。

解：先選中前k個， 從第k+1個元素到最后一個元素為止， 以k/i (i=k+1, k+2,...,N)的概率選中第i個元素，并且隨機(jī)替換掉一個原先選中的元素，這樣遍歷一次得到k個元素， 可以保證完全隨機(jī)選取。這個算法叫做蓄水池抽樣

有20個數(shù)組，每個數(shù)組里面有500個數(shù)組，降序排列，每個數(shù)字是32位的unit,求出這10000個數(shù)字中最大的500個。

將 20 個數(shù)組合并為 1 個，挨著連接起來即可，不必保證有序。在合并的數(shù)組中隨機(jī)選取一個元素，然后將所有小于此元素的元素放在其左側(cè)，大于到右側(cè)。完成操作后，如果原來被選中的元素剛好處在右數(shù)第 500 的位置，那從它開始向右的元素即為所求。否則，如果右端元素數(shù)目大于 500，則對右端序列遞歸使用此方法；否則，如果左端序列數(shù)目大于 10000-500，則對左端序列遞歸使用此方法。復(fù)雜度 expected O(n)

在一個數(shù)組中除兩個數(shù)字只出現(xiàn)1次外，其它數(shù)字都出現(xiàn)了2次， 要求盡快找出這兩個數(shù)字。

位操作方法

單鏈表：

找出單鏈表的倒數(shù)第4個元素：建立兩個指針，第一個先走4步，然后第2個指針也開始走，兩個指針步伐（前進(jìn)速度）一致。

從無頭單鏈表中刪除節(jié)點：這里采用了“移花接木”的方法。設(shè)該節(jié)點為B，下一個節(jié)點為C。那么，首先將B節(jié)點的內(nèi)容替換為C節(jié)點的內(nèi)容，然后，將C節(jié)點刪除

判斷兩個鏈表是否相交并找出交點：先遍歷第一個鏈表到他的尾部，然后將尾部的next指針指向第二個鏈表(尾部指針的next本來指向的是null)。這樣兩個鏈表就合成了一個鏈表，判斷原來的兩個鏈表是否相交也就轉(zhuǎn)變成了判斷新的鏈表是否有環(huán)的問題了

找出帶環(huán)鏈表中環(huán)的起點：用兩個步長分別為1和2的指針遍歷鏈表，直到兩者相遇，此時慢指針走過的長度就是環(huán)的長度。另外相遇后把其中指針重新設(shè)定為起始點，讓兩個指針以步長1再走一遍鏈表，相遇點就是環(huán)的起始點。

單鏈表反序，并返回新鏈表的頭指針：

struct ListNode *reverseList(struct ListNode *head)
{
    struct ListNode *newHead = NULL;
    struct ListNode *tmp = NULL;
    while(head != NULL)
    {
        tmp = head;
        head = head -> next;
        tmp->next = newHead;
        newHead = tmp;
    }
    return newHead;
}

棧問題：

如何用一個數(shù)組實現(xiàn)兩個棧：分別用數(shù)組的兩端作為兩個棧的起點，向中間擴(kuò)展，兩個棧中的元素總和不超過n時，兩個棧不會相遇。

二叉樹：

找出二叉樹上任意兩個結(jié)點的最近共同父結(jié)點：首先數(shù)一下兩個結(jié)點的深度，然后比較深的那個往上走（深-淺）步，最后同時往上走，肯定會命中最近共同父節(jié)點的。如果你把二叉樹的所有節(jié)點看成N的話，我這個算法只需要lg(N)就可以搞定了

在二叉樹中找出和為某一值的所有路徑：到達(dá)一個節(jié)點之后計算當(dāng)前節(jié)點和sum的和，如果為target，輸出路徑返回，如果大于target，則直接返回，如果小于，則將當(dāng)前節(jié)點的值入棧，更新sum的值，繼續(xù)遍歷，遍歷完成之后，也就是從當(dāng)前節(jié)點返回的時候，將其從棧中彈出，更新sum

最新評論