人民搜索實(shí)習(xí)生招聘筆試題

1、人民搜索實(shí)習(xí)生招聘筆試題1、打印漢諾塔移動(dòng)步驟，并且計(jì)算復(fù)雜度。方法是遞歸，將n-1層移到中間柱，然后將最底層移到目標(biāo)柱, 然后再把n-1層移到目標(biāo)柱。f(n) = 2f(n-l) + 1, f(l) = 1 f(n) + 1 = 2( f(n-l) + 1) f(n)0(2T(n)1/1);2、計(jì)算兩個(gè)字符串的是否相似(字符的種類，和出現(xiàn)次數(shù)相同)3、定義二叉樹(shù)，節(jié)點(diǎn)值為int,計(jì)算二叉樹(shù)中的值在a,b區(qū)間 的節(jié)點(diǎn)的個(gè)數(shù)。任意一種方式遍歷二叉樹(shù)，如果值在a , b之間，計(jì)數(shù)器+14、一條路有k可坑，每次能跳平方數(shù)步長(zhǎng)(1 4916OO ),不能 跳到坑里，從a跳到b最少幾步?(動(dòng)態(tài)規(guī)劃題)動(dòng)

2、態(tài)轉(zhuǎn)移方程f(n) = min( f(大于n的第一個(gè)平方數(shù)-n) z f(n-小于n的第個(gè)完全平方數(shù))+1)【補(bǔ)充ing在一個(gè)坐標(biāo)軸上，給定兩個(gè)點(diǎn)，一個(gè)起點(diǎn)，一個(gè)終點(diǎn)，起點(diǎn)有 個(gè)方塊，方塊可以左右移動(dòng)，但是移動(dòng)的長(zhǎng)度只能是平方數(shù)長(zhǎng) (149,16 ),同時(shí)坐標(biāo)軸上還有洞，移動(dòng)的過(guò)程中不能越過(guò)這個(gè)洞, 不然會(huì)掉下去，問(wèn)由起點(diǎn)到終點(diǎn)至少需要多少次移動(dòng)，不能到達(dá)返 0-15、給一個(gè)整數(shù)數(shù)組，求數(shù)組中重復(fù)出現(xiàn)次數(shù)大于數(shù)組總個(gè)數(shù)一 半的數(shù)。int MoreThanHalfNum(int *a , int n )1 /1int i z k # num = a0;int times = 1;for(i =

3、l;i +i)num = ai;times = 1;i/ielse if(ai != num)times;+ +times;k = 0;for(i = 0;i+i)if(k*2 = n)return/沒(méi)有找到else return num; 找至I6、一個(gè)128bits的二進(jìn)制流，要求找出里面包含某8bits二 進(jìn)制流的數(shù)目。如果只是一個(gè)128bit的流，那就用int對(duì)其某個(gè)字節(jié)，然后移 位匕交，然后int向后移動(dòng)3個(gè)字節(jié)，繼續(xù)移位比較。如果是很多 128bit的流，可以模仿kmp ,用上面的方法，每次取int的8bit和 目標(biāo)8bit進(jìn)行AND操作，結(jié)果只有256種可能，事先存一個(gè)256 的

4、表，查表決定向后跳躍的bit數(shù)。7、交換整型的奇數(shù)位和偶數(shù)位1 /1Write a program to s and even bits in an integer with as few instructions as possible(e.gz bit 0 and bit 1 are s, bit 2 and bit 3 are s, etc)int S(int x) return (x Oxaaaaaaaa) 1) | (x 0x55555555) 1); int main(void)int a = 171;printf( %dn, S(a);return 0;8、試著用最小的比較次數(shù)去

5、尋找數(shù)組中的最大值和最小值。解法:1/1每次比較相鄰兩個(gè)數(shù)，較大者及MAX比較，較小者及MIN比比較次數(shù)2N-2解法二:將數(shù)組中相鄰的兩個(gè)數(shù)分在一組,每次比較兩個(gè)相鄰的數(shù)，將 較大值交換至這兩個(gè)數(shù)的左邊，較小值放于右邊。對(duì)大者組掃描一次找出最大值，對(duì)小者組掃描一次找出最小值。比較1.5N-2次，但需要改變數(shù)組結(jié)構(gòu)解法三:較，找出最大值和最小值。方法如下：先將一對(duì)元素互相進(jìn)行比較，然后把最小值跟當(dāng)前 最小值進(jìn)行t匕較，把最大值跟當(dāng)前最大值進(jìn)行比較。因此每?jī)蓚€(gè)元素 需要3次比較。如果n為奇數(shù)，那么比較的次數(shù)是3*(n/2)次比較。 如果n為偶數(shù)，那么t匕較的次數(shù)是3n/2-2次比較。因此，不管是n 是奇數(shù)還是偶數(shù)，比較的次數(shù)至多是3*(n/2),具體的代碼如下：void GetMaxAndMin(int *arr, int n , int max , int min) if(n 1)/ 奇數(shù)1 /1max = min = arri +;elseif(arrO arrl)1/1max = arrO;min = arrl;max = arrl;min = arrO;i += 2;for(; i i + = 2)if(arri arri+l)if(arri max)max = arri