发布于 2014-10-20 03:37:32 | 439 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
一面：
第一题、任意给一个数，试证明这个数的某个倍数的十进制表示是01串，比如3的倍数111是二进制表示，5的倍数10是二进制表示，等等。
假设序列1,11,111,1111…用A1~AN标识，下脚标N即为1的个数，如：A1=1,A2=11,A3=111…
其中没有一个是N的倍数，即AK mod N不等于0（K属于1~N），并且AK mod N的余数各不相同，设它们为a1,a2,a3,…,aN，但AK mod N的余数最多只有N-1个不同，则由鸽巢原理可知，a1,a2,a3,…,aN中必有两个相同，即ai=aj(j>i)，则Aj-Ai=0(mod N)，Aj-Ai即为所求的0和1组成的十进制数M，得证。
第二题、证明素数有无穷多个。
假若素数只有有限多个，设最大的一个是P，从2到P的全体素数是：
2，3，5，7，11……，P。
所有的素数都在这里，此外再没有别的素数了。
现在，我们来考察上面从2到P的全体素数相乘、再加上1这个数，设它是A，即
A=2×3×5×7×11×……×P+1。
A是一个大于1的正整数，它不是素数，就是合数。
如果A是素数，那么，就得到了一个比素数P还要大的素数，这与素数P是最大素数的假设矛盾。
如果A是合数，那么，它一定能够被某个素数整除，设它能被g整除。
因为A被从2到P的任何一个素数除，余数都是1，就是都不能整除，而素数g是能整除A的，所以素数g不在从2到P的全体素数之中。这说明素数g是一个比素数P更大的素数，这又与P是最大的素数的假设矛盾。
上面的证明否定了素数只有有限多个的假定，这就证明了素数是无穷多个。
第三题、给一个很大的数组，里面有两个数只出现过一次，其他数都出现过两次，把这两个数找出来。
很简单，根据所有数的异或结果，将数字分为两组，然后找出这两个数。前面我的blog里有这个题的介绍的。
第四题、把一个链表逆过来，要求空间复杂度O(1)，这个算简单的。
/*
==========================
功能：链表逆序
(链表的头变成链表的尾，链表的尾变成头)
返回：指向链表表头的指针
==========================
*/
struct node *Reverse (struct node *head)
{
struct node *p; //临时存储
struct node *p1; //存储返回结果
struct node *p2; //源结果节点一个一个取
p1 = NULL; //开始颠倒时，已颠倒的部分为空
p2 = head; //p2指向链表的头节点
while(p2 != NULL)
{
p = p2->next;
p2->next = p1;
p1 = p2;
p2 = p;
}
head = p1;
return head;
}
二面：
1、是如何统计代码行数以及注释的行数，并写出具体的实现代码。
代码行数是按照\n数的，行注释//需要注意//...\n算一个注释，但注意//...\n之间的//与/**/不算注释。
/**/要注意/* /* */ 等于一个注释, 也就是一旦遇见/*之后就要记下来，一直匹配到*/才算一个完整的注释，中间的内容随便它是什么，包括//可能也嵌套在其中。
2、要求用最快的速度求两个数组的交集，提示数组中的元素是无序的。写出具体的实现代码。
如果哈希真的是O(1)的，那么可以达到O(n+m)，否则就是nlogn + mlogm。
3、写程序，将一个浮点数转化为字符串。。
先将浮点数赋值给一个int类型的整数，然后分别将整数部分、小数部分转化为字符串就可以了。
4、下面两个printf的输出结果是什么？为什么会有这样的结果？
int main(void)
{
char a = 255;
printf("%d\n",sizeof(++a));
printf("%d\n",a);
return 0;
}
输出结果是：1 -1
第一个输出的是字符类型占用的内存大小，一个字符类型占用一个字节的大小，所以输出1
由于255的二进制表示是1111 1111，将其作为int类型输出的时候，由于最高位是1，表示的是一个负数，其表示的数字就是将最高位后面的7个1取反后在加上1，表示的就是-1，所以第二个输出应该是-1。
5、下面代码的输出是什么？
char *c[] = {"ENTER","NEW","POINT","FIRST"};
char **cp[] = { c + 3 , c + 2 , c + 1 , c};
char ***cpp = cp;
int main(void)
{
printf("%s",**++cpp);
printf("%s",*--*++cpp+3);
printf("%s",*cpp[-2]+3);
printf("%s\n",cpp[-1][-1]+1);
return 0;
}
c是一个指针数组,一个数组,元素是char*类型的指针,值分别是那些字符串(的首地址)
c[0] = "ENTER"
c[1] = "NEW"
c[2] = "POINT"
c[3] = "FIRST"
而[]和*是本质一样的运算，即c[i]=*(c+i)
c和c+i都是char *[]类型，它可以退化成char **类型，再看cp，它正好是一个char **的数组，来看它的值：
cp[0] = c + 3
cp[1] = c + 2
cp[2] = c + 1
cp[3] = c
再引用一次看得清楚些
cp[0][0]=c[3]="FIRST",etc
cp是char **[]类型，它可以退化成char ***类型，看最后的cpp，它正是char ***类型，它是一个指针变量，和上面两个不同，上面两个是数组。
1、printf("%s",**++cpp);
++cpp 的值是cp+1，引用一次后是cp[1]再引用是*cp[1]=c[2]="POINT"，第一句的输出
2、printf("%s",*--*++cpp+3);
再++cpp 的值是cp+2，引用一次是cp[2]=c+1，再对这进行--，减后是c再引用是c[0]="ENTER"再+3，字符串指针指到"ER"，输出是"ER"
3、printf("%s",*cpp[-2]+3);
这时cpp的值是cp+2，cpp[-2]=*(cpp-2)=*(cp+2-2)=cp[0]=c+3，再引用是c[3]="FIRST",+3 字符串指针指到"ST"，输出是"ST"
4、printf("%s\n",cpp[-1][-1]+1);
cpp还是cp+2，cpp[-1]=*(cpp-1)=*(cp+2-1)=cp[1]=c+2，再[-1]得*(c+2-1)=c[1]="NEW",+1字符串指针指到"EW"，输出是"EW"
三面：
1、给定两个排好序的数组A和B，他们中的元素个数都是n，求他们所有元素的中位数。要求：时间复杂度为O（logn），空间复杂度为O（1）。（二分查找）
2、有两个数组a、b，大小都为n，数组中元素的值是整数类型、无序；要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小？
3、对已排好序的数组A，一般来说可用二分查找可以很快找到。现有一特殊数组A[]，它是循环递增的，如A[]={ 17 19 20 25 1 4 7 9},
试在这样的数组中找一元素x，看看是否存在。
请写出你的算法，必要时可写伪代码，并分析其空间、时间复杂度。