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

1、人民搜索实习生招聘笔试题1、打印汉诺塔移动步骤，并且计算复杂度。方法是递归，将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、计算两个字符串的是否相似(字符的种类，和出现次数相同)3、定义二叉树，节点值为int,计算二叉树中的值在a,b区间 的节点的个数。任意一种方式遍历二叉树，如果值在a , b之间，计数器+14、一条路有k可坑，每次能跳平方数步长(1 4916OO ),不能 跳到坑里，从a跳到b最少几步?(动态规划题)动

2、态转移方程f(n) = min( f(大于n的第一个平方数-n) z f(n-小于n的第个完全平方数)+1)【补充ing在一个坐标轴上，给定两个点，一个起点，一个终点，起点有 个方块，方块可以左右移动，但是移动的长度只能是平方数长 (149,16 ),同时坐标轴上还有洞，移动的过程中不能越过这个洞, 不然会掉下去，问由起点到终点至少需要多少次移动，不能到达返 0-15、给一个整数数组，求数组中重复出现次数大于数组总个数一 半的数。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二 进制流的数目。如果只是一个128bit的流，那就用int对其某个字节，然后移 位匕交，然后int向后移动3个字节，继续移位比较。如果是很多 128bit的流，可以模仿kmp ,用上面的方法，每次取int的8bit和 目标8bit进行AND操作，结果只有256种可能，事先存一个256 的

4、表，查表决定向后跳跃的bit数。7、交换整型的奇数位和偶数位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、试着用最小的比较次数去

5、寻找数组中的最大值和最小值。解法:1/1每次比较相邻两个数，较大者及MAX比较，较小者及MIN比比较次数2N-2解法二:将数组中相邻的两个数分在一组,每次比较两个相邻的数，将 较大值交换至这两个数的左边，较小值放于右边。对大者组扫描一次找出最大值，对小者组扫描一次找出最小值。比较1.5N-2次，但需要改变数组结构解法三:较，找出最大值和最小值。方法如下：先将一对元素互相进行比较，然后把最小值跟当前 最小值进行t匕较，把最大值跟当前最大值进行比较。因此每两个元素 需要3次比较。如果n为奇数，那么比较的次数是3*(n/2)次比较。 如果n为偶数，那么t匕较的次数是3n/2-2次比较。因此，不管是n 是奇数还是偶数，比较的次数至多是3*(n/2),具体的代码如下：void GetMaxAndMin(int *arr, int n , int max , int min) if(n 1)/ 奇数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