最新百度实习生面试一试题

发表于 2012-6-12 10:45

第一题、任意给一个数，试证明这个数的某个倍数的十进制表示是01串，比如3的倍数111是二进制表示，5的倍数10是二进制表示，等等。

第二题、证明素数有无穷多个。

第三题、给一个很大的数组，里面有两个数只出现过一次，其他数都出现过两次，把这两个数找出来。

第四题、把一个链表逆过来，要求空间复杂度O(1)，这个算简单的。

这几道题我看了半天的，的却我这种凡夫俗子短期内是整不出来的，求助高手了。。

发表于 2012-6-12 12:47

第三题
要判断的数组为A
定义一个数组B用来存不重复数,和索引bindex
定义一个数组C用来存对应数的数量
把第0个数放入A
A循环 i=1
{
   B循环 j=0
  {
      如果A[i]等于B[j]
C[j]+=1;
否则
B[bindex++]=A[i];

}
}
C循环
查找value为1的索引
B[C索引。。]就是想要找的值

发表于 2012-6-12 16:26

要判断的数组为A
定义一个数组B用来存放只出现一次的数据,和索引bindex
把第A[0]个数放入B[0]
A循环 i=1
{
   B循环 j=0
  {
      如果A[i]等于B[j]
      B[j]=B[bindex--];删除重复数据
      否则
      B[bindex++]=A[i];

}
}
最后bindex为只出现一次的数量
B里存放的为只出现过一次的数据

发表于 2012-6-12 16:30

学习了

发表于 2012-6-12 16:31

1# shenmu2012 学习了

发表于 2012-6-12 19:47

前面二题是数学里的吧，你怎么用程序来证明呢？

发表于 2012-6-12 21:08

这要不跟二楼学习，我是做不出来的。汗。我承认我也是个凡夫俗子

发表于 2012-6-12 21:21

长见识了。

发表于 2012-6-12 22:17

本帖最后由 joseph2675 于 2012-6-12 22:30 编辑

第一题任何整数都可以用二进制来表示任意给一个数它的某个倍数可以是整数
第二题如果素数是有限的话那么合数是由若干个质数相乘而得到的若干个质数相乘必然也是有限的
而素数和合数一起组成了正整数那么正整数也是有限的和事实相悖

发表于 2012-6-12 22:19

素数和合数一起组成了除1外的正整数参见百度百科

发表于 2012-6-12 22:24

确实挺考验老子灵活性的！！！

发表于 2012-6-12 23:01

9# joseph2675 你的证明是错的，思路有点沾边
2的N次方也可以趋近无穷大可是只有一个因子；
正确的证明是
假设自然数中只有有限多个素数，不妨设为n个，它们是q1,q2,q3,…,qn。现构造一个数A=(q1*q2*q3*…*qn)+1，A比q1,…qn中的任何一个都大，因此与它们都不同，假设A是合数。A不能被q1,…qn中的任何一个整除，因为会余1，所以q1,…qn都不是A的因子，即A不能表示成q1,…qn的乘积，这与我们假设的只有q1,…qn是素数是矛盾的，因此自然数中有无限多个素数，证毕

发表于 2012-6-12 23:22

我也是个凡夫俗子、、、

发表于 2012-6-13 08:21

学习了。

发表于 2012-7-4 10:04

各位不愧是高手啊，学习了啊，那就结贴了啊

发表于 2012-7-5 15:48

进来学习一下，发现自己也是个凡夫俗子，短期内也整理不出来。受教了。

发表于 2012-7-7 07:38

牛单位的面试题确实很BT啊

最新百度实习生面试一试题

相关帖子

浏览过的版块

突出贡献奖章

沉静之湖泊

常驻人口

技术高手奖章

偶尔光临

以坛为家

七世轮回

技术奇才奖章

甘甜之泉水

经常做客

无冕之王奖章

奔腾之江水

伴坛终老