一面:
第一题、任意给一个数,试证明这个数的某个倍数的十进制表示是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类型的整数,然后分别将整数部分、小数部分转化为字符串就可以了。三面:
1、给定两个排好序的数组A和B,他们中的元素个数都是n,求他们所有元素的中位数。要求:时间复杂度为O(logn),空间复杂度为O(1)。(二分查找)
http://blog.csdn.net/hackbuteer1/article/details/7584838 实现代码
2、有两个数组a、b,大小都为n,数组中元素的值是整数类型、无序;要求:通过交换a,b中的元素,使数组a元素的和与数组b元素的和之间的差最小?
3、对已排好序的数组A,一般来说可用二分查找可以很快找到。现有一特殊数组A[],它是循环递增的,如A[]={ 17 19 20 25 1 4 7 9},
试在这样的数组中找一元素x,看看是否存在。
请写出你的算法,必要时可写伪代码,并分析其空间、时间复杂度。
http://blog.csdn.net/hackbuteer1/article/details/7581596 实现代码
分享到:
相关推荐
实习生java面试题集及详细答案
hadoop2面试题 -2012年腾讯招聘实习生笔试题.pdf
2012uc实习生招聘笔试题(研发类),word版,从第一题到最后一题,完整版,附带部分答案。 附带UC面试经历:uc面试采用群面方式,大约15人,三人一组,一个考官,首先简单自我介绍,然后给出一个题目,让每组讨论出...
实习生java面试题集及详细答案.pdf
春招,即春季校园招聘,是企业面向应届生(2020届)...补招、实习生招聘两大类。 欢迎实习生投递阿里巴巴开发岗位: 加微信号:alibabazp 发送:职位+学校+姓名+手机 示例:Java研发岗+浙江大学+张三+15988889999
\百度计算机专业招聘面试题及答案\百度计算机专业招聘面试题及答案\百度计算机专业招聘面试题及答案\百度计算机专业招聘面试题及答案\百度计算机专业招聘面试题及答案
百度校园招聘笔试面试题22个文档资料合集: 百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知岗位.docx 百度2014校园招聘笔试试题...
实习生java面试题集及详细答案,比较完整比较全,准备去应聘的同学可以看看
百度DBA的笔试题分为如下几个块涉及了操作系统、计算机组成原理、数据结构、网络、Linux等几个方面
百度笔试题目,很有用,经典的题目,是本人亲身体验,亲身经历过。
Java实习生常见面试题
百度校园招聘笔试面试题合集 深度学习、移动开发、系统研发、web前端
杭州阿里云Java实习生岗位面试真题 程序员八股文 大厂面经 程序员面经
百度面试必备笔试试题。.../*百度面试题算法: 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合,对于集合的每个元素,依次在其他集合中搜索 是否有此元素存在:
2012前端工程师招聘面试题,值得一看,整理资料了,删了可惜
百度计算机专业招聘面试题及答案.pdf
大厂京东Java实习生面试真题 程序员八股文 大厂面经 程序员面经
腾讯实习生面试题,虽然是前两年的,仍然有借鉴意义。
2014.3.29 地点在北航 大家可以参考参考