微软面试100题首次完整亮相[最终完美珍藏版].wps

1、1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/ 6 14/ / 4 8 12 16转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;2.设计包含min 函数的栈。定义栈的数据结构，要求添加

2、一个min 函数，能够得到栈的最小元素。要求函数min、push 以及pop 的时间复杂度都是O(1)。3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径

3、。3例如输入整数22 和如下二元树10/ 5 12/ 4 7则打印出两条路径：10, 12 和10, 5, 7。二元树节点的数据结构定义为：struct BinaryTreeNode / a node in the binary treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left child of nodeBinaryTreeNode *m_pRight; / right child of node;5.查找最小的k 个元素题目：输入n 个整数，输出 中最小的k 个。例如输入1，2，3，4，5，6，7 和8 8 个数

4、 ，则最小的4 个数 为1，2，3 和4。6 题题：10 时间，根据 排 出 个数，在 下排 出 的 个数要求下排每个数都是先 排 个数在下排出 的 数。排的 个数如下：0，1，2，3，4，5，6，7，8，9 一个例子，数值: 0,1,2,3,4,5,6,7,8,9: 6,2,1,0,0,0,1,0,0,00 在下排出 6 ，1 在下排出 2 ，2 在下排出 1 ，3 在下排出 0 .以此 .7 题个链表是相出个currency1向链表的指针，“如h1，h2， 个链表是相。为 问题，我们设个链表fi不fl 。4问题：1.如链表能有 ?2.如要求出个链表相的 一个节点 ?8 题此一“”的题， 中

5、题目 与 不大，。此 一题。1.有两个间，一间里有 ，一间有 的 个开，两个间是 开的，从一间里不能 到一间的 。在要求 两间一 ， 出 是 个开 的。有 2. 一 为 ， 要一根条为 。条 成 小 ，每 出一。如 只能将条 两 ， ?3. 一 一个链 表的 序。 在在不的 下一 。一 在一个 的链 表里 入一个节点，但不得穿越链 表。一 整理一个数组。 为 择 方?一 使通 符串相匹 。一个 符串。优速度。优空间。一个句子中的词的 序，“如将“我叫克丽丝”转换为“克丽丝叫我”，实 速度最快，移动最少。找到一个子 符串。优速度。优空间。“”两个 符串，O(n)时间和恒量空间。设 有一个1001

6、 个整数组成的数组， 整数是任意排 的，但是 知道所有的整数都在1 到1000(包括1000) 间。此外，除一个数 出 两 外， 他所有数 只出一 。设 只能 个数组一 处理，一 找出重复的 个数 。如 在运中使 辅助的存储方， 能找到不 方的 吗?不乘或加增加8 倍。 在同的方增加7 倍。9 题整数序 是不是二元查找树的 序 历结题目：输入一个整数数组，该数组是不是某二元查找树的 序 历的结。如是返回true，则返回false。例如输入5、7、6、9、11、10、8， 一整数序 是如下树的 序 历结：58/ 6 10/ / 5 7 9 11因此返回true。如输入7、4、6、5，没有 棵树的

7、 序 历的结是 个序 ，因此返回false。10 题翻转句子中currency1词的 序。题目：输入一个英文句子，翻转句子中currency1词的 序，但currency1词内 符的 序不变。句子中currency1词以空格符隔开。为currency1起见，标点符号和普通 母一处理。例如输入“I am a student.”，则输出“student. a am I”。11 题求二叉树中节点的最大距离.如我们把二叉树 成一个图，父子节点 间的连线 成是双向的，我们姑且定义“距离“为两节点 间边的个数。写一个序，求一棵二叉树中相距最远的两个节点 间的距离。12 题题目：求1+2+n，要求不能使乘除

8、、for、while、if、else、switch、case 等键 以及条件语句（A?B:C）。13 题：题目：输入一个currency1向链表，输出该链表中数 k 个结点。链表的数 0 个结点为链表的尾指针。链表结点定义如下：struct ListNodeint m_nKey;ListNode* m_pNext;614 题：题目：输入一个已经按升序排序过的数组和一个数 ，在数组中查找两个数，使得它们的和正好是输入的 个数 。要求时间复杂度是O(n)。如有多 数 的和等输入的数 ，输出任意一 即。例如输入数组1、2、4、7、11、15 和数 15。4+11=15，因此输出4 和11。15 题：

9、题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换 的二元查找树中，左子树的结点都大右子树的结点。和 两 方完成树的镜像转换。例如输入：8/ 6 10/ /5 7 9 11输出：8/ 10 6/ /11 9 7 5定义二元查找树的结点为：struct BSTreeNode / a node in the binary search tree (BST)int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nodeBSTreeNode *m_pRight; / right child of node;16 题：题

