全面试 算法题编程 含答案算.docx

面试算法题编程含答案算1 .在不借助第三个变量的情况下，把两个int的变量X.Y的值互换，用任何自己熟悉的编程语言完成参考答案：思路如下X=X+Y;Y=X-Y;X=X-Y;具体编程语言完成情况由面试官检查。考察点：基本算法、语言基础。2 .文件查找优化背景:百度每天都有大量搜索,如果有一个大文本文件（保存各种词语）,每次搜索都必须要检查查询词是否在这个大文件中，请问有什么方式能够提高查找效率要求：先讲解所使用的算法，然后用自己最熟悉的编程语言，在3分钟内予以实现参考答案：基本方法：采用hash签名，提高匹配效率;建立多叉树保存文件数据，提高查找速度。如有列举出更多签名算法或更好数据结构形式，可加分较优方法：在上面基础上，将文本文件转化为key->va1ue的二进制文件，提高文件操作和查找速度更优方法：在上面基础上，开辟内存做cache,保存高频率查询词，提高整体查找效率。如能完整给出cache的更新机制，加分;考察点：基本数据结构；灵活采取算法处理实际问题的能力；快速编程能力；在给出一定提示情况下，检查学习能力和知识应用能力。4 .有一份成绩单，只有两个字段：姓名、成绩；数据量在百万级别。要求用最优的数据存储方式，能通过姓名快速查找出成绩。(5分钟)参考答案:存储方式采用对姓名做hasho考察点：数据结构5 .找出单向链表的中间节点参考答案：1ink*mid(1ink*head)(1ink*p1z*p2;p1=p2=head;if(head=NU11head->next=NU11)returnhead;dop1=p1->next;p2=p2->next->next;whi1e(p2&&p2->next);returnp1;)考察点：算法基础链表6.给定43亿个32位整数的顺序文件，请问如何可以找到一个至少出现两次的整数？考察：算法相关(IOmin)参考答案：用二分查找发。细节点：43亿大于int的最大值，说明肯定有重复的数字7、如何判断一个单链表是有环的(不能用标志位，最多只能用两个额外指针)(6分钟)考察点：算法及数据结构参考答案：可以只给出算法思路,一种O(n)的办法就是(两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然)structnodecharva1;node*next;boo1check(constnode*head)/returnfa1se:无环;true:有环boo1check(constnode*head)if(head=NU11)returnfa1se;node*1ow=headz*fast=head->next;whi1e(fast!=NU11&&fast->next!=NU11)(1ow=1ow->next;fast=fast->next->next;if(1ow=fast)returntrue;)returnfa1se;8.有一个一维数组inta100,里面存储的是1到100的这100个数，不过是乱序存储；这时把其中某一位置的数值改成；请用最优的空间复杂性和时间复杂性求出该位置和值(6分钟)参考答案：遍历一遍数组得到-1的位置并记录，同时把非-1的值相加得到sum被改变的值为：50*(100-1)-sum时间复杂性O(n),空间复杂性0(1)考察点：程序设计、逻辑思维能力