Go程序員面試分類模擬題24

Go程序員面試分類模擬題24論述題1.

題目描述：

搜索引擎會通過日志文件把用戶每次檢索使用的所有查詢串都記錄下來，每個查詢串的長度為1～255字節(jié)。

假設(shè)目前有1000萬個記錄(這些查詢（江南博哥）串的重復度比較高，雖然總數(shù)是1000萬，但如果除去重復后，不超過300萬個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門)，請統(tǒng)計最熱門的10個查詢串，要求使用的內(nèi)存不能超過1G。正確答案：從題目中可以發(fā)現(xiàn)，每個查詢串最長為255個字節(jié)，1000萬個字符串需要占用2.55G內(nèi)存，因此無法把所有的字符串全部讀入到內(nèi)存中處理。對于這類型的題目，分治法是一個非常實用的方法。

方法一：分治法

對字符串設(shè)置一個Hash函數(shù)，通過這個Hash函數(shù)把字符串劃分到更多更小的文件中，從而保證每個小文件中的字符串都可以直接被加載到內(nèi)存中處理，然后求出每個文件中出現(xiàn)次數(shù)最多的10個字符串；最后通過一個小頂堆統(tǒng)計出所有文件中出現(xiàn)最多的10個字符串。

從功能角度出發(fā)，這種方法是可行的，但是由于需要對文件遍歷兩遍，而且Hash函數(shù)也需要被調(diào)用1000萬次，所以性能不是很好，針對這道題的特殊性，下面介紹另外一種性能較好的方法。

方法二：map法

雖然字符串的總數(shù)比較多，但是字符串的種類不超過300萬個，因此可以考慮把所有字符串出現(xiàn)的次數(shù)保存在一個map中(鍵為字符串，值為字符串出現(xiàn)的次數(shù))。map所需要的空間為300萬×(255+4)=3MB×259=777MB(其中，4表示用來記錄字符串出現(xiàn)次數(shù)的整數(shù)占用4個字節(jié))。由此可見1G的內(nèi)存空間是足夠用的?；谝陨系姆治?，本題的求解思路為：

(1)遍歷字符串，如果字符串在map中不存在，則直接存入map中，鍵為這個字符串，值為1。如果字符串在map中已經(jīng)存在了，則把對應的值直接加1。這一步操作的時間復雜度為O(n)，其中n為字符串的數(shù)量。

(2)在第一步的基礎(chǔ)上找出出現(xiàn)頻率最高的10個字符串?？梢酝ㄟ^小頂堆的方法來完成，遍歷map的前10個元素，并根據(jù)字符串出現(xiàn)的次數(shù)構(gòu)建一個小頂堆，然后接著遍歷map，只要遍歷到的字符串的出現(xiàn)次數(shù)大于堆頂字符串的出現(xiàn)次數(shù)，就用遍歷的字符串替換堆頂?shù)淖址?，然后再調(diào)整為小頂堆。

(3)對所有剩余的字符串都遍歷一遍，遍歷完成后小頂堆中的10個字符串就是出現(xiàn)次數(shù)最多的字符串。這一步的時間復雜度為O(nlog10)。

方法三：trie樹法

方法二中使用map來統(tǒng)計每個字符串出現(xiàn)的次數(shù)。當這些字符串有大量相同前綴的時候，可以考慮使用trie樹來統(tǒng)計字符串出現(xiàn)的次數(shù)。可以在樹的結(jié)點中保存字符串出現(xiàn)的次數(shù)，0表示沒有出現(xiàn)。具體的實現(xiàn)方法為，在遍歷的時候，在trie樹中查找，如果找到，則把結(jié)點中保存的字符串出現(xiàn)的次數(shù)加1，否則為這個字符串構(gòu)建新的結(jié)點，構(gòu)建完成后把葉子結(jié)點中字符串的出現(xiàn)次數(shù)設(shè)置為1。這樣遍歷完字符串后就可以知道每個字符串的出現(xiàn)次數(shù)，然后通過遍歷這個樹就可以找出出現(xiàn)次數(shù)最多的字符串。

trie樹經(jīng)常被用來統(tǒng)計字符串的出現(xiàn)次數(shù)。它的另外一個用途就是字符串查找，判斷是否有重復的字符串等。[考點]如何查詢最熱門的查詢串

