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

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

題目描述：

現(xiàn)有海量日志數(shù)據(jù)保存在一個(gè)超級(jí)大的文件中，該文件無法直接讀入內(nèi)存，要求從中提取某天訪問百度次數(shù)最多的那個(gè)IP。正確答案：由于這道題只關(guān)心（江南博哥）某一天訪問百度最多的IP，因此可以首先對(duì)文件進(jìn)行一次遍歷，把這一天訪問百度的IP的相關(guān)信息記錄到一個(gè)單獨(dú)的文件中。接下來可以用上一節(jié)介紹的方法來求解。由于求解思路是一樣的，這里就不再詳細(xì)介紹了。唯一需要確定的是把一個(gè)大文件分為幾個(gè)小文件比較合適。以IPv4為例，由于一個(gè)IP地址占用32位，因此最多會(huì)有232=4G種取值情況。如果使用hash(IP)%1024，那么把海量IP日志分別存儲(chǔ)到1024個(gè)小文件中。這樣，每個(gè)小文件最多包含4MB個(gè)IP地址。如果使用2048個(gè)小文件，那么每個(gè)文件會(huì)最多包含2MB個(gè)IP地址。因此，對(duì)于這類題目而言，首先需要確定可用內(nèi)存的大小，然后確定數(shù)據(jù)的大小。由這兩個(gè)參數(shù)就可以確定hash函數(shù)應(yīng)該怎么設(shè)置才能保證每個(gè)文件的大小都不超過內(nèi)存的大小，從而可以保證每個(gè)小的文件都能被一次性加載到內(nèi)存中。[考點(diǎn)]如何找出訪問百度最多的IP

2.

題目描述：

把一個(gè)含有N個(gè)元素的數(shù)組循環(huán)右移k(k是正數(shù))位，要求時(shí)間復(fù)雜度為O(n)，且只允許使用兩個(gè)附加變量。正確答案：由于有空間復(fù)雜度的要求，因此，只能在原數(shù)組中就地進(jìn)行右移。

方法一：蠻力法

蠻力法也是最簡單的方法，題目中需要將數(shù)組元素循環(huán)右移k位，只需要每次將數(shù)組中的元素右移一位，循環(huán)k次即可。例如，假設(shè)原數(shù)組為abcd1234，那么，按照此種方式，具體移動(dòng)過程如下：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。

此種方法也很容易寫出代碼。示例代碼如下：

packagemain

import(

"fmt"

)

funcrightShiftl(arr[]int,kint){

ifarr==nil{

fmt.Println("參數(shù)不合法")

return

}

ll:=len(arr)

fork!=0{

k--

tmp:=arr[ll-1]

fori:=ll-1;i＞0;i--{

arr[i]=arr[i-1]

}

art[0]=tmp

}

}

funcmain(){

arr:=[]int{1,2,3,4,5,6,7,8}

rightShift1(arr,4)

fmt.Println("方法1")

for_,v:=rangearr{

fmt.Print(v,"")

}

}

程序的運(yùn)行結(jié)果為

56781234

以上方法雖然可以實(shí)現(xiàn)數(shù)組的循環(huán)右移，但是由于每移動(dòng)一次，其時(shí)間復(fù)雜度就為O(n)，所以，移動(dòng)k次，其總的時(shí)間復(fù)雜度為O(k*n)，0＜k＜n，與題目要求的O(n)不符合，需要繼續(xù)往下探索。

對(duì)于上述代碼，需要考慮到，k不一定小于n，有可能等于n，也有可能大于n。當(dāng)k＞n時(shí)，右移k-n之后的數(shù)組序列跟右移k位的結(jié)果一樣，所以，當(dāng)k＞n時(shí)，右移k位與右移k'(其中k'=k%n)位等價(jià)，根據(jù)以上分析，相對(duì)完備的代碼如下：

