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

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

題目描述：

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

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

方法一：分治法

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

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

方法二：map法

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

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

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

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

方法三：trie樹法

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

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

2.

題目描述：

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

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

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

00000000對(duì)應(yīng)位圖最后一位：0x0000…000001。

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

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

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

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

(1)通過P/32就可以計(jì)算出該電話號(hào)碼在bitmap數(shù)組的下標(biāo)(因?yàn)槊總€(gè)整數(shù)占用32bit，通過這個(gè)公式就可以確定這個(gè)電話號(hào)碼需要移動(dòng)多少個(gè)32位，也就是可以確定它對(duì)應(yīng)的bit在數(shù)組中的位置)。

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

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

packagemain

import(

"strconv"

"fmt"

)

varbitmap[]int

funcphoneToBit(phoneint)

{

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

//bitmap表示申請(qǐng)的位圖

}

funcmain(){

fmt.Println()

}[考點(diǎn)]如何統(tǒng)計(jì)不同電話號(hào)碼的個(gè)數(shù)

3.

題目描述：

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

方法一：雙堆法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

方法二：分治法

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

(1)對(duì)于讀取到的數(shù)字num，如果它對(duì)應(yīng)的二進(jìn)制中最高位為1則把這個(gè)數(shù)字寫入到f1中，如果最高位是0則寫入到f0中。通過這一步就可以把這5億個(gè)數(shù)字劃分成了兩部分，而且f0中的數(shù)字都大于f1中的數(shù)字(因?yàn)樽罡呶皇欠?hào)位)。

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

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

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

4.

題目描述：

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

方法一：map法

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

方法二：分治法

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

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

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

5.

題目描述：

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

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

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

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

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

packagemain

import(

"fmt"

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

)

typeDataWithSourcestruct{

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

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

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

}

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

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

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

ifp.value＞o.value{

return-1

}elseifp.value＜o(jì).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)

//