2.

題目描述：

已知某個文件內(nèi)包含一些電話號碼，每個號碼為8位數(shù)字，統(tǒng)計不同號碼的個數(shù)。正確答案：這個題目從本質(zhì)上而言也是求解數(shù)據(jù)重復的問題，一般而言，對于這類問題首先會考慮位圖法。對于本題而言，8位電話號碼可以表示的范圍為：00000000～99999999，如果用1bit表示一個號碼，總共需要1億個bit，大約100MB的內(nèi)存。

通過上面的分析可知，這道題的主要思路為：申請一個位圖并初始化為0，然后遍歷所有電話號碼，把遍歷到的電話號碼對應的位圖中的bit設(shè)置為1。當遍歷完成后，如果bit值為1則表示這個電話號碼在文件中存在，否則這個bit對應的電話號碼在文件中不存在。所以bit值為1的數(shù)量就是不同電話號碼的個數(shù)。

那么對于這道題而言，最核心的算法是如何確定電話號碼對應的是位圖中的哪一位。下面重點介紹這個轉(zhuǎn)化的方法，這里使用下面的對應方法。

00000000對應位圖最后一位：0x0000…000001。

00000001對應位圖倒數(shù)第二位：0x0000…0000010(1向左移一位)。

00000002對應位圖倒數(shù)第三位：0x0000…0000100(1向左移2位)。

00000012對應位圖的倒數(shù)十三位：0x0000…0001000000000000。

通常，位圖都是通過一個整數(shù)數(shù)組來實現(xiàn)的(這里假設(shè)一個整數(shù)占用4個字節(jié))。由此可以得出通過電話號碼獲取位圖中對應位置的方法為(假設(shè)電話號碼為P)：

(1)通過P/32就可以計算出該電話號碼在bitmap數(shù)組的下標(因為每個整數(shù)占用32bit，通過這個公式就可以確定這個電話號碼需要移動多少個32位，也就是可以確定它對應的bit在數(shù)組中的位置)。

(2)通過P%32就可以計算出這個電話號碼在這個整型數(shù)字中具體的bit的位置，也就是1這個數(shù)字對應的左移次數(shù)。因此可以通過把1向左移P%32位，然后將得到的值與這個數(shù)組中的值做或運算，這樣就能把這個電話號碼在位圖中對應的位設(shè)置為1。

(3)這個轉(zhuǎn)換的操作可以通過一個非常簡單的函數(shù)來實現(xiàn)：

packagemain

import(

"strconv"

"fmt"

)

varbitmap[]int

funcphoneToBit(phoneint)

{

bitmap[phone/(8*strconv.IntSize)]|=1＜＜uint(phone%(8*strconv.IntSize));

//bitmap表示申請的位圖

}

funcmain(){

fmt.Println()

}[考點]如何統(tǒng)計不同電話號碼的個數(shù)

3.

題目描述：

從5億個數(shù)中找出中位數(shù)。數(shù)據(jù)排序后，位置在最中間的數(shù)值就是中位數(shù)。當樣本數(shù)為奇數(shù)時，中位數(shù)=(N+1)/2；當樣本數(shù)為偶數(shù)時，中位數(shù)為N/2與1+N/2的均值。正確答案：如果這道題目沒有內(nèi)存大小的限制，可以把所有的數(shù)字排序后找出中位數(shù)，但是最好的排序算法的時間復雜度都是O(nlogn)(n為數(shù)字的個數(shù))。這里介紹另外一種求解中位數(shù)的算法：雙堆法。

方法一：雙堆法

這種方法的主要思路是維護兩個堆，一個大頂堆，一個小頂堆，且這兩個堆需要滿足如下兩個特性：

特性一：大頂堆中最大的數(shù)值小于等于小頂堆中最小的數(shù)。

特性二：保證這兩個堆中的元素個數(shù)的差不能超過1。

在數(shù)據(jù)總數(shù)為偶數(shù)的時候，當這兩個堆建立好以后，中位數(shù)顯然就是兩個堆頂元素的平均值。當數(shù)據(jù)總數(shù)為奇數(shù)的時候，根據(jù)兩個堆的大小，中位數(shù)一定在數(shù)據(jù)多的堆的堆頂。對于本題而言，具體實現(xiàn)思路為：維護兩個堆maxHeap與minHeap，這兩個堆的大小分別為max_size和min_size。然后開始遍歷數(shù)字。對于遍歷到的數(shù)字data：