10、目（ ）：输入一颗二元树，从 往下按层打印树的每个结点，同一层中按照从左往右的 序打印。例如输入78/ 6 10/ / 5 7 9 11输出8 6 10 5 7 9 11。17 题：题目：在一个 符串中找到 一个只出 一 的 符。如输入abaccdeff，则输出b。析： 道题是2006 年google 的一道笔 题。18 题：题目：n 个数 （0,1,n-1）形成一个圆圈，从数 0 开始，每 从 个圆圈中删除 m 个数 （ 一个为当 数 ， 二个为当 数 的下一个数）。当一个数 删除 ，从 删除数 的下一个继续删除 m 个数 。求出在 个圆圈中剩下的最 一个数 。July：我想， 个题目，不少

11、 已经见识过 。19 题：题目：定义Fibonacci 数 如下：/ 0 n=0f(n)= 1 n=1 f(n-1)+f(n-2) n=2输入n，最快的方求该数 的 n 项。析：在很多C 语言教科书中讲到函数的时候，都会Fibonacci 为例子。因此很多序员 道题的解非常熟悉，但.呵呵， 知道的。20 题：题目：输入一个表示整数的 符串，把该 符串转换成整数 输出。例如输入 符串“345“，则输出整数345。821 题2010 年中兴 题求解：输入两个整数n 和m，从数 1，2，3.n 中随意取几个数,使 和等m ,要求将 中所有的能组 出 .22 题：有4 的 和4 的 ， 先 任意两 ，

12、 在A、B、C 任意两 ，A、B、C 都以 见 两 的 ， 完 他们 是 的 ，A 不知道，B 不知道，C 不知道， A 知道 。教如何 理，A 是 知道的。如序， 实 23 题：最currency1，最快速的方计 出下 个圆形是和正方形相。“3D 标 点(0.0,0.0,0.0)圆形:径r = 3.0圆 o = (*.*, 0.0, *.*)正方形:4 个 标;1:(*.*, 0.0, *.*)2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)4:(*.*, 0.0, *.*)24 题：链表 ，（1）.currency1链表 ，（2） 链表25 题：写一个函数,它的 形是i

13、nt continumax(char *outputstr,char *intputstr)9能：在 符串中找出连续最 的数 串， 把 个串的 度返回，把 个最 数 串 中一个函数 数outputstr 所指内存。例如：“abcd12345ed125ss123456789“的首 intputstr ，函数将返回9，outputstr 所指的值为12345678926.左转 符串题目：定义 符串的左转 ：把 符串 的个 符移动到 符串的尾。如把 符串abcdef 左转2 得到 符串cdefab。 实 符串左转的函数。要求时间 度为n 的 符串 的复杂度为O(n)，辅助内存为O(1)。27.cur

14、rency1“问题题目：一个“有n ，如一 以currency11 ，也以currency12 。求有多少currency1， 析 的时间复杂度。道题最fi经常出 ，包括MicroStrategy 等“”重fl 的 都先 过个 道题为 题或 笔 题。28.整数的二 表示中1 的个数题目：输入一个整数，求该整数的二 表中有多少个1。例如输入10， 二 表示为1010，有两个1，因此输出2。析：是一道很 的查运 的 题。包括 在内的很多 都 过 道题。29.栈的push、pop 序 题目：输入两个整数序 。 中一个序 表示栈的push 序，10一个序 有没有能是 的pop 序。为 currency

15、1起见，我们设push 序 的任意两个整数都是不相等的。“如输入的push 序 是1、2、3、4、5， 4、5、3、2、1 有能是一个pop 。因为以有如下的push 和pop 序 ：push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，得到的pop 序 是4、5、3、2、1。但序 4、3、5、1、2 不能是push 序 1、2、3、4、5 的pop 序 。30.在从1 到n 的正数中1 出 的 数题目：输入一个整数n，求从1 到n n 个整数的 表示中1 出 的 数。例如输入12，从1 到12 整数中包含1 的数 有1，10，11 和1

16、2，1 一出 5 。析： 是一道为的google 题。31.为 题：一 ”的结构的图， 最路径（要求5 ）32.有两个序 a,b，大小都为n,序 元素的值任意整数， 序要求：通过换a,b 中的元素，使序 a 元素的和与序 b 元素的和 间的最小。例如:var a=100,99,98,1,2, 3;var b=1, 2, 3, 4,5,40;33.实 一个的 符匹 ：一串很 符串，要求找到符 要求的 符串，例如目的串：1231*3*2 ,12*3 都要找出 实 是 一和。1134.实 一个 。 的 为：一个 线将int 的数入 ，一个 线将int 的数出 35.求一个中最大的二(元素和最大).如

17、:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)写出 ;(2) 析时间复杂度;(3)C 写出键 36 题-40 题（有题目 CSDN 的 ，已标 ）：36. ：longzuo笔 ：n “ ， 号为0，1，2。n-1，已知它们 间的实 “，存储在一个二数组wnn中，wij 的值 表号为i，j 的 中 的一 。所以wij=i 或 j， 在 出它们的出 序， 存储在数组ordern中，“如ordern = 4,3,5,8,1.， 一 “ 是4 3，5 8。.， ，同一 的所有 排 不 ，即以随排，下一 一 的 按照 序， 两两“，“如能是4 5,直出 一

