- 相關(guān)推薦
人民搜索實(shí)習生招聘筆試題
1、打印漢諾塔移動(dòng)步驟，并且計算復雜度。
方法是遞歸，將n-1層移到中間柱，然后將最底層移到目標柱，然后再把n-1層移到目標柱。
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、計算兩個(gè)字符串的是否相似(字符的種類(lèi)，和出現次數相同)
3、定義二叉樹(shù)，節點(diǎn)值為int，計算二叉樹(shù)中的值在[a,b]區間的節點(diǎn)的個(gè)數。
任意一種方式遍歷二叉樹(shù)，如果值在 [a，b] 之間，計數器+1
4、一條路有k可坑，每次能跳平方數步長(cháng)(1 4 9 16。。)，不能跳到坑里，從a跳到b最少幾步?(動(dòng)態(tài)規劃題)
動(dòng)態(tài)轉移方程
f(n) = min( f(大于n的第一個(gè)平方數 -n) ，f(n- 小于n的第一個(gè)完全平方數) +1 )
【 補充 ing
在一個(gè)坐標軸上， 給定兩個(gè)點(diǎn)，一個(gè)起點(diǎn)，一個(gè)終點(diǎn)，起點(diǎn)有一個(gè)方塊，方塊可以左右移動(dòng)，但是移動(dòng)的長(cháng)度只能是平方數長(cháng)(1,4,9,16 ••••) ，同時(shí)坐標軸上還有洞，移動(dòng)的過(guò)程中不能越過(guò)這個(gè)洞，不然會(huì )掉下去，問(wèn) 由起點(diǎn)到終點(diǎn) 至少需要多少次移動(dòng)，不能到達返回-1】
5、給一個(gè)整數數組，求數組中重復出現次數大于數組總個(gè)數一半的數。
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)制流的數目。
如果只是一個(gè)128bit的流，那就用int對其某個(gè)字節，然后移位比較，然后int向后移動(dòng)3個(gè)字節，繼續移位比較。如果是很多128bit的流，可以模仿kmp，用上面的方法，每次取int的8bit和目標8bit進(jìn)行AND操作，結果只有256種可能，事先存一個(gè)256的表，查表決定向后跳躍的bit數。
7、交換整型的奇數位和偶數位
問(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、試著(zhù)用最小的比較次數去尋找數組中的最大值和最小值。
解法一：
掃描一次數組找出最大值;再掃描一次數組找出最小值。
比較次數2N-2
解法二：
將數組中相鄰的兩個(gè)數分在一組， 每次比較兩個(gè)相鄰的數，將較大值交換至這兩個(gè)數的左邊，較小值放于右邊。
對大者組掃描一次找出最大值，對小者組掃描一次找出最小值。
比較1.5N-2次，但需要改變數組結構
解法三：
每次比較相鄰兩個(gè)數，較大者與MAX比較，較小者與MIN比較，找出最大值和最小值。
方法如下：先將一對元素互相進(jìn)行比較，然后把最小值跟當前最小值進(jìn)行比較，把最大值跟當前最大值進(jìn)行比較。因此每?jì)蓚�(gè)元素需要3次比較。如果n為奇數，那么比較的次數是3*(n/2)次比較。如果n為偶數，那么比較的次數是3n/2-2次比較。因此，不管是n是奇數還是偶數，比較的次數至多是3*(n/2)，具體的代碼如下：
void GetMaxAndMin(int *arr , int n , int &max , int &min)
{
int i = 0 ;
if(n & 1) // 奇數
{
max = min = arr[i++];
}
else
{
if(arr[0] > arr[1])
{
max = arr[0];
min = arr[1];
}
else
{
max = arr[1];
min = arr[0];
}
i += 2;
}
for( ; i < n ; i += 2)
{
if(arr[i] > arr[i+1])
{
if(arr[i] > max)
max = arr[i];
if(arr[i+1] < min)
min = arr[i+1];
}
else
{
if(arr[i+1] > max)
max = arr[i+1];
if(arr[i] < min)
min = arr[i];
}
}
}
【人民搜索實(shí)習生招聘筆試題】相關(guān)文章：
人民銀行招聘筆試題07-25
人民銀行招聘筆試題07-31
208年人民銀行招聘試題02-12
2016阿里實(shí)習生招聘筆試題08-04
中國人民銀行招聘試題07-30
中國人民銀行招聘筆試題07-11
中國人民銀行招聘筆試題02-18
深創(chuàng )投實(shí)習生招聘筆試題目08-10
中國人民銀行招聘筆試題302-24