(1)如果data＜maxHeap的堆頂元素，此時為了滿足特性一，只能把data插入到maxHeap中。為了滿足特性二，需要分以下幾種情況討論。

1)如果max_size＜=min_size，說明大頂堆元素個數(shù)小于小頂堆元素個數(shù)，此時把data直接插入大頂堆中，并把這個堆調(diào)整為大頂堆。

2)如果max_size＞min_size，為了保持兩個堆元素個數(shù)的差不超過1，此時需要把maxHeap堆頂?shù)脑匾苿拥絤inHeap中，接著把data插入到maxHeap中。同時通過對堆的調(diào)整分別讓兩個堆保持大頂堆與小頂堆的特性。

(2)如果maxHeap堆頂元素＜=data＜=minHeap堆頊元素，為了滿足特性一，此時可以把data插入任意一個堆中，為了滿足特性二，需要分以下幾種情況討論：

1)如果max_size＜min_size，顯然需要把data插入到maxHeap中。

2)如果max_size＞min_size，顯然需要把data插入到minHeap中。

3)如果max_size==min_size，可以把data插入到任意一個堆中。

(3)如果data＞maxHeap的堆頂元素，此時為了滿足特性一，只能把data插入到。minHeap中。為了滿足特性二，需要分以下幾種情況討論。

1)如果max_size＞=min_size，那么把data插入到minHeap中。

2)如果max_size＜min_size，那么需要把minHeap堆頂元素移到maxHeap中，然后把data插入到minHeap中。

通過上述方法可以把5億個數(shù)構(gòu)建兩個堆，兩個堆頂元素的平均值就是中位數(shù)。

這種方法由于需要把所有的數(shù)據(jù)都加載到內(nèi)存中，當數(shù)據(jù)量很大的時候，由于無法把數(shù)據(jù)一次性加載到內(nèi)存中，因此這種方法比較適用于數(shù)據(jù)量小的情況。對于本題而言，5億個數(shù)字，每個數(shù)字在內(nèi)存中占4B，5億個數(shù)字需要的內(nèi)存空間為2GB內(nèi)存。如果可用的內(nèi)存不足2G的時候顯然不能使用這種方法，因此下面介紹另外一種方法。

方法二：分治法

分治法的核心思想為把一個大的問題逐漸轉(zhuǎn)換為規(guī)模較小的問題來求解。對于本題而言，順序讀取這5億個數(shù)字：

(1)對于讀取到的數(shù)字num，如果它對應的二進制中最高位為1則把這個數(shù)字寫入到f1中，如果最高位是0則寫入到f0中。通過這一步就可以把這5億個數(shù)字劃分成了兩部分，而且f0中的數(shù)字都大于f1中的數(shù)字(因為最高位是符號位)。

(2)通過上面的劃分可以非常容易地知道中位數(shù)是在f0中還是在f1中，假設(shè)f1中有1億個數(shù)，那么中位數(shù)一定在文件f0中從小到大是第1.5億個數(shù)與它后面的一個數(shù)求平均值。

(3)對于f0可以用次高位的二進制的值繼續(xù)把這個文件一分為二，使用同樣的思路可以確定中位數(shù)是文件中的第幾個數(shù)。直到劃分后的文件可以被加載到內(nèi)存中為止，接著把數(shù)據(jù)加載到內(nèi)存后再進行排序，從而找出中位數(shù)。

需要注意的是，這里有一種特殊情況需要考慮，當數(shù)據(jù)總數(shù)為偶數(shù)的時候，如果把文件一分為二后發(fā)現(xiàn)兩個文件中的數(shù)據(jù)有相同的個數(shù)，那么中位數(shù)就是數(shù)據(jù)比較小的文件中的最大值與數(shù)據(jù)比較大的文件中的最小值的平均值。對于求一個文件中所有數(shù)據(jù)的最大值或最小值，可以使用前面介紹的分治法進行求解。[考點]如何從5億個數(shù)中找出中位數(shù)

