人民搜索实习生招聘笔试题

[结构化面试题型]结构化面试题型结构化面试只要考生在考前有一个充分的准备，面试成绩是可以迅速提高的。但要想在面试中取得好成绩，就必须对结构化面试的各种题型及其解题思路有一个清晰的把...+阅读

1、打印汉诺塔移动步骤，并且计算复杂度。

方法是递归，将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、计算两个字符串的是否相似(字符的种类，和出现次数相同)

3、定义二叉树，节点值为int，计算二叉树中的值在[a,b]区间的节点的个数。

任意一种方式遍历二叉树，如果值在 [a，b] 之间，计数器+1

4、一条路有k可坑，每次能跳平方数步长(1 4 9 16。。)，不能跳到坑里，从a跳到b最少几步?(动态规划题)

动态转移方程

f(n) = min( f(大于n的第一个平方数 -n) ，f(n- 小于n的第一个完全平方数) +1 )

【补充 ing

在一个坐标轴上，给定两个点，一个起点，一个终点，起点有一个方块，方块可以左右移动，但是移动的长度只能是平方数长(1,4,9,16 ) ，同时坐标轴上还有洞，移动的过程中不能越过这个洞，不然会掉下去，问由起点到终点至少需要多少次移动，不能到达返回-1】

5、给一个整数数组，求数组中重复出现次数大于数组总个数一半的数。

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; 没有找到

else

return num; 找到

}

6、一个128bits 的二进制流，要求找出里面包含某8bits 二进制流的数目。

如果只是一个128bit的流，那就用int对其某个字节，然后移位比较，然后int向后移动3个字节，继续移位比较。如果是很多128bit的流，可以模仿kmp，用上面的方法，每次取int的8bit和目标8bit进行AND操作，结果只有256种可能，事先存一个256的表，查表决定向后跳跃的bit数。

7、交换整型的奇数位和偶数位

问题定义：

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、试着用最小的比较次数去寻找数组中的最大值和最小值。

解法一：

扫描一次数组找出最大值;再扫描一次数组找出最小值。

比较次数2N-2

解法二：

将数组中相邻的两个数分在一组，每次比较两个相邻的数，将较大值交换至这两个数的左边，较小值放于右边。

对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。

比较1.5N-2次，但需要改变数组结构

解法三：

每次比较相邻两个数，较大者与MAX比较，较小者与MIN比较，找出最大值和最小值。

方法如下：先将一对元素互相进行比较，然后把最小值跟当前最小值进行比较，把最大值跟当前最大值进行比较。因此每两个元素需要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];

}