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

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

2、態(tài)轉(zhuǎn)移方程f(n) = min( f(大于n的第一個平方數(shù)-n) z f(n-小于n的第個完全平方數(shù))+1)【補充ing在一個坐標軸上，給定兩個點，一個起點，一個終點，起點有 個方塊，方塊可以左右移動，但是移動的長度只能是平方數(shù)長 (149,16 ),同時坐標軸上還有洞，移動的過程中不能越過這個洞, 不然會掉下去，問由起點到終點至少需要多少次移動，不能到達返 0-15、給一個整數(shù)數(shù)組，求數(shù)組中重復(fù)出現(xiàn)次數(shù)大于數(shù)組總個數(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/沒有找到else return num; 找至I6、一個128bits的二進制流，要求找出里面包含某8bits二 進制流的數(shù)目。如果只是一個128bit的流，那就用int對其某個字節(jié)，然后移 位匕交，然后int向后移動3個字節(jié)，繼續(xù)移位比較。如果是很多 128bit的流，可以模仿kmp ,用上面的方法，每次取int的8bit和 目標8bit進行AND操作，結(jié)果只有256種可能，事先存一個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每次比較相鄰兩個數(shù)，較大者及MAX比較，較小者及MIN比比較次數(shù)2N-2解法二:將數(shù)組中相鄰的兩個數(shù)分在一組,每次比較兩個相鄰的數(shù)，將 較大值交換至這兩個數(shù)的左邊，較小值放于右邊。對大者組掃描一次找出最大值，對小者組掃描一次找出最小值。比較1.5N-2次，但需要改變數(shù)組結(jié)構(gòu)解法三:較，找出最大值和最小值。方法如下：先將一對元素互相進行比較，然后把最小值跟當前 最小值進行t匕較，把最大值跟當前最大值進行比較。因此每兩個元素 需要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