精选80题：各种企业面试题.docVIP

[整理III]微软等公司数据结构+算法面试第1-80题汇总 ?????????????---首次一次性汇总公布 ? 由于这些题，实在太火了。所以，应广大网友建议要求，在此把之前已整理公布的前80题， 现在，一次性分享出来。此也算是前80题第一次集体亮相。 此些题，已有上万人，看到或见识到，若私自据为己有，必定为有知之人识破，付出代价。 所以，作者声明： 本人July对以上所有任何内容和资料享有版权，转载请注明作者本人July出处。向你的厚道致敬。谢谢。2010年11月27日。 ---------------------------------------------------------------------------------------------------------------- ? 1.把二元查找树转变成排序的双向链表?题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。?? 10? / \? 6? 14?/ \ / \4? 8 12 16?转换成双向链表4=6=8=10=12=14=16。??首先我们定义的二元查找树 节点的数据结构如下：?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函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。 ? ?3.求子数组的最大和题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。 ? 4.在二元树中找出和为某一值的所有路径 题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。打印出和与输入整数相等的所有路径。例如 输入整数22和如下二元树? 10??? / \????5? 12????/?? \???4???? 7则打印出两条路径：10, 12和10, 5, 7。 二元树节点的数据结构定义为：struct BinaryTreeNode // a node in the binary tree{int 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个数字为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?0在下排出现了6次，1在下排出现了2次，?2在下排出现了1次，3在下排出现了0次....?以此类推.. 第7题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。 问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列? ?第8题此贴选一些 比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关， 这两个房间是 分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。有什么办法呢？ 2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人? 3.　用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。　　用一种算