【史上最全】算法面试题集锦.pdf

微软等公司数据结构+算法面试 100 题(第 1-100 题)

原地址：http://blog.csdn.net/v_JULY_v/article/details/6057286

1.把二元查找树转变成排序的双向链表（树）

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

10

/ /

首先我们定义的二元查找树 节点的数据结构如下：

struct BSTreeNode

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

2.设计包含 min 函数的栈（栈）

定义栈的数据结构，要求添加一个 min 函数，能够得到栈的最小元素。

数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

求所有子数组的和的最大值。要求时间复杂度为 O(n)。

例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，

因此输出为该子数组的和 18。

4.在二元树中找出和为某一值的所有路径（树）

题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

/ /

5 12

4 7

则打印出两条路径：10, 12 和 10, 5, 7。

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree

{

题目：输入 n 个整数，输出其中最小的 k 个。

例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 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,0

以此类推..

第 7 题（链表）

微软亚院之编程判断俩个链表是否相交

给出俩个单向链表的头指针，比如 h1，h2，判断这俩个链表是否相交。

1.如果链表可能有环列?

2.如果需要求出俩个链表相交的第一个节点列?

这两个房间是 分割开的，从一间里不能看到另一间的情况。

现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控

制的。

有什么办法呢？

2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，

每天给出一块。

如果你只能将金条切割两次，你怎样分给这些工人?

3. ★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

★用一种算法整理一个数组。你为什么选择这种方法?

★用一种算法使通用字符串相匹配。

你知道所有的整数都在 1 到 1000(包括 1000)之间。此外，除一个数字出现 两次

外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法

找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不

用这种方式的算法吗?

★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。

第 9 题（树）

判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。

8

/ /

6 10

/ / / /

5 7 9 11

第 10 题（字符串）

第 11 题（树）

求二叉树中节点的最大距离...

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，

我们姑且定义"距离"为两节点之间边的个数。

写一个程序，

求一棵二叉树中相距最远的两个节点之间的距离。

第 12 题（语法）

题目：求 1+2+„+n，

要求不能使用乘除法、for、while、if、else、switch、case 等关键字以及条

{

int m_nKey;

ListNode* m_pNext;

};

第 14 题（数组）：

题目：输入一个已经按升序排序过的数组和一个数字，

在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对

即可。

第 15 题（树）：

题目：输入一颗二元查找树，将该树转换为它的镜像，

即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

用递归和循环两种方法完成树的镜像转换。

例如输入：

6 10

// //

10 6

// //

11 9 7 5

定义二元查找树的结点为：

struct BSTreeNode // a node in the binary search tree (BST)

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

第 16 题（树）：

/ / / /

5 7 9 11

输出 8 6 10 5 7 9 11。

第 17 题（字符串）：

题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输

出 b。

分析：这道题是 2006 年 google 的一道笔试题。

每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字

的下一个数字）。

当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。

求出在这个圆圈中剩下的最后一个数字。

/ 0 n=0

f(n)= 1 n=1