funcrightShift2(arr[]int,kint){

ifarr==nil{

fmt.Println("參數(shù)不合法")

return

}

ll:=len(arr)

k%=ll

fork!=0{

k--

t:=arr[ll-1]

fori:=ll-1;i＞0;i--{

arr[i]=arr[i-1]

}

arr[0]=t

}

}

算法性能分析：

上例中，算法的時(shí)間復(fù)雜度為O(n2)，與k值無關(guān)，但時(shí)間復(fù)雜度仍然太高，是否還有其他更好的方法呢?

仔細(xì)分析上面的方法，不難發(fā)現(xiàn)，上述方法的移動(dòng)采取的是一步一步移動(dòng)的方式，可是問題是，題目中已經(jīng)告知了需要移動(dòng)的位數(shù)為k，為什么不能一步到位呢?

方法二：空間換時(shí)間法

通常情況下，以空間換時(shí)間往往能夠降低時(shí)間復(fù)雜度，本題也不例外。

首先定義一個(gè)輔助數(shù)組T，把數(shù)組A的第n-k+1到N位數(shù)組中的元素存儲(chǔ)到輔助數(shù)組T中，然后再把數(shù)組A中的第1到n-k位數(shù)組元素存儲(chǔ)到輔助數(shù)組T中，然后將數(shù)組T中的元素復(fù)制回?cái)?shù)組A，這樣就完成了數(shù)組的循環(huán)右移，此時(shí)的時(shí)間復(fù)雜度為O(n)。

雖然時(shí)間復(fù)雜度滿足要求，但是空間復(fù)雜度卻提高了，由于需要?jiǎng)?chuàng)建一個(gè)新的數(shù)組，所以，此時(shí)的空間復(fù)雜度為O(n)，鑒于此，還可以對(duì)此方法繼續(xù)優(yōu)化。

方法三：翻轉(zhuǎn)法

把數(shù)組看成由兩段組成的，記為XY。左旋轉(zhuǎn)相當(dāng)于要把數(shù)組XY變成YX。先在數(shù)組上定義一種翻轉(zhuǎn)的操作，就是翻轉(zhuǎn)數(shù)組中數(shù)字的先后順序。把X翻轉(zhuǎn)后記為XT。顯然有(XT)T=X。

首先對(duì)X和Y兩段分別進(jìn)行翻轉(zhuǎn)操作，這樣就能得到XTYT。接著再對(duì)XTYT進(jìn)行翻轉(zhuǎn)操作，得到(XTYT)T=(YT)T(XT)T=YX。正好是期待的結(jié)果。

回到原來的題目。要做的僅僅是把數(shù)組分成兩段，再定義一個(gè)翻轉(zhuǎn)子數(shù)組的函數(shù)，按照前面的步驟翻轉(zhuǎn)三次就行了。時(shí)間復(fù)雜度和空間復(fù)雜度都合乎要求。

對(duì)于數(shù)組序列A={123456}，如何實(shí)現(xiàn)對(duì)其循環(huán)右移2位的功能呢?將數(shù)組A分成兩個(gè)部分：A[0～n-k-1]和A[n-k～n-1]，將這兩個(gè)部分分別翻轉(zhuǎn)，然后放在一起再翻轉(zhuǎn)(反序)。具體是這樣的：

(1)翻轉(zhuǎn)12341：123456---＞432156。

(2)翻轉(zhuǎn)56：432156---＞432165。

(3)翻轉(zhuǎn)432165：432165---＞561234。

示例代碼如下：

funcreverse(arr[]int,start,endint){

forstart＜end{

tmp:=arr[start]

arr[start]=arr[end]

arr[end]=tmp

start++

end--

}

}

funcrightShift3(arr[]int,kint){

ifarr==nil{

fmt.Println("參數(shù)不合法")

return

}

ll:=len(arr)

k%=ll

reverse(arr,0,ll-k-1)

reverse(arr,ll-k,ll-1)

reverse(arr,0,ll-1)

}

