原创

Java 真实大厂面试题 100 道汇总,含答案

第 1 题:把二元查找树转变成排序的双向链表(树)


第 2 题:设计包含 min 函数的栈(栈)


第 3 题:求子数组的最大和(数组)


第 4 题:在二元树中找出和为某一值的所有路径(树)


第 5 题:查找最 小的 k 个元素(数组)


第 6 题(腾讯面试题):
根据上排给出十个数,在其下排填出对应的十个数,要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下:【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:★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
★用一种算法在一个循环的链接表里插入一个节点,但不得穿越链接表。
★用一种算法整理一个数组。你为什么选择这种方法 。
★用一种算法使通用字符串 相匹配。
★颠倒一个字符串。优化速度。优化空间。
★颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”,实现速度最快,移动最少。
★找到一个子字符串。优化速度。优化空间。
★比较两个字符串,用 O(n) 时间和恒量空间。
★假设你有一个用 1001 个整数组成的数组,这些整数是任意排列的,但是你知道所有的整数都在 1 到 1000( 包括 1000) 之间。此外,除一个数字出现两次外,其他所有数字只出现一次。假设你只能对这个数组做一次处理,用一种算法找出重复的那个数字。如果你在运算中使用了 辅助的存储方式,那么你能找到不用这种方式的算法吗?
★不用乘法或加法增加 8 倍。现在用同样的方法增加 7 倍。


第 9 题(树):
判断整数序列是不是二元查找树的后序遍历结果
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true ,否则返回 false 。


第 10 题(字符串):
翻转句子中单词的顺序。 题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。
例如输入“I am a student. student.”,则输出 student. a am I ”。


第 11 题(树):
求二叉树中节点的最大距离
如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,我们姑且定义距离为两节点之间边的个数。
写一个程序,求一棵二叉树中相距最远的两个节点之间的距离。


第 12 题(语法):
题目:求 1 + 2 + 2 + …… + n 要求不能使用乘除法、for 、 while 、 if 、 else 、 switch 、 case 等关键字以及条件判断语句( A?B:C )。


第 13 题(链表):
题目:输入一个单向链表,输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表的尾指针。


第 14 题(数组):
题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是 O(n) 。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组 1 、 2 、 4 、 7 、 11 、 15 和数字 15 。由于 4+11=15 ,因此输出 4 和 11 。


第 15 题(树):
题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。


第 16 题(微软):
输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。


第 17 题(Google):
题目:在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff ,则输出 b 。


第 18 题(数组):
题目:n 个数字( 0,1,0,1,……,n 1 )形成一个圆圈,从数字 0 开始,每次从这个圆圈中删除第 m 个数字( 第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。


第 19 题(数组、递归):
题目:定义 Fibonacci 数列如下:
/ 0 n = 0
f(n)= 1 n = 1
/ f(n 1) + f(n 2) n = 2
输入 n ,用最快的方法求该数列的第 n 项。


第 20 题(中兴):
编程求解: 输入两个整数 n 和 m ,从数列 1 2 3.......n 中 随意取几个数使其和等于 m , 要求将其中所有的可能组合列出来。

......

剩余的 80 道面试题,及所有的答案,请关注我的公众号 TomScript 并回复 100,即可免费领取。

该篇文章的评论功能已被站长关闭