4.

題目描述：

有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復。要求按照quety的頻度排序。正確答案：對于這種題，如果query的重復度比較大，那么可以考慮一次性把所有query讀入到內(nèi)存中處理，如果query的重復率不高，那么可用的內(nèi)存不足以容納所有的query，那么就需要使用分治法或者其他的方法來解決。

方法一：map法

如果query的重復率比較高，說明不同的query總數(shù)比較小，可以考慮把所有的query都加載到內(nèi)存中的map中(由于map中針對每個不同的query只保存一個鍵值對，因此這些query占用的空間會遠小于10G，有希望把它們一次性都加載到內(nèi)存中)。接著就可以對map按照query出現(xiàn)的次數(shù)進行排序。

方法二：分治法

這種方法需要根據(jù)數(shù)據(jù)量的大小以及可用內(nèi)存的大小來確定問題劃分的規(guī)模。對于本題而言，可以順序遍歷10個文件中的query，通過Hash函數(shù)hash(query)%10把這些query劃分到10個文件中，通過這樣的劃分，每個文件的大小為1G左右，當然可以根據(jù)實際情況來調(diào)整Hash函數(shù)，如果可用內(nèi)存很小，可以把這些query劃分到更多的小的文件中。

如果劃分后的文件還是比較大，可以使用相同的方法繼續(xù)劃分，直到每個文件都可以被讀取到內(nèi)存中進行處理為止，然后對每個劃分后的小文件使用hash_map統(tǒng)計每個query出現(xiàn)的次數(shù)，然后根據(jù)出現(xiàn)次數(shù)排序，并把排序好的query以及出現(xiàn)次數(shù)寫入到另外一個單獨的文件中。這樣針對每個文件，都可以得到一個按照query出現(xiàn)次數(shù)排序的文件。

接著對所有的文件按照query的出現(xiàn)次數(shù)進行排序，這里可以使用歸并排序(由于無法把所有的query都讀入到內(nèi)存中，因此這里需要使用外排序)。[考點]如何按照query的頻度排序

5.

題目描述：

有20個數(shù)組，每個數(shù)組有500個元素，并且是有序排列好的，現(xiàn)在如何在這20×500個數(shù)中找出排名前500的數(shù)?正確答案：對于求topk的問題，最常用的方法為堆排序方法。對于本題而言，假設(shè)數(shù)組降序排列，可以采用如下方法：

(1)首先建立大頂堆，堆的大小為數(shù)組的個數(shù)，即20，把每個數(shù)組最大的值(數(shù)組第一個值)存放到堆中。

(2)接著刪除堆頂元素，保存到另外一個大小為500的數(shù)組中，然后向大頂堆插入刪除的元素所在數(shù)組的下一個元素。

(3)重復第(1)、(2)步驟，直到刪除個數(shù)為最大的k個數(shù)，這里為500。

為了在堆中取出一個數(shù)據(jù)后，能知道它是從哪個數(shù)組中取出的，從而可以從這個數(shù)組中取下一個值，可以把數(shù)組的指針存放到堆中，對這個指針提供比較大小的方法(比較指針指向的值)。為了便于理解，把題目進行簡化：三個數(shù)組，每個數(shù)組有5個元素且有序，找出排名前5的數(shù)。

packagemain

import(

"fmt"

."/isdamir/gotype"http://引入定義的數(shù)據(jù)結(jié)構(gòu)

)

typeDataWithSourcestruct{

valueint//數(shù)據(jù)

comeFromint//來源的數(shù)組

indexint//在數(shù)組中的index

}

//由于PriorityQueue使用小頂堆來實現(xiàn)的。這里通過修改

//兩個整數(shù)比較的邏輯來讓PriorityQueue變?yōu)橐粋€大頂堆

func(pDataWithSource)compareTo(o*DataWithSource)int{

ifp.value＞o.value{

return-1

}elseifp.value＜o.value{

return1

}else{

return0

}

}

funcNewDataWithSource(value,comFrom,indexint)*DataWithSource{

return&DataWithSource{value,comFrom,index}

}

funcgetTop(data[][]int)[]int{

rowSize:=len(data)

columnSize:=len(data[0])

result3:=make([]int,columnSize)

//