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

時(shí)間：2022-10-14 16:49:41 筆試題目我要投稿

相關(guān)推薦

　　1、打印漢諾塔移動(dòng)步驟，并且計(jì)算復(fù)雜度。

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

　　方法是遞歸，將n-1層移到中間柱，然后將最底層移到目標(biāo)柱，然后再把n-1層移到目標(biāo)柱。

　　f(n) = 2f(n-1) + 1 , f(1) = 1

　　f(n) + 1 = 2( f(n-1) + 1 )

　　f(n) = 2^n - 1

　　T(n) = O(2^n);

　　2、計(jì)算兩個(gè)字符串的是否相似(字符的種類(lèi)，和出現(xiàn)次數(shù)相同)

　　3、定義二叉樹(shù)，節(jié)點(diǎn)值為int，計(jì)算二叉樹(shù)中的值在[a,b]區(qū)間的節(jié)點(diǎn)的個(gè)數(shù)。

　　任意一種方式遍歷二叉樹(shù)，如果值在 [a，b] 之間，計(jì)數(shù)器+1

　　4、一條路有k可坑，每次能跳平方數(shù)步長(zhǎng)(1 4 9 16。。)，不能跳到坑里，從a跳到b最少幾步?(動(dòng)態(tài)規(guī)劃題)

　　動(dòng)態(tài)轉(zhuǎn)移方程

　　f(n) = min( f(大于n的第一個(gè)平方數(shù) -n) ，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)(1,4,9,16 ••••) ，同時(shí)坐標(biāo)軸上還有洞，移動(dòng)的過(guò)程中不能越過(guò)這個(gè)洞，不然會(huì)掉下去，問(wèn) 由起點(diǎn)到終點(diǎn) 至少需要多少次移動(dòng)，不能到達(dá)返回-1】

　　5、給一個(gè)整數(shù)數(shù)組，求數(shù)組中重復(fù)出現(xiàn)次數(shù)大于數(shù)組總個(gè)數(shù)一半的數(shù)。

　　int MoreThanHalfNum(int *a , int n )

　　{

　　int i , k , num = a[0];

　　int times = 1;

　　for(i = 1 ; i < n ; ++i)

　　{

　　if(times == 0)

　　{

　　num = a[i];

　　times = 1;

　　}

　　else if(a[i] != num)

　　--times;

　　else

　　++times;

　　}

　　k = 0;

　　for(i = 0 ; i < n ; ++i)

　　{

　　if(a[i] == num)

　　++k;

　　}

　　if(k*2 <= n)

　　return -1; //沒(méi)有找到

　　else

　　return num; //找到

　　}

　　6、一個(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的表，查表決定向后跳躍的bit數(shù)。

　　7、交換整型的奇數(shù)位和偶數(shù)位

　　問(wèn)題定義：

　　Write a program to swap odd and even bits in an integer with as few instructions as possible(e.g, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)

　　int SwapOddEvenBit(int x)

　　{

　　return ( ((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));

　　}

　　int main(void)

　　{

　　int a = 171;

　　printf("%d\n", SwapOddEvenBit(a));

　　return 0;

　　}

　　8、試著用最小的比較次數(shù)去尋找數(shù)組中的最大值和最小值。

　　解法一：

　　掃描一次數(shù)組找出最大值;再掃描一次數(shù)組找出最小值。

　　比較次數(shù)2N-2

　　解法二：

　　將數(shù)組中相鄰的兩個(gè)數(shù)分在一組，每次比較兩個(gè)相鄰的數(shù)，將較大值交換至這兩個(gè)數(shù)的左邊，較小值放于右邊。

　　對(duì)大者組掃描一次找出最大值，對(duì)小者組掃描一次找出最小值。

　　比較1.5N-2次，但需要改變數(shù)組結(jié)構(gòu)

　　解法三：

　　每次比較相鄰兩個(gè)數(shù)，較大者與MAX比較，較小者與MIN比較，找出最大值和最小值。

　　方法如下：先將一對(duì)元素互相進(jìn)行比較，然后把最小值跟當(dāng)前最小值進(jìn)行比較，把最大值跟當(dāng)前最大值進(jìn)行比較。因此每?jī)蓚€(gè)元素需要3次比較。如果n為奇數(shù)，那么比較的次數(shù)是3*(n/2)次比較。如果n為偶數(shù)，那么比較的次數(shù)是3n/2-2次比較。因此，不管是n是奇數(shù)還是偶數(shù)，比較的次數(shù)至多是3*(n/2)，具體的代碼如下：

　　void GetMaxAndMin(int *arr , int n , int &max , int &min)

　　{

　　int i = 0 ;

　　if(n & 1) // 奇數(shù)

　　{

　　max = min = arr[i++];

　　}

　　else

　　{

　　if(arr[0] > arr[1])

　　{

　　max = arr[0];