精选微软等数据结构+算法面试100题[第61-80题]
--最新整理公布
昨日,11.19,最新整理了,第61-80题,现在公布。
可以这么说,绝大部分的面试题,都是这100道题系列的翻版,
此微软等公司数据结构+算法面试100题系列,是极具代表性的经典面试题。
我曾经暗暗问自己,不知道我是否把面试题基本上都搜集整理尽了,
而当然,对你更重要的是,我自个还提供了答案下载,提供思路,呵。
所以,这份资料+答案,在网上是独一无二的。
闲不多说,接下来,你可以尽情的享用了,朋友。
现在首次公布整理的第61-80题(11.19最新整理公布):
---------------------------------------
[整理I]精选微软等公司数据结构+算法面试100题 [第1-40题] (博文)
http://blog.csdn.net/v_JULY_v/archive/2010/10/27/5968678.aspx
[整理II]精选微软等公司数据结构+算法面试100题 [第41-60题] (博文)
http://blog.csdn.net/v_JULY_v/archive/2010/10/29/5975019.aspx
[汇总I]精选微软等公司数据结构+算法面试100题[第1-60题汇总](博文)
http://blog.csdn.net/v_JULY_v/archive/2010/11/12/6004660.aspx
61.找出数组中两个只出现一次的数字
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
分析:这是一道很新颖的关于位运算的面试题。
62.找出链表的第一个公共结点。
题目:两个单向链表,找出它们的第一个公共结点。
链表的结点定义为:
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
分析:这是一道微软的面试题。
微软非常喜欢与链表相关的题目,因此在微软的面试题中,链表出现的概率相当高。
63.在字符串中删除特定的字符。
题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。
例如,输入”They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”。
分析:这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部分,
因为写程序操作字符串能很好的反映我们的编程基本功。
64. 寻找丑数。
题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。
例如6、8都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。
分析:这是一道在网络上广为流传的面试题,据说google曾经采用过这道题。
65.输出1到最大的N位数
题目:输入数字n,按顺序输出从1最大的n位10进制数。
比如输入3,则输出1、2、3一直到最大的3位数即999。
分析:这是一道很有意思的题目。看起来很简单,其实里面却有不少的玄机。
66.颠倒栈。
题目:用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5},1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1},5处在栈顶。
67.俩个闲玩娱乐。
1.扑克牌的顺子
从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。
2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。
2.n个骰子的点数。
把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。
输入n,打印出S的所有可能的值出现的概率。
68.把数组排成最小的数。
题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。
例如输入数组{32, 321},则输出这两个能排成的最小数字32132。
请给出解决问题的算法,并证明该算法。
分析:这是09年6月份百度的一道面试题,
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
69.旋转数组中的最小元素。
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个排好序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。
分析:这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性,我们应该能找到更好的解法。
70.给出一个函数来输出一个字符串的所有排列。
分析:简单的回溯就可以实现了。当然排列的产生也有很多种算法,去看看组合数学,
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。
这些算法的理解需要一定的数学功底,
也需要一定的灵感,有兴趣最好看看。
71.数值的整数次方。
题目:实现函数double Power(double base, int exponent),求base的exponent次方。
不需要考虑溢出。
分析:这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码:
double Power(double base, int exponent)
{
double result = 1.0;
for(int i = 1; i <= exponent; ++i)
result *= base;
return result;
}
72.
题目:设计一个类,我们只能生成该类的一个实例。
分析:只能生成一个实例的类是实现了Singleton模式的类型。
73.对策字符串的最大长度。
题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。
分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的加强版。
74.数组中超过出现次数超过一半的数字
题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
分析:这是一道广为流传的面试题,包括百度、微软和Google在内的多家公司
都曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,除了较好的编程能力之外,
还需要较快的反应和较强的逻辑思维能力。
75.二叉树两个结点的最低共同父结点
题目:二叉树的结点定义如下:
struct TreeNode
{
int m_nvalue;
TreeNode* m_pLeft;
TreeNode* m_pRight;
};
输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
76.复杂链表的复制
题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:
struct ComplexNode
{
int m_nValue;
ComplexNode* m_pNext;
ComplexNode* m_pSibling;
};
下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。
为简单起见,指向NULL的指针没有画出。
请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。
//图,接下来,自会补上。July、11.19.
分析:在常见的数据结构上稍加变化,这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目,
我们需要较快的反应能力,对数据结构透彻的理解以及扎实的编程功底。
77.关于链表问题的面试题目如下:
题一、 给定单链表,检测是否有环。
使用两个指针p1,p2从链表头开始遍历,p1每次前进一步,p2每次前进两步。
如果p2到达链表尾部,说明无环,否则p1、p2必然会在某个时刻相遇(p1==p2),从而检测到链表中有环。
题二、 给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。
如果head1==head2,那么显然相交,直接返回head1。
否则,分别从head1,head2开始遍历两个链表获得其长度len1与len2,假设len1>=len2,
那么指针p1由head1开始向后移动len1-len2步,指针p2=head2,
下面p1、p2每次向后前进一步并比较p1p2是否相等,如果相等即返回该结点,
否则说明两个链表没有交点。
题三、 给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。
运用题一,我们可以检查链表中是否有环。
如果有环,那么p1p2重合点p必然在环中。从p点断开环,方法为:p1=p, p2=p->next,
p->next=NULL。此时,原单链表可以看作两条单链表,一条从head开始,另一条从p2开始,
于是运用题二的方法,我们找到它们的第一个交点即为所求。
题四、只给定单链表中某个结点p(并非最后一个结点,即p->next!=NULL)指针,删除该结点。
办法很简单,首先是放p中数据,然后将p->next的数据copy入p中,接下来删除p->next即可。
题五、只给定单链表中某个结点p(非空结点),在p前面插入一个结点。
办法与前者类似,首先分配一个结点q,将q插入在p后,
接下来将p中的数据copy入q中,然后再将要插入的数据记录在p中。
78.链表和数组的区别在哪里?
分析:主要在基本概念上的理解。
但是最好能考虑的全面一点,现在公司招人的竞争可能就在细节上产生,
谁比较仔细,谁获胜的机会就大。
79.
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法?
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法?
3.请编写能直接实现strstr()函数功能的代码。
80.阿里巴巴一道笔试题
引自baihacker
问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.
//第81-100题正在整理中。
---------------------------------------------------------------------------------------
整理资源下载地址:
题目系列:
1.[最新整理公布][汇总II]微软等数据结构+算法面试100题[第1-80题]
http://download.csdn.net/source/2846055
2.[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题]
http://download.csdn.net/source/2778852
3.[第二部分]精选微软等公司结构+算法面试100题[前41-60题]:
http://download.csdn.net/source/2811703
4.[第1题-60题汇总]微软等数据结构+算法面试100题
http://download.csdn.net/source/2826690
答案系列:
5.[最新答案V0.3版]微软等数据结构+算法面试100题[第21-40题答案]
http://download.csdn.net/source/2832862
6.[答案V0.2版]精选微软数据结构+算法面试100题[前20题]--修正
http://download.csdn.net/source/2813890
//此份答案是针对最初的V0.1版本,进行的校正与修正。
7.[答案V0.1版]精选微软数据结构+算法面试100题[前25题]
http://download.csdn.net/source/2796735
更多资源,下载地址:
http://v_july_v.download.csdn.net/
谢谢。
---------------------------------------
各位,我已经针对本100题,开了一帖,作为本微软等100题系列的永久维护地址。
真诚欢迎,各位,前去帖子上,写下对这100道题中任何一题的思路或想法。
帖子地址:
横空出世,席卷Csdn:记微软等100题系列数次被荐[100题维护地址] 11.26日
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html
本人July对以上所有任何内容和资料享有版权,转载请注明出处。
向你的厚道致敬。谢谢。
2010年11月22日。
分享到:
相关推荐
NSGA-III 算法在 C++ 中的实现:
基于uCOS-III+STemWin+FatFS+ARM_DSP_Lib的示波器源码
数据结构与算法分析java版 Table of Contents Data Structures and Algorithms in Java - 4 Introduction - 7 Part I Chapter 1 - Overview - 11 Chapter 2 - Arrays - 29 Chapter 3 - Simple Sorting -...
https://www.mathworks.com/matlabcentral/fileexchange/60678-nsga-iii-in-matlab?s_tid=srchtitle 另外,这是开源资源,纯粹为了学术交流,个别人不要拿去重复上传。CSDN设置了最低积分限制,想免费都不行了。
FreeModbus--RTU--Master+Slave--uCOSIII--STM32F407工具.rar
实验一 线性表及其应用 一、 实验目的和要求 1、掌握线性表的插入、删除、查找等基本操作设计与实现 2、学习利用线性表提供的接口去求解实际问题 3、熟悉线性表的的存储方法 二、 实验内容和原理 1、实验内容:设计...
NSGA-III算法
数据结构与算法分析(Java版英文)目录 PartI Chapter1-Overview Chapter2-Arrays Chapter3-Simple Sorting PartII Chapter4--Stacks and Queues Chapter5-linked lists Chapter^-Recursion...
多目标遗传算法(NSGA-III)matlab源代码 多目标遗传算法(NSGA-III)matlab源代码 多目标遗传算法(NSGA-III)matlab源代码 多目标遗传算法(NSGA-III)matlab源代码已验证
μCOS-III+STemWin+FatFs+Lwip+UIP+USB综合程序,不错的学习资料
μCOS-III+STemWin+FatFs+Lwip+UIP+USB综合程序V1.21d.rar
100-uCOS-III-ST-STM32-003,uCOS-3英文版,解压打开即可
stm32操作系统的学习操作,大家可以参考学习,STM32F4x7+freertos+lwip+ssl+MQTT-(MDK5)稳定可靠+W5500 MQTT例程和说明+LWIP+UCOSIII+UCOSII
STM32F4x7+freertos+lwip+ssl+MQTT-(MDK5)稳定可靠+W5500 MQTT例程和说明+LWIP+UCOSIII+UCOSII源码.zip
ThinkPad -- Integrated Bluetooth III微软蓝牙
美国国家标准学会根据文章,NSGA-III算法在C ++中的实现: Kalyanmoy Deb和Himanshu Jain,一种使用基于参考点的非支配排序方法的进化多目标优化算法,第一部分:解决盒子约束问题。 IEEE进化计算学报,第1卷。 18,...
NSGA-III 首先定义一组参考点。然后随机生成含有 N 个(原文献说最好与参考点个数相同)个体的初始种群,其中 N 是种群大小。接下来,算法进行迭代直至终止条件满足。在第 t 代,算法在当前种群 Pt的基础上,通过...
在STM32F429下移植了操作系统UCOSIII(现以开源)、基于LAN8720的LWIP以及RS485、FreeModBus/tcp,为了方便大家移植,上传,减少工作量
最新uCOS-III,关于LPC17XX平台的官方电子书,Jean J.Labrosse写的。