又到了每年的金三银四招聘旺季，有幸获得了微软的笔试机会，程序猿们应该都知道，老美的公司都喜欢怼数据结构与算法，微软肯定也不例外，个人觉得考数据结构对每一个应聘者都公平，我这次投的是微软苏研院，笔试考察的不难，是最最常见的数据结构算法裸题，这里记录一下，也给出解法。

1 快速排序

快排应该是最网红的题了，从校招到社招，从后端到前端再到移动端，都会问，但是估计能手撕出来的不超过一半，能讲清楚思路的估计不超过一半的一半，其实用两个词概括，就是双指针+递归分治，在每一轮递归的时候找到每个基准数排完序后的位置，将小于这个基准数的所有数放到它的左边，将大于这个基准数的所有数放到它的右边，然后再分别递归它左边的数组与它右边的数组。比如说数组[2,3,1,5,6,4]:

初始状态是这样，我现在给两个指针出来，一个指针指向头，即arr[0] = 2, 一个指针指向尾，及arr[5] = 4，规定一个基准数，这里直接用第一个数(arr[0] = 2)即可。开始第一次的递归处理，尾指针先从右往左扫，扫到第一个小于（注意是小于，而不是小于等于哦）基准数的位置停住，这时候头指针再从左往右扫，扫到第一个大于基准数的位置停住，这时候是下面的图示状态：

交换两个指针所指的数，成为了下面的状态：

两个数交换完毕，右指针此时指的是arr[2] = 3, 左指针指着arr[1] = 1；交换完毕后右指针继续从当前位置往左扫，扫到1的时候发现和左指针相遇了，那么这个时候就结束左右指针的扫描，左右指针同时指着arr[1] = 1，即：

此时退出循环扫描的过程，交换基准数与左右指针同时所指的数的位置，开头说了，基准数我选择的是arr[0] = 2, 指针指的是arr[1] = 1; 交换过后就变成了：

这时候就发现基准数已经出现在了它排完序后应该在的位置（排完序后是[1,2,3,4,5,6]，2出现在了第2位）,比这个基准数小的数组出现在了它的左边（[1]出现在了2的左边），比基准数大的出现在了它的右边（[3,5,6,4]出现在了2的右边）。之后的过程就是对左右数组的分别递归处理。附上代码：

思考：为什么是右指针先扫而不是左指针先扫呢，大家自己想想吧哈哈，模拟一下就知道了。

发散性思考

上文中我提到了左数组，右数组，还提到了基准数的概念，其中，左数组中的所有值都小于基准数，右数组中的所有值都大于基准数，而且快排还是个递归的过程。我这里如果做一下类比，如果我把基准数看成是树根，把左数组看成是根的左孩子，右数组看成是根的右孩子，相信学过数据结构的童鞋都知道了，那不就是一颗BST吗。哈哈确实如此，其实你会发现BST的中序遍历出来就是一个有序数组，所以上文中快排的过程就是一个创建二叉搜索树的过程。

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树.

所以要是问你怎么创建一颗BST，想必也能信手拈来了吧，废话不说上代码：

二叉树的非递归中序遍历

我相信很多人都能写出二叉树的递归遍历：递归遍历左子树，输出根节点，递归遍历右子树，三行代码，完事，但是要问到非递归遍历，估计大多数人就傻眼了，但是人家就要考你不会的啊，非递归遍历其实就是借助栈来完成：

“我自己是一名从事了6年web前端开发的老程序员（我的微信：webxxq），今年年初我花了一个月整理了一份最适合2019年自学的web前端全套培训教程（视频+源码+笔记+项目实战），从最基础的HTML+CSS+JS到移动端HTML5以及各种框架和新技术都有整理，打包给每一位前端小伙伴，这里是前端学习者聚集地，欢迎初学和进阶中的小伙伴（所有前端教程关注我的微信公众号：web前端学习圈，关注后回复“2019”即可领取）。

老美的公司，算法关必须过啊。所以，路漫漫其修远兮，刷题刷题多刷题吧