算法性能分析：

此時(shí)的時(shí)間復(fù)雜度為O(n)。主要是完成翻轉(zhuǎn)(逆序)操作，并且只用了一個(gè)輔助空間。[考點(diǎn)]如何對(duì)數(shù)組進(jìn)行循環(huán)移位

3.

題目描述：

何判斷一個(gè)數(shù)是否為2的n次方?正確答案：方法一：構(gòu)造法

2的n次方可以表示為：2^0，2^1，2^2…，2^n，如果一個(gè)數(shù)是2的n次方，那么最直觀的想法是對(duì)1執(zhí)行了移位操作(每次左移一位)，即通過移位得到的值必定是2的n次方(針對(duì)n的所有取值構(gòu)造出所有可能的值)。所以，要想判斷一個(gè)數(shù)是否為2的n次方，只需要判斷該數(shù)移位后的值是否與給定的數(shù)相等，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//判斷n能否表示成2的n次方

funcisPower1(nint)bool{

if(n＜1){

returnfalse

}

fori:=1;i＜n;{

if(i==n){

returntrue

}

i＜＜=1

}

returnfalse

}

funcmain(){

fmt.Println("方法一")

ifisPower1(8){

fmt.Println("8能表示成2的n次方")

}else{

fmt.Println("8不能表示成2的n次方")

}

ifisPower1(9){

fmt.Println("9能表示成2的n次方")

}else{

fmt.Println("9不能表示成2的n次方")

}

}

程序的運(yùn)行結(jié)果為

8能表示成2的n次方

9不能表示成2的n次方

算法性能分析：

上述算法的時(shí)間復(fù)雜度為O(logn)。

方法二：與操作法

那么是否存在效率更高的算法呢?通過對(duì)2^0，2^1，2^2，…，2^n進(jìn)行分析，發(fā)現(xiàn)這些數(shù)字的二進(jìn)制形式分別為：1，10，100，…。從二進(jìn)制的表示可以看出，如果一個(gè)數(shù)是2的n次方，那么這個(gè)數(shù)對(duì)應(yīng)的二進(jìn)制表示中有且只有一位是1，其余位都為0。因此，判斷一個(gè)數(shù)是否為2的n次方可以轉(zhuǎn)換為這個(gè)數(shù)對(duì)應(yīng)的二進(jìn)制表示中是否只有一位為1。如果一個(gè)數(shù)的二進(jìn)制表示中只有一位是1，例如num=00010000，那么num-1的二進(jìn)制表示為num-1=00001111，由于num與num-1二進(jìn)制表示中每一位都不相同，因此，num&(num-1)的運(yùn)算結(jié)果為0?？梢岳眠@種方法來判斷一個(gè)數(shù)是否為2的n次方。實(shí)現(xiàn)代碼如下：

funcisPower2(nint)bool{

if(n＜1){

returnfalse

}

returnn&(n-1)==0

}

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(1)。[考點(diǎn)]何判斷一個(gè)數(shù)是否為2的n次方

4.

題目描述：

如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算正確答案：本題要求只能使用++操作來實(shí)現(xiàn)加減乘除運(yùn)算，下面重點(diǎn)介紹用++操作來實(shí)現(xiàn)加減乘除運(yùn)算的方法：

(1)加法操作：實(shí)現(xiàn)a+b的基本思路為對(duì)a執(zhí)行b次++操作即可。

(2)減法操作：實(shí)現(xiàn)a-b(a＞=b)的基本思路為：不斷對(duì)b執(zhí)行++操作，直到等于a為止，在這個(gè)過程中記錄執(zhí)行++操作的次數(shù)。

(3)乘法操作：實(shí)現(xiàn)a*b的基本思路為：利用已經(jīng)實(shí)現(xiàn)的加法操作把a(bǔ)相加b次，就得到了a*b的值。

