《各大公司实习生面试题总汇》由会员分享，可在线阅读，更多相关《各大公司实习生面试题总汇（34页珍藏版）》请在金锄头文库上搜索。
1、分享陈毅陈毅的分享当前分享返回分享首页分享各大公司（Google，Microsoft，Baidu， Microsoft Research Asia etc.）实习生面试题总汇 来源： 陆超超的日志1.把二元查找树转变成排序的双向链表（树）题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。10/ 6 14/ / 4 8 12 16转换成双向链表4=6=8=10=12=14=16。首先我们定义的二元查找树 节点的数据结构如下：struct BSTreeNodeint m_nValue; / value of nodeBSTreeNode
2、*m_pLeft; / left child of nodeBSTreeNode *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、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 treeint m_nValue; / value of nodeBinaryTreeNode *m_pLeft; / left chil
4、d 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,00在下
5、排出现了6 次，1在下排出现了2次，2在下排出现了1 次，3在下排出现了0次.以此类推.第7题（链表）微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如 h1，h2 ，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列? 第8题（算法）此贴选一些比较怪的题， ，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，这两个房间是 分割开的，从一间里不能看到另一间的情况。现在要求受训者分别进这两房间一次，然后判断出这三盏灯分
6、别是由哪个开关控制的。有什么办法呢？2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。如果你只能将金条切割两次，你怎样分给这些工人?3.用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。用一种算法整理一个数组。你为什么选择这种方法?用一种算法使通用字符串相匹配。颠倒一个字符串。优化速度。优化空间。颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，实现速度最快，移动最少。找到一个子字符串。优化速度。优化空间。比较两个字符串，用 O(n)时间和恒量空间。假设你有一个用
7、1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到 1000(包括1000)之间。此外，除一个数字出现两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不用这种方式的算法吗?不用乘法或加法增加8倍。现在用同样的方法增加7倍。第9题（树）判断整数序列是不是二元查找树的后序遍历结果题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。例如输入5、7 、 6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：8/
8、6 10/ / 5 7 9 11因此返回 true。如果输入7、4 、 6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。第10题（字符串）翻转句子中单词的顺序。题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“ student. a am I”。第11题（树）求二叉树中节点的最大距离.如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义距离 为两节点之间边的个数。写一个程序，求一棵二叉树中相距最远的两个节点之间的距离。第
9、12题（语法）题目：求1+2+ +n，要求不能使用乘除法、for、while、if、else 、switch、case 等关键字以及条件判断语句（A?B:C） 。第13题（链表）：题目：输入一个单向链表，输出该链表中倒数第 k 个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下： struct ListNodeint m_nKey;ListNode* m_pNext;第14题（数组）：题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2
10、、4、7、11、15和数字15。由于4+11=15，因此输出4和11 。第15题（树）：题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入：8/ 6 10/ /5 7 9 11输出：8/ 10 6/ /11 9 7 5定义二元查找树的结点为：struct BSTreeNode / a node in the binary search tree (BST)int m_nValue; / value of nodeBSTreeNode *m_pLeft; / left child of nod
11、eBSTreeNode *m_pRight; / right child of node;第16题（树）：题目（微软）：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。 例如输入8/ 6 10/ / 5 7 9 11输出8 6 10 5 7 9 11。 第17题（字符串）：题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b。 分析：这道题是2006年 google 的一道笔试题。第18题（数组）：题目：n 个数字（ 0,1,n-1）形成一个圆圈，从数字0 开始，每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当
12、前数字的下一个数字） 。当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。July：我想，这个题目，不少人已经 见识过了。第19题（数组、递归）：题目：定义 Fibonacci 数列如下： / 0 n=0f(n)= 1 n=1 f(n-1)+f(n-2) n=2输入 n，用最快的方法求该数列的第 n 项。分析：在很多 C 语言教科书中讲到递归函数的时候，都会用 Fibonacci 作为例子。因此很多程序员对这道题的递归解法非常熟悉，但.呵呵，你知道的。 。第20题（字符串）：题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符
13、串345，则输出整数345。第21题（数组）2010年中兴面试题编程求解：输入两个整数 n 和 m，从数列1，2，3.n 中 随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来.第22题（推理）：有4张红色的牌和4 张蓝色的牌，主持人先拿任意两张，再分别在 A、B、C 三人额头上贴任意两张牌，A、B、C 三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，A 说不知道， B 说不知道，C 说不知道，然后 A 说知道了。请教如何推理，A 是怎么知道的。如果用程序，又怎么实现呢？第23题（算法）：用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。 3D 坐
14、标系 原点(0.0,0.0,0.0)圆形:半径 r = 3.0圆心 o = (*.*, 0.0, *.*)正方形:4个角坐标; 1:(*.*, 0.0, *.*)2:(*.*, 0.0, *.*)3:(*.*, 0.0, *.*)4:(*.*, 0.0, *.*)第24题（链表）：链表操作，单链表就地逆置，第25题（字符串）：写一个函数,它的原形是 int continumax(char *outputstr,char *intputstr)功能：在字符串中找出连续最长的数字串，并把这个串的长度返回，并把这个最长数字串付给其中一个函数参数 outputstr 所指内存。例如：abcd12345
15、ed125ss123456789的首地址传给 intputstr 后，函数将返回9，outputstr 所指的值为12345678926.左旋转字符串（字符串）题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串 abcdef 左旋转2位得到字符串 cdefab。请实现字符串左旋转的函数。要求时间对长度为 n 的字符串操作的复杂度为 O(n)，辅助内存为 O(1)。27.跳台阶问题（递归）题目：一个台阶总共有 n 级，如果一次可以跳 1级，也可以跳2级。求总共有多少总跳法，并分析算法的时间复杂度。这道题最近经常出现，包括 MicroStrategy 等比较重视算
16、法的公司都曾先后选用过个这道题作为面试题或者笔试题。28.整数的二进制表示中1的个数（运算）题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制表示为1010，有两个1，因此输出2。分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。29.栈的 push、pop 序列（栈）题目：输入两个整数序列。其中一个序列表示栈的 push 顺序，判断另一个序列有没有可能是对应的 pop 顺序。为了简单起见，我们假设 push 序列的任意两个整数都是不相等的。 比如输入的 push 序列是1、2、3、4 、5，那么4、5 、3、2、1就有可能是一个 pop 系列。因为可以有如下的 push 和 pop 序列：push 1， push 2，push
