微软的100道算法面试题（一）

  程序员为什么要学数据结构？

    在计算机发展的初期，人们使用计算机的主要目的是处理数值计算问题。使用计算机解决具体问题一般需要经过以下几个步骤：首先从具体问题抽象出适当的数学模型，然后设计或选择解此数学模型的算法，接着编写程序并进行调试、测试，直至得到最终的解答。

    由于最初涉及的运算对象是简单的整型、实型或布尔型数据，所以程序设计者的主要精力集中于程序设计的技巧上，而无需重视数据结构。随着计算机应用领域的扩大和软硬件的发展，非数值计算问题显得越来越重要，据统计，当今处理非数值计算问题占用了90%以上的机器时间。这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法，而是要设计出合适的数据结构。

    著名的瑞士计算机科学家沃思（N.Wirth）教授曾提出：算法 + 数据结构＝程序

    程序设计的实质是对实际问题设计/选择好的数据结构和好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。

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

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

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

2、设计包含min 函数的栈

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

要求函数min、push 以及pop 的时间复杂度都是O(1)。

3、求子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。

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

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

题目：输入一个整数和一棵二元树，从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

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

5、查找最小的k 个元素

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

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

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

为了简化问题，我们假设俩个链表均不带环。

问题扩展：

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

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

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

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

如果是返回true，否则返回false。

8、输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。

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

9、输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

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

10、输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

11、n 个数字（0,1,…,n-1）形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数

字）。

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

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

12、定义Fibonacci 数列如下：

/ 0 n=0

f(n)= 1 n=1

\ f(n-1)+f(n-2) n=2

输入n，用最快的方法求该数列的第n 项。

分析：在很多C 语言教科书中讲到递归函数的时候，都会用Fibonacci 作为例子。

13、输入一个表示整数的字符串，把该字符串转换成整数并输出。

例如输入字符串"345"，则输出整数345。

14、链表操作

（1）.单链表就地逆置，

（2）合并链表

15、写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)功能：

在字符串中找出连续最长的数字串，并把这个串的长度返回，

并把这个最长数字串付给其中一个函数参数outputstr 所指内存。

例如："abcd12345ed125ss123456789"的首地址传给intputstr 后，函数将返回9，

outputstr 所指的值为123456789

16、跳台阶问题

题目：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。

求总共有多少总跳法，并分析算法的时间复杂度。

17、整数的二进制表示中1 的个数

题目：输入一个整数，求该整数的二进制表达中有多少个1。

例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

分析：这是一道很基本的考查位运算的面试题

18、栈的push、pop 序列

题目：输入两个整数序列。其中一个序列表示栈的push 顺序，判断另一个序列有没有可能是对应的pop 顺序。

为了简单起见，我们假设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 序列。

19、在从1 到n 的正数中1 出现的次数

输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。

例如输入12，从1 到12 这些整数中包含1 的数字有1，10，11 和12，1 一共出现了5 次。

分析：这是一道广为流传的google 面试题。

.

20、求一个矩阵中最大的二维矩阵(元素和最大).如:

1 2 0 3 4

2 3 4 5 1

1 1 5 3 0

中最大的是:

4 5

5 3

要求:(1)写出算法;(2)分析时间复杂度;(3)用C 写出关键代码

21、谷歌笔试

n 支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，

存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j 的队伍中更强的一支。

所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，

比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是4 对3， 5 对8。.......

胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，

下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4 对5,直至出现第一名

编程实现，给出二维数组w，一维数组order 和用于输出比赛名次的数组result[n]，

求出result。

22、有n 个长为m+1 的字符串，如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接，问这n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

23、网易有道笔试

(1)求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。

(2)求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。

24、百度研发笔试题

（1）设计一个栈结构，满足一下条件：min，push，pop 操作的时间复杂度为O(1)。

（2）一串首尾相连的珠子(m 个)，有N 种颜色(N<=10)，设计一个算法，取出其中一段，要求包含所有N 中颜色，并使长度最短，并分析时间复杂度与空间复杂度。

（3）)设计一个系统处理词语搭配问题，比如说中国和人民可以搭配，则中国人民人民中国都有效。要求：

*系统每秒的查询数量可能上千次；

*词语的数量级为10W；

*每个词至多可以与1W 个词搭配

当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

25、递归和非递归俩种方法实现二叉树的前序遍历。

26、腾讯面试题

1、设计一个魔方（六面）的程序。

2、有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

请用5 分钟时间，找出重复出现最多的前10 条。

3、收藏了1 万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

27、雅虎：

1、对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

2、一个整数数组，长度为n，将其分为m 份，使各份的和相等，求m 的最大值

比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;

{3,6}{2,4,3} m=2

{3,3}{2,4}{6} m=3 所以m 的最大值为3

28、微软

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

29、1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是这两个节点间边

的个数，比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。

2.求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，有向图不再连通，描述算法。

30、和为n 连续正数序列

题目：输入一个正数n，输出所有和为n 连续正数序列。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3 个连续序列1-5、4-6 和7-8。

数据结构与算法的重要性已不言而喻，最近，我整理出十大经典排序算法、五大常用算法总结，今天特意整理出微软面试的100题，由于篇幅过长，将分开分享，若有不足之处，欢迎指正！很多人都会想要答案，但是我认为没有标准答案，答案表现的是个人思维，欢迎大家在评论区讨论，进行思维的碰撞。

如何学习才能快速入门并精通呢？

当真正开始学习时难免不知从何入手，从而导致效率低下影响继续学习的信心。

但最重要的是不知道需要重点掌握哪些技术，学习时频繁踩坑，最终浪费大量时间。

为了让学习变得轻松高效， 现在给大家提供一个学习平台，让你在实践中积累经验掌握原理。主要方向是JAVA架构师，在这里你可以学习Java工程化、高性能及分布式、深入浅出、性能调优、Spring，MyBatis，Netty源码分析和大数据等知识点。可以加入Java后端技术群：819940388，群里有阿里大牛直播讲解技术，或是关注微信公众号：Java资讯库，回复“架构”，免费的大型互联网Java技术视频分享给大家。