面试 算法题编程 含答案算

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