(4)除法操作：實(shí)現(xiàn)a/b的基本思路為：利用乘法操作，使b不斷乘以1，2，…，n，直到b*n＞b時(shí)，就可以得到商為n-1。

根據(jù)以上思路，實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

)

//用++實(shí)現(xiàn)加法操作(限制條件：至少有一個(gè)非負(fù)數(shù))

funcadd(a,bint)int{

ifa＜0&&b＜0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

ifb＞=0{

fori:=0;i＜b;i++{

a++

}

returna

}else{

fori:=0;i＜a;i++{

b++

}

returnb

}

}

//用++實(shí)現(xiàn)加減法操作(限制條件：被減數(shù)大于減數(shù))

funcminus(a,bint)int{

if(a＜b){

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=0

for;b!=a;b++{

result++

}

returnresult

}

//用++實(shí)現(xiàn)加乘法操作(限制條件：兩個(gè)數(shù)都為整數(shù))

funcmulti(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=0

fori:=0;i＜b;i++{

result=add(result,a)

}

returnresult

}

//用++實(shí)現(xiàn)加法除法操作(限制條件：兩個(gè)數(shù)都為整數(shù))

funcdivide(a,bint)int{

ifa＜=0||b＜=0{

fmt.Println("無法用++操作實(shí)現(xiàn)")

return-1

}

result:=1

tmpMulti:=0

fortrue{

tmpMulti=multi(b,result)

iftmpMulti＜=a{

result++

}else{

break

}

}

returnresult-1

}

funcmain(){

fmt.Println(add(2,-4))

fmt.Println(minus(2,-4))

fmt.Println(multi(2,4))

fmt.Println(divide(9,4))

}

程序的運(yùn)行結(jié)果為

-2

6

8

2

此處，在實(shí)現(xiàn)加法操作的時(shí)候，如果a與b都是整數(shù)，那么可以選擇比較小的數(shù)進(jìn)行循環(huán)，從而可以提高算法的性能。[考點(diǎn)]如何只使用++操作符實(shí)現(xiàn)加減乘除運(yùn)算

5.

題目描述：

給定一個(gè)數(shù)d和n，如何計(jì)算d的n次方?例如：d=2，n=3，d的n次方為2^3=8。正確答案：方法一：蠻力法

可以把n的取值分為如下幾種情況：

(1)n=0，那么計(jì)算結(jié)果肯定為1。

(2)n=1，計(jì)算結(jié)果肯定為d。

(3)n＞0，計(jì)算方法為：初始化計(jì)算結(jié)果result=1，然后對(duì)result執(zhí)行n次乘以d的操作，得到的結(jié)果就是d的n次方。

(4)n＜0，計(jì)算方法為：初始化計(jì)算結(jié)果result=1，然后對(duì)result執(zhí)行|n|次除以d的操作，得到的結(jié)果就是d的n次方。

以2的三次方為例，首先初始化result=1，接著對(duì)result執(zhí)行三次乘以2的操作：result=result*2=1*2=2，result=result*2=2*2=4，result=result*2=4*2=8，因此，2的三次方等于8。根據(jù)這個(gè)思路給出實(shí)現(xiàn)代碼如下：

packagemain

import(

"fmt"

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

)

fimcpower1(dfloat64,nint)float64{

if(n==0){return1}

if(n==1){returnd}

result:=1.0

ifn＞0{

fori:=1;i＜=n;i++{

result*=d

)

returnresult

}else{

fori:=1;i＜=Abs(n);i++{

result=result/d

}

}

returnresult

}

funcmain(){

fmt.Println("方法一")

fmt.Println(power1(2,3))

fmt.Println(power1(-2,3))

fmt.Println(power1(2,-3))

}

程序的運(yùn)行結(jié)果為

8

-8

0.125

算法性能分析：

這種方法的時(shí)間復(fù)雜度為O(n)，需要注意的是，當(dāng)n非常大的時(shí)候，這種方法的效率是非常低下的。

方法二：