微软面试汇总.docx

编号：时间：2021年x月x日书山有路勤为径学海无涯苦作舟页码：微软面试1.把二元查找树转变成排序的双向链表题目：输入一棵二元查找树将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点只调整指针的指向。10/\614/\/\481216转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};2.设计包含min函数的栈。定义栈的数据结构要求添加一个min函数能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。3.求子数组的最大和题目：输入一个整形数组数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1-2310-472-5和最大的子数组为310-472因此输出为该子数组的和18。4.在二元树中找出和为某一值的所有路径题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如输入整数22和如下二元树10/\512/\47则打印出两条路径：1012和1057。二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};5.查找最小的k个元素题目：输入n个整数输出其中最小的k个。例如输入1234567和8这8个数字则最小的4个数字为123和4。第6题腾讯面试题：给你10分钟时间根据上排给出十个数在其下排填出对应的十个数要求下排每个数都是先前上排那十个数在下排出现的次数。上排的十个数如下：【0123456789】举一个例子数值:0123456789分配:62100010000在下排出现了6次1在下排出现了2次2在下排出现了1次3在下排出现了0次....以此类推..第7题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针比如h1h2判断这俩个链表是否相交。为了简化问题我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?第8题此贴选一些比较怪的题由于其中题目本身与算法关系不大仅考考思维。特此并作一题。1.有两个房间一间房里有三盏灯另一间房有控制着三盏灯的三个开关这两个房间是分割开的从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？2.你让一些人为你工作了七天你要用一根金条作为报酬。金条被分成七小块每天给出一块。如果你只能将金条切割两次你怎样分给这些工人?3.★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。★用一种算法在一个循环的链接表里插入一个节点但不得穿越链接表。★用一种算法整理一个数组。你为什么选择这种方法?★用一种算法使通用字符串相匹配。★颠倒一个字符串。优化速度。优化空间。★颠倒一个句子中的词的顺序比如将“我叫克丽丝”转换为“克丽丝叫我”实现速度最快移动最少。★找到一个子字符串。优化速度。优化空间。★比较两个字符串用O(n)时间和恒量空间。★假设你有一个用1001个整数组成的数组这些整数是任意排列的但是你知道所有的整数都在1到1000(包括1000)之间。此外除一个数字出现两次外其他所有数字只出现一次。假设你只能对这个数组做一次处理用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式那么你能找到不用这种方式的算法吗?★不用乘法或加法增加8倍。现在用同样的方法增加7倍。第9题判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true否则返回false。例如输入5、7、6、9、11、10、8由于这一整数序列是