18、实 ， 出二数组w，一数组order 和输出“ 的数组resultn，求出result。37.有n 个 为m+1 的 符串，如某个 符串的最 m 个 符与某个 符串的 m 个 符匹 ，则两个 符串以 ，问 n 个 符串最多以连成一个多 的 符串，如出 ，则返回 。1238.度 ：1. （只能“”，不能重）从一 小 中找出 中 一一个”的，使x ，最多以从y 个小 中找出”的 个，求y 与x 的。2.有一个很大很大的输入，大到没有存储 以将 存储下 ，且只输入一 ，如何从 个输入中随取得m 个。3.大量的URL 符串，如何从中除重复的，优时间空间复杂度39.有道笔 ：(1).求一个二叉树中任意两

19、个节点间的最大距离，两个节点的距离的定义是 两个节点间边的个数，“如某个 子节点和父节点间的距离是1，和相 弟节点间的距离是2，优时间空间复杂度。(2).求一个有向连通图的 点， 点的定义是，如除此节点和与 相的边，有向图不 连通，描述 。40. 度研发笔 题 ：zp1553348771)设计一个栈结构，满足一下条件：min，push，pop 的时间复杂度为O(1)。2)一串首尾相连的珠子(m 个)，有N (N2-3 和2-3-5 为1-2-3-5外只能输出结，不能修改两个链表的数据。43.和非 方实 二叉树的 序 历。44. 题：1.设计一个魔方（六 ）的序。2.有一千万条信，有重复，以文

20、文件的形保存，一一条，有重复。5 时间，找出重复出 最多的 10 条。3.收藏 1 万条url， 在 一条url，如何找出相的url。（ 官不解释何为相）45.雅虎：1. 一个整数，存在一 运 ， 中任意元素加一时，要 相 （ 下左右）某一个元素也加一， 出一正数， 是能够一个全零经过 述运 得到。2.一个整数数组， 度为n，将 为m 份，使各份的和相等，求m 的最大值“如3，2，4，3，6 以 成3，2，4，3，6 m=1;3,62,4,3 m=23,32,46 m=3 所以m 的最大值为346.狐：四 括号以有多少 匹 排 方“如两 括号以有两 ：（）（）和（）1447.创新 ：求一个数组

21、的最 减子序 “如9，4，3，2，5，4，3，2的最 减子序 为9，5，4，3，248. ：一个数组是一个减数 左移形成的，“如4，3，2，1，6，5是6，5，4，3，2，1左移两形成的，在 数组中查找某一个数。49.一道 很吓 的 题：如何 n 个数 排序，要求时间复杂度O(n)，空间复杂度O(1)50. 有道笔 ：1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 两个节点间边的个数，“如某个 子节点和父节点间的距离是1，和相 弟节点间的距离是2，优时间空间复杂度。2.求一个有向连通图的 点， 点的定义是，如除此节点和与 相的边，有向图不 连通，描述 。-51.和为n 连续

22、正数序 。题目：输入一个正数n，输出所有和为n 连续正数序 。例如输入15，1+2+3+4+5=4+5+6=7+8=15，所以输出3 个连续序 1-5、4-6 和7-8。析： 是 的一道 题。52.二元树的深度。题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点 经过的结点（含根、叶结点）形成树的一条路径，最 路径的 度为树的深度。15例如：输入二元树：10/ 6 14/ / 4 12 16输出该树的深度3。二元树的结点定义如下：struct SBinaryTreeNode / a node of the binary treeint m_nValue; / value of nod

23、eSBinaryTreeNode *m_pLeft; / left child of nodeSBinaryTreeNode *m_pRight; / right child of node;析： 道题 质 还是查二元树的 历。53. 符串的排 。题目：输入一个 符串，打印出该 符串中 符的所有排 。例如输入 符串abc，则输出 符a、b、c 所能排 出 的所有 符串abc、acb、bac、bca、cab 和cba。析： 是一道很好的查 理解的题，因此在过一年中频繁出 在各大 的 、笔 题中。54.调整数组 序使奇数偶数 。题目：输入一个整数数组，调整数组中数 的 序，使得所有奇数数组的 ，所

24、有偶数数组的 。要求时间复杂度为O(n)。55.题目： CMyString 的声 如下：class CMyStringpublic:CMyString(char* pData = NULL);16CMyString(const CMyStringCMyString(void);CMyStringprivate:char* m_pData;实 赋值运 符的重载函数，要求异常安全，即当 一个 象 赋值时发异常，象的状态不能改变。56.最 串。题目：如 符串一的所有 符按 在 符串中的 序出 在外一个 符串二中，则 符串一 为 符串二的子串。注意， 不要求子串（ 符串一）的 符必须连续出 在 符串二中。写一个函数，输入两个 符串，求它们的最 子串， 打印出最 子串。例如：输入两个 符串BDCABA 和ABCBDAB， 符串BCBA 和BDAB 都是是它们的最子串，则输出它们的 度4， 打印任意一个子串。析：求最 子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一重fl 的 像MicroStrategy 都把它当 题。57.个栈实 。题目：某 的声 如下：template class CQueuepublic: