今天看到一个帖子
http://www.iteye.com/topic/622496
里面提到了如下问题:
附微软面试的面试题:
1:单链表,遍历一次,找到倒数第N个节点。
2:单链表,遍历一次,找到中间节点。(这个主要要考虑到单链表元素个数是奇/偶数的情况,这个是关键的,我当时 就是差点没考虑到这个)。
3:如何把一个大象装到冰箱里。
4:随手拿一个笔筒,把笔倒掉,问,你会用什么方法测试这个笔筒。
有意义的回复:
第一题先把一个节点前进n个节点(当然,前进的时候判断是否遇到null,遇到表明题目无解)。然后用另外一个节点和刚才的节点一起前进,当后一个节点遇到null时,前一个节点就是要找的节点。
第二题和第一题的思路是一样的。一个前进两个节点,一个前进一个,和检测环算法类似。
时间复杂度都是O(n)
你的基本解题思路是对的,第一题也没有什么问题,但第2题有点问题,因为要考虑到元素是偶数的情况下,你是如何确认中间节点的(可以认为偶数没有中间节点,也可以认为偶数有两个中间节点),另外如果是奇数且只有一个节点,你的中间节点又是怎么算的?这些细节问题都是需要考虑到得。
4:随手拿一个笔筒,把笔倒掉,问,你会用什么方法测试这个笔筒。
答:再把笔装回去,原因很简单,笔筒就是用来装笔的,要测试的最好方法就是往里面装笔。
exloong 写道
第四题你们想怎么去测试就进圈套了,要先问他要测试需求
分享到:
相关推荐
用c++实现了单链表的查找,插入和删除,简单直观。
单链表快速排序 VC++ WIN32 Console Application
基础的单链表查找函数 c语言实现 新手学习c语言链表的基础函数
链表 C语言实现 单链表 查找运算 txt
使用C++实现单链表的基本操作: 1、创建单链表 2、遍历单链表 3、单链表插入 4、删除单链表 5、判断是否为空 6、单链表的长度 7、单链表查找 8、退出
int main() { listtype l; int i,j; printf("输入链表数据:\n"); initiatesl(&l); show_l(&l); i=find_list(&l,3); j=find_list(&l,7);... printf("'3'所在位置:%d\n'7'所在位置:%d\n",i,j);...}
这里有封装好的单链表,里面包含了各种单链表的实现过程
该数据结构算法可以令初学者学会数据结构内的单链表按值查找,并了解数据结构里的数据操作
按照查找单链表带环的思路二,我们用一个HashSet维护已经跑过的元素,当重复的时候,那个结点就是环的入口。这法子还算好使,不过还是老问题——空间复杂度大。 思路二:再开一个指针与当前指针相会 我们当前双指针...
本程序由C#实现,如何定义单链表以及查找、插入、求长度基本操作。
2、查找单链表中的第i个结点,并输出结点元素的值; 3、在单链表中的第i个结点前插入一个结点值为e的正整数(从外部输入); 4、删除单链表中的第j个结点; 5、将单链表中的各结点就地逆序(不允许另建一个链表); 6 ...
此压缩包为1、无头+单向+非循环链表增删查改实现// 动态申请一个结点// 单链表打印// 单链表尾插// 单链表的头插// 单链表的尾删// 单链表头删// 单链表查找// 单链表在pos位置之后插入x// 单链表删除pos位置之后的...
2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点...
头插法建立带头结点的单链表,并找出中间节点值
2、对已建立的单链表实现查找、逆置和计算线性表长度等操作。 void main( ) { int r[100],n,i,x; cout请输入线性表中元素的个数!"; cin>>n; cout请输入线性表中每个元素!"; for(i=0;i;i++) {cout请输入第...
单链表的查找插入删除.cpp
3.单链表的查找.md
单链表的头插入、尾插入、以及查找、删除、逆置等操作
单链表的创建、查找、删除、添加、合并
单链表的查找 插入与删除.c