精品文档Problem 1 : Is it a loop ?（判断链表是否有环？）
Assume that wehave a head pointer to a link-list. Also assumethat we
know the list is single-linked. Can you come up an algorithm to
checkwhether this link list includes a loop by using O(n) time and O(1)
space wheren is the length of the list? Furthermore, can you do so with
O(n) time and onlyone register?
方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进 2 个节点，则最多 2N ，后两个指针可以重合；如果无环，则正常停止。
同样的，可以找到链表的中间节点。同上。
Problem 2：设计一个复杂度为n 的算法找到链表倒数第m 个元素。最后一个
元素假定是倒数第0 个。
提示：双指针查找
Problem 3：用最简单的方法判断一个LONG 整形的数 A 是 2^n（2 的 n 次方）提示： x&(x-1)
Problem 4：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，
然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？
提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，
不合理。
Problem 5：给你a、b两个文件，各存放50 亿条 url ，每条 url 各占用 64 字节，内存限制是4G ，让你找出 a、b 文件共同的 url 。
法 1 ：使用 hash 表。使用 a 中元素创建 hash 表， hash 控制在适当规模。在
hash 中查找 b 的元素，找不到的url 先存在新文件中，下次查找。如果找到，
则将相应的 hash 表项删除，当hash 表项少于某个阈值时，将 a 中新元素重新
hash 。再次循环。
法 2 ：对于 hash 表项增加一项记录属于的文件a，b 。只要不存在的表项即放入
hash 表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频
繁。
Problem 6：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的
单词 b ，那么定义 b 是 a 的兄弟单词。现在给你一个字典，用户输入一个单词，
让你根据字典找出这个单词有多少个兄弟单词。
提示：将每个的单词按照字母排序，则兄弟单词拥有一致的字母排序（作为单词签名）。使用单词签名来查找兄弟单词。
Problem 7：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一
次找出那桶不正常的球。
Problem 8：给两个烧杯，容积分别是m 和 n 升（ m!=n ），还有用不完的水，用这两个烧杯能量出什么容积的水？
m, n, m+n, m-n以及线性叠加的组合
Problem 9：写出一个算法，对给定的n 个数的序列，返回序列中的最大和最
小的数。
Problem 10：你能设计出一个算法，只需要执行 1.5n 次比较就能找到序列中
最大和最小的数吗？能否再少？
提示：先通过两两比较，区分大小放入“大”，“小”两个数组中。从而最大数
在“大”数组中，最小数在“小”数组中。
Problem 11：给你一个由n-1个整数组成的未排序的序列，其元素都是 1 到 n
中的不同的整数。请写出一个寻找序列中缺失整数的线性- 时间算法。
提示：累加求和
Problem 12：void strton(const char* src, const char*token)假设src是一长串字符， token存有若干分隔符，只要src的字符是token中的任何一个，就进行分割，最终将src 按照 token分割成若干单词。找出一种O(n) 算法？
提示：查表的方法，将所有的字符串存储在长度为128 的数组中，并将作为分
隔符的字符位置 1 ，这样即可用常数时间判断字符是否为分隔符，通过n次扫描，将 src 分割成单词。
Problem 13：一个排好序的数组A，长度为 n ，现在将数组 A 从位置 m(m m 未知 )分开，并将两部分互换位置，假设新数组记为 B，找到时间复杂度为O(lgn) 的算法查找给定的数x 是否存在数组 B 中？ 提示：同样采用二分查找。核心思想就是确定所查找数所在的范围。通过比较3 个数（头，尾，中间）和所查找数之间的关系，可以确定下次查找的范围。 Problem 14：一个排好序的数组A，长度为 n ，现在将数组 A 从位置 m(m m 已知 )分开，并将两部分互换位置，设计一个O(n) 的算法实现这样的倒置，只 允许使用一个额外空间。（循环移位的效率不高） 提示：(A’B’)’ =BA Problem 15：给出Vector的一个更好实现。（STL的vector内存的倍增的，但是每次倍增需要拷贝已存元素，平均每个元素需要拷贝一次，效率不高） 提示：可使用 2^n的固定长度作为每次分配的最小单位，并有序的记录每个块 的首地址。这中结构同样可以实现线性查找，并且拷贝代价很低（仅有指针） Problem 16：出已排序数 A ，B，度分 n ，m ，找出一个复 度（ lgn ）的算法，找到排在第k 位置的数。 提示：二分找。 Problem 17：出任意数A，B，度分n， m ，找出一个复 度（ lgn ）的算法，找到排在第k 位置的数。 提示：通最小堆k 个数，不断更新，描一次完。 个提示有，求最算法！ Problem 18 ：假数 A 有 n 个元素，元素取范是1~n ，判定数是否 存在重复元素？要求复度 O(n) 。 法 1：使用 n 的数，元素，存在 1 ，两次出 1 ，即重复。 法 2：使用 m 的数，分大小：n/m, 2n/m? .. 的元素个数。桶方法法 3：累加求和。可用于求有一个元素重复的方法。 Problem 19：定排好序的数 A ，大小 n ，定数 X，判断 A 中是否存 在两数之和等于X。出一个 O(n) 的算法。 提示：从中向两找。利用有序的条件 Problem 20：定排好序的数 A ，大小 n ，出一个 O(n) 的算法，除 重复元素，且不能使用外空。 提示，既然有重复，必有冗余空。将元素放入数的前面，并下次可放位 置，不断向后描即可。 Problem 21：定两个排好序的数 A ，B，大小分 n ，m 。出一个高 效算法找 A 中的哪些元素存在 B 数中。 注意：一般在大数中行二分找，将小数的元素作需找的象。 更算法（刃提供）：可以使用两个指遍AB ，比当前大小就可以了 ... 复度 o(n+m) Problem 22 ：：有 1000桶酒，其中 1 桶有毒。而一旦吃了，毒性会在 1 周 后作。在我用小老鼠做，要在 1 周内找出那桶毒酒，最少需要多少 老鼠。 答案：10 只。将酒号 1~1000将老鼠分号 1 2 4 8 16 32 64 128 256 512 喂酒酒的号等于老鼠号的加和如：17 号酒喂 1 号和 16 号老鼠 76 号酒喂 4 号、 8 号和 64 号老鼠七天后将死掉的老鼠号加起来得到的号就是有毒的那桶酒因 2 的 10 次方等于 1024所以10只老鼠最多可以 1024 桶酒 明如下：使用二制表示：01, 10, 100, 100 0,?, 1,000,000,000。于任何一个小于 1024 的数，均可以采用前面的唯一一二制数来表示。故成立。 Problem 23：一最少个数砝，使得天平能称量1~1000的重量。如果砝只能放， 1，2 ，4 ， 512 最好。（只能加） 如果允砝双放，1, 3, 9, 27最好。（可?加.可减）已知1,3 ，如何算下一个数。可称重量 1,2,3,4 。下个数 x,可称重量 , x-4, x-3, x-2, x-1, x, x+1, x+2, x+3, x+4。使砝最好，所称重量不重复（浪）。故x=9 。同理， 可得后面。 形算法 Problem 24：如何判断一个点是否在一个多形内？ 提示：多形行分割，成一个个三角形，判断点是否在三角形内。 一个非常有用的解析几何：如果 P2(x1,y1),P2(x2,y2), P3(x3,y3)是平面上的3 个点，那么三角形P1P2P3 的面等于下面的二分之一： | x1 y1 1 | | x2 y21| = x1y2 + x3y1 + x2y3–x3y2 –x2y1 –x1y3 | x3 y31| 当且当点 P3 位于直 P1P2( 有向直 P1->P2) 的右，表达式的 符号正。个公式可以在固定的内，一个点位于两点确定直的哪， 以及点到直的距离 (面 = 底* 高/2) 。 这个结论：可以用来判断点是否在点是否在三角形内。法 1 ：判断点和三角形三边所行程的 3 个三角形的面积之和是否等于原来三角形的面积。（用了三次上面的公式）。 法 2 ：判断是否都在三条边的同一边，相同则满足，否则不在三角形内。 Problem 25：给出两个n为向量与0点形成角的角平分线。 提示：对两条边进行归一化，得到长度为 1 的两点，取两个的中点即可。 简介：计算机考研之家搜集的华为C语言经典面试题，来试试你的C语言水平吧。每道题都附有详细解答和讲解，很有参考价值的C语言面试题。 怎么判断链表中是否有环？ bool CircleInList(Link* pHead) { if(pHead = = NULL || pHead->next = = NULL)//无节点或只有一个节点并且无自环 return (false); if(pHead->next = = pHead)//自环 return (true); Link *pTemp1 = pHead;//step 1 Link *pTemp = pHead->next;//step 2 while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL) { pTemp1 = pTemp1->next; pTemp = pTemp->next->next; } if(pTemp = = pTemp1) return (true); return (false); } 两个字符串，s,t;把t字符串插入到s字符串中，s字符串有足够的空间存放t字符串 void insert(char *s, char *t, int i) { memcpy(&s[strlen(t)+i],&s[i],strlen(s)-i); memcpy(&s[i],t,strlen(t)); s[strlen(s)+strlen(t)]='\0'; } 1。编写一个C 函数，该函数在一个字符串中找到可能的最长的子字符串，且该字符串是由同一字符组成的。 char * search(char *cpSource, char ch) { char *cpTemp=NULL, *cpDest=NULL; int iTemp, iCount=0; while(*cpSource) { if(*cpSource == ch) { iTemp = 0; cpTemp = cpSource; while(*cpSource == ch) ++iTemp, ++cpSource; if(iTemp > iCount) 第一题简答题 1．多线程和多进程模式有什么区别？在用两种模型开发服务程序时，分别有什么优缺点？采用长连接和短连接模式有什么区别？分别有什么优缺点？采用同步和异步模式有什么区别？分别有什么优缺点。 （1）启动进程的时候，操作系统会为进程分配资源，其中最主要的资源是内存空间，因为程序是在内存中运行的。在进程中，有些程序流程块是可以乱序执行的，并且这个代码块可以同时被多次执行。实际上，这样的代码块就是线程体。线程是进程中乱序执行的代码流程。当多个线程同时运行的时候，这样的执行模式成为并发执行。 对于一个进程中的多个线程来说，多个线程共享进程的内存块，当有新的线程产生的时候，操作系统不分配新的内存，而是让新线程共享原有的进程块的内存。因此，线程间的通信很容易，速度也很快。不同的进程因为处于不同的内存块，因此进程之间的通信相对困难。线程切换快，但实现稍复杂。进程易实现，较稳定，但性能与线程相比较差。 （2）所谓长连接，指在一个TCP连接上可以连续发送多个数据包，在TCP连接保持期间，如果没有数据包发送，需要双方发检测包以维持此连接，一般需要自己做在线维持。 短连接是指通信双方有数据交互时，就建立一个TCP连接，数据发送完成后，则断开此TCP连接，一般银行都使用短连接。 长连接多用于操作频繁，点对点的通讯，而且连接数不能太多情况，。每个TCP 连接都需要三步握手，这需要时间，如果每个操作都是先连接，再操作的话那么处理速度会降低很多，所以每个操作完后都不断开，次处理时直接发送数据包就OK了，不用建立TCP连接。而像WEB网站的http服务一般都用短链接，因为长连接对于服务端来说会耗费一定的资源，而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源，如果用长连接，而且同时有成千上万的用户，如果每个用户都占用一个连接的话，那可想而知吧。所以并发量大，但每个用户无需频繁操作情况下需用短连好。 （3）同步:调用方调用一个程序,等待返回,然后再继续下面的程序处理 异步: 调用方调用一个程序,不等待返回,继续执行下面的程序。 1)异步通信简单，双方时钟可允许一定误差。同步通信较复杂，双方时钟的允许误差较小。 2)通信效率：异步通信低，同步通信高。 算法经典面试题 世界上第一位程序员是英国著名诗人拜伦的女儿AdaLovelace曾设计了巴贝奇分析机上解伯努利方程的一个程序。她甚至还建立了循环和子程序的概念。下面就由X为大家介绍一下程序员面试算法题的文章。 程序员面试算法题篇1 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 思路一：当我们到达某一个节点准备调整以该节点为根节点的子数时，先调整其左子树将左子树转换成一个排好序的左子链表，再调整其右子树转换成右子链表。最近链接左子链表的最右节点、当前节点和右子链表的最左节点。从树的根节点开始递归调整所有节点。 思路二：我们可以中序遍历整个树。按照这个方式遍历树，比较小的节点优先访问。如果我们每访问一个节点，假设之前访问过的节点已经调整为一个排序的双向链表，我们再把调整当前节点的指针链接到链表的末尾。当所有的节点都访问过之后，整棵树也就转换成一个排序的双向链表了。 参考代码： 二元查找树的节点数据结构： structBSTreeNode{ int value; BSTreeNode *m_left; BSTreeNode *m_right; } 思路二对应的代码： void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList) { if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); 1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同 的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？ 2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取不同种颜色的 两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？ 3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形 状上下都不均匀，问你如何才能准确称出4公升的水？（40秒-3分钟） 4.一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的， 另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？ 5.村子中有50个人，每人有一条狗。在这50条狗中间有病狗（这种病不会传 染）。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有枪响。到了第三天传来一阵枪声，问有几条病狗，如何推算得出？ 6.S先生、P先生、Q先生他们知道桌子的抽屉里有16张扑克牌：红桃A、Q、 4 黑桃J、8、4、2、7、3 草花K、Q、5、4、6 方块A、5。约翰教授从这 16张牌中挑出一张牌来，并把这张牌的点数告诉P先生，把这张牌的花色告诉Q先生。这时，约翰教授问P先生和Q 先生：你们能从已知的点数或花色中推知这张牌是什么牌吗？于是，S先生听到如下的对话： P先生：我不知道这张牌。 Q先生：我知道你不知道这张牌。 P先生：现在我知道这张牌了。 Q先生：我也知道了。 听罢以上的对话，S先生想了一想之后，就正确地推出这张牌是什么牌。请问：这张牌是什么牌？ 7.两个男孩各骑一辆自行车，从相距2O英里（1英里合1.6093千米）的两个 地方，开始沿直线相向骑行。在他们起步的那一瞬间，一辆自行车车把上的一只苍蝇，开始向另一辆自行车径直飞去。它一到达另一辆自行车车把，就立即转向往回飞行。这只苍蝇如此往返，在两辆自行车的车把之间来回飞行，直到两辆自行车相遇为止。如果每辆自行车都以每小时1O英里的等速前进，苍蝇以每小时15英里的等速飞行，那么，苍蝇总共飞行了多少英里？ 8.有位渔夫，头戴一顶大草帽，坐在划艇上在一条河中钓鱼。河水的流动速度 是每小时3英里，他的划艇以同样的速度顺流而下。“我得向上游划行几英里，” 他自言自语道，“这里的鱼儿不愿上钩！” 教师资格证面试结构化真题解析思路——综合分析类（25道题） 1.如果一个老师上课拖堂了，同学指出应该下课了，老师气呼呼的摔门而去，你怎么看？ 题型：综合分析-观点类 分析：要从教师及学生两方面进行分析，各有合理之处，也存在一定的问题。不能全盘否定，要辩证的看待。 参考答案： 点题：老师上课拖堂了，同学指出应该下课了，老师气呼呼的摔门而去，这个教师的作法就欠妥当，同学们直接指出老师问题，也不够礼貌。 析题：作为老师，可能出发点是好的，希望学生多学习知识，取得理想的教学效果，但是不能提倡拖堂，因为首先，占用学生休息时间用来上课，本身会招来学生的反感和抵触情绪。人在教室，心思早已飘出课堂，不能达到很好的教学效果。其次教师应该及时反思，自己的教学安排是否恰当可行，在以后的教学计划中，精简内容，突出重点，吸引学生。最后，当学生指出问题之后，应该虚心接受，不能摔门而出，学生具有向师性，不好的行为，学生也会模仿，不利于学生身心全面发展及良好品行的形成。 作为学生，题目中的学生作法也不妥当，应该在课下开诚布公的告诉老师，或者给代课教师写一封信，做到友好交流，共同解决问题才是关键。 总结：总之，这位教师应该多反思，树立终身学习的理念，不断更新教学的内容和方法。才能适应新时期素质教育要求，形成良好的师生关系，成为受学生欢迎的教师。这些学生也要体会教师的良苦用心，用合适的方法来反映教师的一些问题。 2.有的老师上课的时候频频使用多媒体，给学生播放电影，学生反映老师讲的内容少，你怎么看？ 题型：综合分析—现象类 分析：本题采用主体分析法进行作答。这道题目中的主体是老师、学生两个，那就从这两个主体进行分析。 从老师的角度看，希望授课时课程生动，但是方法有所欠缺，缺乏必要知识的引导总结； 从学生角度讲，学生是学习的主体，学习更多知识是追求，反映学生的成长进步等。 参考答案： 点题：有的老师上课的时候频频使用多媒体，给学生播放电影，学生反映老师讲的内容少，对于这种现象，我有以下几点看法： 精选微软等公司数据结构 精选微软等公司数据结构++算法面试100题 -----[第1题-60题总] 资源说明： 此份，是为微软等公司数据结构+算法面试100题，之前60题的汇总。 总结整理了前第1题-第60题。特此并作此一份上传。以飨各位。:)。 -------------------------------- 相关资源，包括答案，下载地址： [答案V0.2版]精选微软数据结构+算法面试100题[前20题]--答案修正 https://www.doczj.com/doc/e17837313.html,/source/2813890 //此份答案是针对最初的V0.1版本，进行的校正与修正。 [答案V0.1版]精选微软数据结构+算法面试100题[前25题] https://www.doczj.com/doc/e17837313.html,/source/2796735 [第二部分]精选微软等公司结构+算法面试100题[前41-60题]： https://www.doczj.com/doc/e17837313.html,/source/2811703 [第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题] https://www.doczj.com/doc/e17837313.html,/source/2778852 更多资源，下载地址： http://v_july_https://www.doczj.com/doc/e17837313.html,/ 很快，我将公布第21-40题的答案，敬请期待。:).. 如果你对以下的前第1-60题，有好的思路，和算法，欢迎跟帖回复， 或者，联系我，发至我的邮箱， zhoulei0907@https://www.doczj.com/doc/e17837313.html,。 My CSDN Blog：https://www.doczj.com/doc/e17837313.html,/v_JULY_v My sina Blog：https://www.doczj.com/doc/e17837313.html,/shitou009 帖子维护地址： [整理]算法面试：精选微软经典的算法面试100题[前1-60题] https://www.doczj.com/doc/e17837313.html,/u/20101023/20/5652ccd7-d510-4c10-9671-307a56006e6d.html -------------------------------------- July、2010、/11.12.请享用。:)。 1 计算机网络OSI与TCP/IP各层的结构与功能，都有哪些协议。 ISO/OSI模型用途主要作用协议 应用层进程间通信为操作或网络应用程序提供访问 网络服务的接口。TFTP，HTTP，SNMP，FTP，SMTP，DNS，Telnet 表示层数据表示（编码）解决用户信息的语法表示问题。 提供格式化的表示和转换数据服 务。数据的压缩和解压缩，?和解 密等工作都由表示层负责。 无协议 会话层建立和管理主机 间的会话会话层不参与具体的传输，它提供 包括访问验证和会话管理在内的 建立和维护应用之间通信的机制。 如服务器验证用户登录便是由会 话层完成的。（以上统称报文） 无协议 传输层端到端链接提供主机之间连接，屏蔽技术细 节。将分组组成报文，可靠传输、 流量控制。为上层提供端到端（最 终用户到最终用户）的透明的、可 靠的数据传输服务。 TCP，UDP 网络层寻址路径选择为传输层提供建立、维护和网络连 接，解决路由选择。数据单元--- 分组packet IP，ICMP，RIP，OSPF，BGP，IGMP 数据链路层占用传输介质数据链路层在不可靠的物理介质 上提供可靠的传输。建立相邻结点 之间的数据链路，通过差错控制提 供数据帧（Frame）在信道上无差 错的传输。作用；物理地址寻址、 数据的成帧、流量控制、数据的检 错、重发。?SLIP，CSLIP，PPP，ARP，RARP，MTU TCP/IP 相似之处： 基于独立的协议族，层的功能划分相似差异： ISO/OSI：从概念模型到协议实现；TCP/IP:从协议实现到概念描述 层次数量差别； 2.TCP与UDP的区别。 UDP（UserDatagramProtocol）：不提供复杂的控制机制，利用IP提供面向无连接的通信服务。并且他是将应用程序发来的数据在收到那一刻，立刻按照原样发送到网络上的一种机制。即使出现网络拥堵，UDP也无法进行流量控制等避免拥塞的行为。如果传输途中出现丢包，也不负责重发。甚至出现包的到达乱序时也没有纠正功能。如果需要这些细节控制，要交给采用UDP的应用程序处理。UDP将控制转移到应用程序，只提供作为传输层协议的最基本功能。 TCP（TransmissionControlProtocol）：TCP充分实现了数据传输时的各种控制功能，可以进行丢包的重发控制、对乱序的分包进行顺序控制。此外，TCP作为一种面向有链接的协议，只有在确认通信对端存在时才会发送数据，从而可以控制通信流量的浪费。 TCP通过检验和、序列号、确认应答、重发控制、连接管理以及窗口控制等机制实现可靠性传输。 如何加以区分使用？ TCP用于传输层有必要实现可靠性传输的情况。UDP主要用于对高速传输和实时性有较高要求的通信或广播通信。 区别： 1）TCP面向连接;UDP是无连接的，发送数据之前不需要建立连接。 2）TCP提供可靠的服务。TCP传送的数据无差错，不丢失，不重复，且按序到达；UDP尽最大努力交付，不保证可靠交付。 3）TCP面向字节流，实际上TCP把数据看成一串无结构的字节流；UDP是面向报文的，UDP没有拥塞控制，网络出现拥塞不会使源主机的发送速率降低。 4）每一条TCP连接只能是点对点的；UDP支持一对一、一对多、多对一和多对多的交互通信 5）TCP首部开销20字节；UDP首部开销8字节； 6）TCP逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道 3.TCP报文结构。 IP结构 首部固定长度20字节，所有IP数据报必须具有。 可选字段，长度可变。 一、单链表 目录 1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表，其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级链表称一级单链表。 7.单链表交换任意两个元素（不包括表头） 8.判断单链表是否有环？如何找到环的“起始”点？如何知道环的长度？ 9.判断两个单链表是否相交 10.两个单链表相交，计算相交点 11.用链表模拟大整数加法运算 12.单链表排序 13.删除单链表中重复的元素 首先写一个单链表的C#实现，这是我们的基石： public class Link { public Link Next; public string Data; public Link(Link next, string data) { this.Next = next; this.Data = data; } } 其中，我们需要人为地在单链表前面加一个空节点，称其为head。例如，一个单链表是1->2->5，如图所示： 对一个单链表的遍历如下所示： static void Main(string[] args) { Link head = GenerateLink(); Link curr = head; while (curr != null) { Console.WriteLine(curr.Data); curr = curr.Next; } } 1.单链表反转 这道题目有两种算法，既然是要反转，那么肯定是要破坏原有的数据结构的：算法1：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext： public static Link ReverseLink1(Link head) { Link curr = head.Next; Link next = null; Link nextnext = null; //if no elements or only one element exists if (curr == null || curr.Next == null) { return head; } //if more than one element while (curr.Next != null) { next = curr.Next; //1 nextnext = next.Next; //2 next.Next = head.Next; //3 head.Next = next; //4 curr.Next = nextnext; //5 } return head; } 算法的核心是while循环中的5句话 我们发现，curr始终指向第1个元素。 此外，出于编程的严谨性，还要考虑2种极特殊的情况：没有元素的单链表，以及只有一个元素的单链表，都是不需要反转的。 阿里校园招聘历年经典面试题汇总：算法工程师 （1）、jvm 原理 （2）、minor GC 与 Full GC （3）、HashMap 实现原理 （4）、java.util.concurrent 包下使用过哪些 （5）、concurrentMap 和 HashMap 区别 （6）、信号量是什么，怎么使用？ （7）、阻塞队列了解吗？怎么使用？ （8）、JAVA NIO 是什么？ （9）、类加载机制是怎样的 （10）、什么是幂等性 （11）、有哪些 JVM 调优经验 （12）、分布式 CAP 了解吗？ （13）、hdfs怎么添加Datanode,添加后hdfs会有什么操作？ （14）、Hbase 跟关系数据库对比优缺点？为什么 Hbase 索引速度快 （15）、Hbase 大压缩与小压缩区别 （16）、Hive 与 Hbase 的使用场景 （17）、简单说说Spark功能，spark 与hive有无依赖关系？ （18）、zookeeper 有什么应用场景，怎么选举的？3 个节点挂掉一个能正常工作吗？ （19）、Hbase 中 zookeaper 作用 （20）、Hbase 写操作什么时候返回 （21）、mysql 有哪些存储引擎？各自特点 （22）、用过哪些设计模式？怎样实现线程安全单例模式？ （23）、用过哪些RPC框架？ （24）、什么是AOP？ （25）、决策树算法怎么实现的？ （26）、java垃圾回收会出现不可回收的对象吗？怎么解决内存泄露问题？怎么 定位问题源？ （27）、终止线程有几种方式？终止线程标记变量为什么是 valotile 类型？（28）、用过哪些并发的数据结构？ cyclicBarrier 什么功能？信号量作用？数据库读写阻塞怎么解决？ （29）、乐观锁与悲观锁，怎么实现乐观锁？ （30）、开发过分布式框架？怎么实现分布式事务？ （31）、spark streaming与storm区别？ （32）、找到最大子数组的 start,和end下标 （33）、用过 CDH中什么任务调度？ （34）、spark streaming时间间隔设置很小会出现什么状况？ （35）、搜索引擎了解多少？你认为搜索引擎的难点在哪里？ （36）、RPC 了解吗？怎么监控 RPC 状态，找出出现问题的 RPC 连接？（37）、spring 框架了解多少？ （38）、flume应用场景 （39）、找出一串字符中第一个不重复字符的下标。 点击查看详细面经〉〉〉〉〉〉〉〉〉〉〉〉 更多精品干货>>>>>>>>>>> 更多阿里机器学习/数据挖掘经典面试题 其他名企机器学习/数据挖掘经典面试题 新人面试常见100道问题及回答 面试的形式有多种，有一个面试官对一个应聘者，也有多对一，一对多，多对多；无论面试的形式有多少，都是围绕考核应聘者的素质是否符合所招聘岗位的要求而展开的。而企业想了解求职者就必须通过问答的形式，这里给大家总结了面试常见100道问题以及回答和点评： 一：工作动机与个人愿望 问题：你现在最感兴趣的是什么？ 回答：做个人网站，练习口语，但越做越感到自己知识欠缺。 点评：可以简述你的兴趣，及这个兴趣带给你个性或能力的正面效果。 问题：你认为这份工作最重要的是什么？ 回答：最重要的是对自己的挑战和提高。 点评：对工作要加上自己的看法。 问题：你是否可以接受加班？ 回答：我愿意接受挑战。在自己责任范围内的工作，不能算是加班。 点评：这是面试者针对应聘者的工作热忱而提的问题，因无理的加班不一定是好的。 问题：请问你有什么样的工作观？ 回答：我认为工作是为了实现自己的人生价值，发挥自己的最大潜能，解决自己的生活问题。 点评：此话是问工作在你的生活中意味着什么？为何而工作？从工作中得到了什么？几年后想变成怎样等。因此，别把它想得太复杂，可根据自己的具体情况回答。 问题：你为何要跳槽？ 回答：虽然在前面公司工作挺顺的，同事间合作也很愉快，但我感到贵公司更适合我的发展。 点评：公司根据你跳槽原因，意在了解你的就业动机。 问题：在公司想做什么样的工作？ 回答：现在想在某工作方面冲刺，将来则希望能在某方面努力等。朝自己想要的目标陈述即可。 点评：同时招聘很多职种的公司，最有可能问到这样的问题，这是判断应聘者个人的能力倾向。面试者如果不论职种都回答“可以”的话，反而会让人怀疑工作态度。如果这家公司只招聘一个职种，还是被问到这个问题时，是为了确认应聘者有无犹豫，应聘者只要清楚的叙述自己想做的事就可以了。 问题：你为何选择应聘我们公司？ 一、递归和分制策略 汉诺塔递归实现： Void hannoi(int n,char x,char y,char z) { if (n ==1) move(x,1,z);//printf(“%i Move disk %i from %c to %c \n”,++c,n,x,z) //将编号1从x移到z else{ hanoi(n-1, x,z,y);//将x上编号1至n-1的移到y，z做辅助 move(x,n,z);// 将编号n从x移到z hanoi(n-1, y,x,z);// 将y上编号1至n-1的移到z，x做辅助 } } 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了 本来由编译器做的事情，优化效果不明显。 2.用递推来实现递归函数。 3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 排序总结 直接插入排序： void insertSort(listtp & r) { for(i=2; i<=n; i++) { r[0]=r[i]; /* 设置监视哨*/ j=i-1; k=r[i].key; while(j>0&&r[j].key>k)/* 大值的记录后移*/ { r[j+1]=r[j]; j--; } r[j+1]=r[0]; /*插入位置*/ } } /* straisort */ 希尔排序：将整个序列划分成若干子序列，分别进行直接插入排序。 void ShellSort(SeqList R,int dlta[],int t) { For(k=0;k Problem 1 : Is it a loop ? （判断链表是否有环？） Assume that wehave a head pointer to a link-list. Also assumethat we know the list is single-linked. Can you come up an algorithm to checkwhether this link list includes a loop by using O(n) time and O(1) space wheren is the length of the list? Furthermore, can you do so with O(n) time and onlyone register? 方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进2个节点，则最多2N，后两个指针可以重合；如果无环，则正常停止。 同样的，可以找到链表的中间节点。同上。 Problem 2：设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。 提示：双指针查找 Problem 3：用最简单的方法判断一个LONG整形的数A是2^n（2的n次方）提示：x&(x-1) Problem 4：两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？ 提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，不合理。 Problem 5：给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。 法1：使用hash表。使用a中元素创建hash表，hash控制在适当规模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，则将相应的hash表项删除，当hash表项少于某个阈值时，将a中新元素重新hash。再次循环。 法2：对于hash表项增加一项记录属于的文件a，b。只要不存在的表项即放入hash表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频繁。 Problem 6：给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。 提示：将每个的单词按照字母排序，则兄弟单词拥有一致的字母排序（作为单词签名）。使用单词签名来查找兄弟单词。 Problem 7：五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。 链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现 1.struct Node{ 2.int data; 3.Node*next; 4.}; 5.void reverse(Node*head,Node*end){ 6.if(head==NULL||end==NULL)return; 7.Node*pre=NULL,*cur=head,*stop=end->next; 8.while(cur!=stop){ 9.Node*nxt=cur->next; 10.cur->next=pre; 11.pre=cur; 12.cur=nxt; 13.} 14.} 15. 16.Node*reverseAll(Node*head,int k){ 17.if(head==NULL||k<=0)return NULL; 18.Node*cur=head; 19.for(int i=0;i 微软四道经典算法面试题(附思路) 1.比较经典的四个算法题，目前只收集到相关的思路和个别题目的解法，不断更新中 2. 1.一个整数数列，元素取值可能是0~65535中的任意一个数，相同数值不会重复出 现。0是例外，可以反复出现。 3.请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相 邻。 4.注意： 5.- 5个数值允许是乱序的。比如： 8 7 5 0 6 6.- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4 7.- 0可以多次出现。 8.- 复杂度如果是O(n2)则不得分。 9. 2.设计一个算法，找出二叉树上任意两个结点的最近共同父结点。 10.复杂度如果是O(n2)则不得分。 11.3.一棵排序二叉树，令 f=(最大值最小值)/2，设计一个算法，找出距离f值最近、 大于f值的结点。 12.复杂度如果是O(n2)则不得分。 13.4.一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数， 相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N 1。 14.复杂度最好是O(n)，如果是O(n2)则不得分。 15.思路分析 16.1.非0最大-非0最小 1 <=5 ==> 非0最大-非0最小 <=4 17.2.如果每个节点包含父亲指针，把两个节点到根的路径都记录下来，两条路径的最 后面的元素肯定相同， 18.从两条路径的最后一个元素向前比较，直到第一次出现分叉为止，就可以找到最近 节点。复杂度为O（n）， 19.路径最长可能是n 20.如果不包含父亲节点，那就先前序遍历二叉树，遍历的时候可以像哈夫曼树那样左 右01编号， 21.记录给定两节点的到达路径，最后比较两个0，1序列的前面位数，直到出现不相等 为止，就找到最近父节点， 22.复杂度也是O（n） 23.3.找出最大值，最小值，复杂度都是O（h），然后搜索f，可以找到f应该插入的 位置，复杂度也是O（h）， 24.再找f的后继，复杂度也是O（h），h最大可能是n，所以总体最坏情况复杂度就 是O（n） 25.4.先排序，复杂度O（nlgn），然后用两个指示器（front和back）分别指向第一 个和最后一个元素，如果 26.A[front] A[back]>N 1，则back–； 27.如果A[front] A[back]=N 1，则计数器加1，back–，同时front ； 28.如果A[front] A[back] 重复上述步骤，O（n）时间找到所有数对，总体复杂度 为O（nlgn） 29.题目分析 30.第1题：首先扫描一遍求出非0平均值，然后再扫描一遍即可判断，复杂度：O(n) 31.第2题，是一个送分题，可以设计一个相当巧妙的数据结构，其复杂度为O(n) 32.第3题，也是送分题，扫描几次即可 33.第4题，送分题。牺牲空间即可完成。 34.具体算法 35.1.思路是非0最大值-非0最小值 <=数组长度-1 36.我觉得这道题的前提非常重要 37.p ublic boolean isContiguous(int[] array) 38. { 39. int min=-1; 40. int max=-1; 41. for(int i=0;i 1、将一整数逆序后放入一数组中（要求递归实现） void convert(int *result, int n) { if(n>=10) convert(result+1, n/10); *result = n%10; } int main(int argc, char* argv[]) { int n = 123456789, result[20]={}; convert(result, n); printf("%d:", n); for(int i=0; i<9; i++) printf("%d", result[i]); } 2、求高于平均分的学生学号及成绩（学号和成绩人工输入） double find(int total, int n) { int number, score, average; scanf("%d", &number); if(number != 0) { scanf("%d", &score); average = find(total+score, n+1); if(score >= average) printf("%d:%d\n", number, score); return average; } else { printf("Average=%d\n", total/n); return total/n; } } int main(int argc, char* argv[]) { find(0, 0); } 3、递归实现回文判断（如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序）int find(char *str, int n) { if(n<=1) return 1; else if(str[0]==str[n-1]) return find(str+1, n-2); else return 0; } int main(int argc, char* argv[]) { char *str = "abcdedcba"; printf("%s: %s\n", str, find(str, strlen(str)) ? "Yes" : "No"); 常见算法笔试或面试题 1、Is it a loop ? （判断链表是否有环？） Assume that we have a head pointer to a link-list. Also assume that we know the list is single-linked. Can you come up an algorithm to check whether this link list includes a loop by using O(n) time and O(1) space where n is the length of the list? Furthermore, can you do so with O(n) time and only one register? 方法：使用两个指针，从头开始，一个一次前进一个节点，一个前进2个节点，则最多2N，后两个指针可以重合；如果无环，则正常停止。同样的，可以找到链表的中间节点。同上。 2、设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。 提示：双指针查找 3、用最简单的方法判断一个LONG整形的数A是2^n（2的n次方） 提示：x&(x-1) 4、两个烧杯，一个放糖一个放盐，用勺子舀一勺糖到盐，搅拌均匀，然后舀一勺混合物会放糖的烧杯，问你两个烧杯哪个杂质多？ 提示：相同。假设杂质不等，那么将杂质放回原杯中，则杯中物体重量必变化，不合理。 5、给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。 方法一：使用hash表。使用a中元素创建hash表，hash控制在适当规模。在hash中查找b的元素，找不到的url先存在新文件中，下次查找。如果找到，则将相应的hash表项删除，当hash表项少于某个阈值时，将a中新元素重新hash。再次循环。 方法二：对于hash表项增加一项记录属于的文件a，b。只要不存在的表项即放入hash表中，一致的项则删除。注意：可能存在很多重复项，引起插入，删除频繁。 6、给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单 25个最难的面试问题(附答案).txt点的是烟抽的却是寂寞……不是你不笑，一笑粉就掉！人又不聪明，还学别人秃顶。绑不住我的心就不要说我花心！再牛b的肖邦，也弹不出老子的悲伤！活着的时候开心点，因为我们要死很久。请你以后不要在我面前说英文了，OK？最难的25个面试问题应对策略 1.介绍你自己 这个问题通常是一个面试的开始的第一个问题,要额外的小心不要滔滔不绝。尽可能的让你的回答在一分钟,最多2分钟的时间内结束。你的回答应该包含以下4个主题:早期生活,教育背景,工作背景以及最近的工作经验。要着重强调最后的那个主题。要牢记这个问题通常是一个热身的问题,不要把你的最重要的观点浪费在这个问题上。字串2 2.你对我们公司有什么样的了解 你必须能够谈论关于这个公司的产品,服务,收入,业界声望,形象,目标,存在的问题,管理风格,职工,历史和企业文化等问题。但是不要表现出你对这个公司的一切都了如指掌。让你的回答能够体现出你对该公司做了一些研究,但是不要让面试官被你打败(overwhelm),并表现出你希望能够了解关于公司更多的情况。 你可以用这样的态度来开始回答问题:“在我的寻找工作的过程中,我调查研究了很多公司,出于如下的理由,贵公司是我感兴趣的公司之一:”。 用一个积极的态度来回答这个问题,不要这样说:“每个人都告诉我这个公司处于困境中,有各种样的麻烦,这就是我来这儿的原因”,即是那的确是你在这儿的理由。 字串2 3.为什么你希望来我们公司工作? 最糟糕的答案就是“因为我喜欢人”。要是你喜欢的是动物,那你去哪工作呢?在这个问题的回答上,并且贯穿整个面试的过程中,一个优秀的答案总是来自于你所作的调查研究,这样的话你可以从公司的需要那个方面来回答。你可能说你的研究表明这个公司所做的工作正是你说希望参与的,并且他们做这个工作的方式极大的吸引了你。例如,如果这个公司由于强大的管理而著称,纳闷你的答案可以提到这个事实,并表示你希望成为这个小组的一员。如果这个公司着重强调研发,那么就强调你希望创造你的事物,而你知道这个公司非常鼓励这样的行为。如果这个公司强调经济控制,你的答案就应该包含对数字的热爱。 如果你觉得你必须捏造一个答案,例如如果这个公司强调研发,但是你觉得你必须提到这一点而实际上你对这根本不感兴趣,那么你可能根本不应该参加这个面试,因为你可能根本不会考虑在这个公司工作。 你的之前的准备必须包括对这个公司做详尽的了解,来避免到一个你无法发挥才干或者根本不想去的公司面试。大多数人都不擅长说谎,所以在面试中欺瞒面试官是一件很困难的事情。即使你成功的做到了这一点,你所获得的也只是一个你不想参加的工作 字串6 4.你可以为我们完成哪些其他人做不到的事情? 这个问题上,你有权利或者是义务来自吹自擂。谈论一些你完成工作的记录,提到你简历中的独特之处,或者列出你职业生涯中的成就。告诉别人,你的技能和兴趣在获取这些结果的 微软的22道数据结构算法面试题（含答案）1、反转一个链表。循环算法。 1 List reverse(List l) { 2 if(!l) return l; 3 list cur = l.next; 4 list pre = l; 5 list tmp; 6 pre.next = null; 7 while ( cur ) { 8 tmp = cur; 9 cur = cur.next; 10 tmp.next = pre; 11 pre = tmp; 12 } 13 return tmp; 14 } 2、反转一个链表。递归算法。 1 List resverse(list l) { 2 if(!l || !l.next) return l; 3 4 List n = reverse(l.next); 5 l.next.next = l; 6 l.next=null; 7 } 8 return n; 9 } 3、广度优先遍历二叉树。 1 void BST(Tree t) { 2 Queue q = new Queue(); 3 q.enque(t); 4 Tree t = q.deque(); 5 while(t) { 6 System.out.println(t.value); 7 q.enque(t.left); 9 t = q.deque(); 10 } 11 } ---------------------- 1class Node { 2 Tree t; 3 Node next; 4 } 5class Queue { 6 Node head; 7 Node tail; 8 public void enque(Tree t){ 9 Node n = new Node(); 10 n.t = t; 11 if(!tail){ 12 tail = head = n; 13 } else { 14 tail.next = n; 15 tail = n; 16 } 17 } 18 public Tree deque() { 19 if (!head) { 20 return null; 21 } else { 22 Node n = head; 23 head = head.next; 24 return n.t; 25 } 26} 4、输出一个字符串所有排列。注意有重复字符。 1char[] p; 2void perm(char s[], int i, int n){ 3 int j; 4 char temp; 5 for(j=0;j计算机常见算法面试题
百度笔试题及答案
算法经典面试题
面试逻辑题目汇总
教师资格证面试结构化真题解析思路综合分析类25道题
[第1题-60题汇总]微软数据结构+算法面试100题
面试常见问题计算机网络
算法大全-面试题-数据结构
阿里校园招聘历年经典面试题汇总：算法工程师
新人面试常见100道问题及回答
算法笔试题总结
25道常见算法面试题
美团面试算法题
微软四道经典算法面试题(附思路)
各大公司算法笔试题
经典算法类笔试或面试题及答案
25个最难的面试问题(附答案)
22道数据结构算法面试题
相关主题
文本预览