关于java:大厂面试系列七数据结构与算法等

数据结构和算法

链表

• 链表，常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的局部，这个个别必须得齐全无误的状况下写进去；
• 给出两个链表的头结点，找出这两个链表的交点。
• java 中数组和链表的区别，各自劣势 如何设计领有高效的随机读取能力的的链表（跳表）设计跳表，跳表插入开销，跳表随机读取过程
• 给你一个单向链表，给这个链表做 K 反转，例如 k=3 1 -> 2 -> 3 -> 4 -> 5 -> 6 反转后为：3 -> 2 -> 1 -> 6 -> 5 -> 4 链表长度保障为 K 的倍数
• 给定一个链表，返回链表开始入环的第一个节点
• n 个降序的链表返回前 K 个大的节点形成的链表
• 链表合并：给出 n 个有序的链表，将他们合并为一个有序链表。
• 有 k 个有序单链表，怎么合并成一个有序单链表？
• 链表逆序，不能用批改指针的办法，用递归如何实现。
• 反转单链表
• 晓得双向链表怎么翻转吗
• 有两个数字十分大曾经超出了 long 型的范畴，当初以链表的形式存储其中链表头示意最高位，例如 1 ->2->3->4 示意 1234，请设计一个算法求出两数之和；
• 反转数字，不能把数字变成字符串
• 链表找环的入口
• 单链表的逆序
• 两个链表合并，最长公共子串问题
• 单链表逆序，快排，数组中找两个数和等于目标值

数组

• 在 M 个大小的数组中找到第 K 大的数（最大堆）
• 我当初有一个数组[1,2,3,4]，请实现算法，失去这个数组的全排列的数组，如[2,1,3,4]，•[2,1,4,3]。。。。你这个算法的工夫复杂度是多少
• 数组 A，2* n 个元素，n 个奇数、n 个偶数，设计一个算法，使得数组奇数下标地位搁置的都是奇数，偶数下标地位搁置的都是偶数 •先说下你的思路 •下一个奇数？怎么找？•有思路么？•你这样工夫复杂度有点高，如果要求 O(N)要怎么做
• 手写算法，两个有序数组的合并。
• 十万行二维数组，每行长度为 10，每个数组降序，找出最大的 15 个数。先跟面试官说了思路，而后又在白纸上写了进去
• 对一个数组进行绝对值排序的算法；
• 非降序数组，打印某个值最初呈现的地位
• 找出数组中超过半数的那个数字（摩尔投票）
• 一个数组反转，o(logn)复杂度用什么排序算法；
• 一个 100 长度数组, 外面是 固定的随机数, 要求列出反复的数字的最优算法.；
• 给定两个数组，每个数组中都有反复的数字。不必类库函数，对这两个数组排序。
• 给定一个数组，求该数组所有的自子数组 去掉一个字符串中的所有空格
• 给定一个数组，元素的大小 0~25，有反复元素。按呈现频次的高下输入所有的数字
• 给定一个乱序数组，求数组内最大间断的数；
• 无序数组找第 k 大的数
• 给一个数组，和 k，求数组中的哪两个数之和为 k，除了双层 for 循环和字典的形式还能用什么形式实现；

查找

• 写二分查找算法
• 有主字符串 A，子字符串 B，在 A 中查找 B
• 手撕一个有序数组的二分查找算法
• 请说出二分查找的实现思路及时空复杂度。
• 用二分法查找一个长度为 18 的，排好的线性表，当查找不胜利时，最多须要比拟多少次

排序

• 快排怎么实现的，疾速排序（包含算法步骤、均匀算法复杂度、最好和最坏的情景）
• 5 亿整数的大文件，怎么排？
• 两个 1G 排好序的文件，按序合并
• 手写归并排序。两个有序数组合并。
• 常见的排序算法有哪些？各种排序算法的均匀工夫复杂度和最坏状况下的工夫复杂度？
• 写出你相熟的排序算法，并阐明其优缺点
• 给了长度为 N 的有反复元素的数组，要求输入第 10 大的数。
• 手写一下疾速排序吧，我看你加入过 ACM，所以用非递归实现一下。
• 快排听过吗？他是怎么实现的？
• 如果是单链表的疾速排序，你怎么做？
• 快排工夫空间复杂度，最好最坏的状况，优化计划？
• 手写了冒泡排序
• 手写递归排序等
• 两个排序好的数组，构思算法把一个按序插入另一个数组
• 手工实现一个疾速排序算法
• 列举数据的几个排序算法
• 疾速排序？疾速排序是稳固的么？如何实现一个疾速排序的稳定性？
• 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法工夫复杂度必须是 O(n)。
• 快排会吗？晓得原理吗？
• 排序算法，介绍一下疾速排序，疾速排序工夫复杂度，是不是稳固排序，介绍几种你所晓得的稳固排序算法
• 10 亿个数选最大的 K 个，用什么办法，复杂度多少
• 说一下冒泡排序的原理
• 请对 3 个有序数组进行归并排序

树

• AVL 树和 B 树的概念、细节，比方会问 mysql 数据库的索引的实现原理，基本上就等于问你 B 树了。
• 红黑树，这个基本上必问的一个数据结构，包含红黑树的概念、均匀算法复杂度、最好最坏状况下的算法复杂度、左右旋转、色彩变换。
• 找出二叉树中任意两个节点的最低公共根节点, 如果树是 BST 呢. 深度优先搜寻 + 二分查找树性质
• B+ 树如何决裂？
• 二叉树前中后遍历 二叉树档次遍历 二叉树深度优先遍历(递归、非递归) 二叉树广度优先遍历(递归、非递归) 和为 n 的二叉树门路 二叉树深度 二叉树是否对称 链表反转
• 红黑树有啥个性?
• 二叉树层序遍历输入，每一层输入数组（手写算法）。
• JDK1.8 采纳的红黑树个性，以及采纳红黑树的理由而不采纳 AVL 和 B 树的起因？
• 一个二叉搜寻树，找出某两个节点的公共先人。
• 给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。例如，输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输入: 6 解释: 节点 2 和节点 8 的最近公共先人是 6。示例 2: 输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输入: 2 解释: 节点 2 和节点 4 的最近公共先人是 2, 因为依据定义最近公共先人节点能够为节点自身。
• 均衡二叉树的基本概念 简略介绍一下 b + 树
• 多叉树的生成 给定一个数组【[a,b]、、[e,a]、[h,a]、[k,h]】，数组前一个代表子节点、后一个代表父节点，生成一颗多叉树，返回根节点
• 依照 Z 字形分层遍历二叉树，要求 bug free，并且结构二叉树进行测试
• 二叉树的右视图。
• 写一个二叉树的深度遍历
• 二叉树翻转
• 二叉树的 s 型遍历，层序遍历的变种，简略，不过要写测试用例，等于还要写一个数组转二叉树的函数
• 一颗非均衡二叉树，如何最快的形式找到间隔最远的两个叶子节点。
• 给一个二叉树和一个目标值，找到和等于这个值的所有门路
• B 和 B + 树，B+ 树的搜寻次数、为什么不必二叉树。
• 红黑树最差旋转几次
• 给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共先人是两个节点的公共的先人节点且具备最大深度。假如给出的两个节点都在树中存在。
• 档次遍历二叉树，返回一个二维数组，每行示意一层
• 不必迭代办法计算树的高度；
• 假如一棵二叉树的后序遍历序列为 DFGGEBHICA, 中序遍历序列为：DBFEGAHCI, 则前序遍历序列为？
• 多叉树的第 n 层 档次遍历 2. 递归太深会怎么？答栈溢出。为什么会栈溢出？python 函数中的长期变量存在哪？那很深的时候，用循环会怎么呢？为什么不会栈溢出？
• 给定一个二叉树，顺次打印出每一行
• 前序遍历 中序遍历 后序遍历 晓得那些能够复原二叉树，只晓得前序和后序能够吗？
• 有 N 个节点的满二叉树的高度

其余

• 哈希表，对哈希表的细节要求很高，比方哈希表的冲突检测、哈希函数罕用实现、算法复杂度；比方百度二面就让我写一个哈希表插入元素算法，元素类型是任意类型。
• 找出两个有序数组中的反复项，剖析工夫和空间复杂度，而后就是一直优化优化优化。。要是数组长度十分大会呈现什么状况？
• 俩线程别离继续打印奇数和偶数，实现俩线程的交替打印（从小到大）
• 给定一个通过编码的字符串，返回它解码后的字符串。编码规定为: k[encoded_string]，示意其中方括号外部的 encoded_string 正好反复 k 次。留神 k 保障为正整数。你能够认为输出字符串总是无效的；输出字符串中没有额定的空格，且输出的方括号总是合乎格局要求的。此外，你能够认为原始数据不蕴含数字，所有的数字只示意反复的次数 k，例如不会呈现像 3a 或 2[4] 的输出。示例: s = “3[a]2[bc]”, 返回 “aaabcbc”. s = “3[a2]“, 返回 “accaccacc”. s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.
• leetcode213 你是一个业余的小偷，打算偷窃沿街的屋宇，每间房内都藏有肯定的现金。这个中央所有的屋宇都围成一圈，这意味着第一个屋宇和最初一个屋宇是紧挨着的。同时，相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。给定一个代表每个屋宇寄存金额的非负整数数组，计算你在不触动警报安装的状况下，可能偷窃到的最高金额。示例 1: 输出: [2,3,2] 输入: 3 解释: 你不能先偷窃 1 号屋宇（金额 = 2），而后偷窃 3 号屋宇（金额 = 2）, 因为他们是相邻的。示例 2: 输出: [1,2,3,1] 输入: 4 解释: 你能够先偷窃 1 号屋宇（金额 = 1），而后偷窃 3 号屋宇（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4。
• 有 15 个瓶子，其中最多有一瓶有毒，当初有四只老鼠，喝了有毒的水之后，第二天就会死。如何在第二天就能够判断出哪个瓶子有毒
• 看你简历提到了 raft 算法，讲下 raft 算法的根本流程？raft 算法外面如果呈现脑裂怎么解决？有没有理解过 paxos 和 zookeeper 的 zab 算法，他们之前有啥区别？
• 依据身高重建队列 假如有打乱程序的一群人站成一个队列。每个人由一个整数对 (h, k) 示意，其中 h 是这个人的身高，k 是排在这个人后面且身高大于或等于 h 的人数。编写一个算法来重建这个队列。留神：总人数少于 1100 人。示例 输出: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]] 输入: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
• 一个二维数组，每一列的数字从左往右增大，每一行从上往下增大，求一个指定的数字在这个数组中的地位
• 给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”例如，输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输入: 6 解释: 节点 2 和节点 8 的最近公共先人是 6。示例 2: 输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输入: 2 解释: 节点 2 和节点 4 的最近公共先人是 2, 因为依据定义最近公共先人节点能够为节点自身。
• 股票买卖的一道题 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你能够尽可能地实现更多的交易（屡次交易一支股票）: 你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。卖出股票后，你无奈在第二天买入股票 (即冷冻期为 1 天)。示例: 输出: [1,2,3,0,2] 输入: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
• 给你一个 n * m 的二维整数数组，数字都是大于等于 0，当初要你对数组做一种操作，对于所有 0，将 0 所在的行和列全副变为 0。要求应用尽量少的空间和工夫。
• 给你一个整数数组，数组中的元素定义一种间隔 d[i] 为将数组排序后，该元素挪动的间隔，当初给你一个 K 数组，即数组中所有元素的间隔 d <= k，对这个 K 数组排序，心愿尽量小的工夫复杂度。
• 输出一个不含雷同整数的整数汇合，输入所有子集 输出：[1,2,3] 输入：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 有三十瓶水，十个桶，每个桶能放 0 -10 瓶水，有多少种计划
• 给定一个字符串和一个整数 k，你须要对从字符串结尾算起的每个 2k 个字符的前 k 个字符进行反转。如果残余少于 k 个字符，则将残余的所有全副反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将残余的字符放弃原样。示例: 输出: s = “abcdefg”, k = 2 输入: “bacdfeg” 要求:（1）该字符串只蕴含小写的英文字母。（2）给定字符串的长度和 k 在 [1, 10000]范畴内。
• 翻转字符串，反转句子等。
• 判断一串字符串里括号的最大无效长度。用动静布局实现
• 给一个字符串，找出间断雷同的字符，如果有两个以上雷同的，取 ASCII 码小的。
• 给一个字符串，删除最大间断雷同的字符串并返回
• 有一组未排序的整形数组，你设计一个算法，对数组的元素两两配对，而后输入最大的绝对值差和最小的绝对值差的 ” 对数 ”
• m* n 二维数组整体有序，查找 value
• 返回一个数字数组的排序值，比方数据 [6,2,5,0] 的返回是[4,2,3,1]；
• 一个负数数组，长度为 N，且数组元素 <N，统计每个负数呈现的次数，要求工夫复杂度 O(n)，空间复杂度 O(1)；
• 实现一个 fibonacci 函数，输出数字 n，输入 fibonacci 数列的第 n 项数字，并给该函数退出缓存性能。
• 100G 文本找某个单词呈现的频率
• 是否连贯红黑树 •
• 是否理解数据结构的“堆”
• 斐波拉契数列非递归实现
• 算法 n 的阶乘开端 0 的个数
• 我一个文件, 有 45 亿个阿拉伯数字, 如何进行去重啊? 如何找出最大的那个数啊?
• 写一个 fibnaccio 的相干例子
• 输出两个字符串 str1 str2 和整数 n，要求两个数以 n 进制相加，而后输入字符串 str3
• 就是二位数组如何进行螺旋输入 而后第二道的算法题是如何从 25 匹马中通过赛马的模式找到最快的 3 匹，每次最多只能 5 匹马参赛，问起码须要赛几次？答案是 7 次，我思路对了，不过我把次数给弄错了，多了 2 次没必要的较量。
• 6 个元素 1.2.3.4.5.6 的程序进栈，请问下列哪个不是非法的出栈序列？a:345261 b:436521 c:245316 d:124653 e:543612
• 图的最短门路问题
• 算法题（爬楼梯，问一个人爬楼梯，每次只能爬一个台阶或两个台阶，问有 N 个台阶，总共能有多少种爬法）；
• 实现一个 random(m,n)办法，返回 m 到 n 的随机数
• 64 只球队找到最强的，找前二强的，前 k 强的
• 就是 m * n 的矩形从左下面到右上面的门路有多少条
• 求 N 内的所有素数
• 判断字符串是否是一个数字
• 当一个文本文件中有 200 万行数据，如何在在每一行的尾部追加一个字符；
• 求一个字符串中最长不反复子串的长度
• 三个有符号的整型（long）数 a, b, c，怎么判断 a +b > c? 实现并且设计测试用例（在 main 函数中调用，打印后果）（思考同号越界问题）
• 给一个字符串和一个 k，要求找到不超过 k 个不同字符的最长子串的长度
• 10 进制转 16 进制（缓和了，有点费时间，啧啧啧）
• f(0)=0;f(1)=1; f(n)=f(n-1)+f(n-2) 求 f（n）
• 有主字符串 A，子字符串 B，在 A 中查找 B

欢送搜寻关注自己与敌人共同开发的微信面经小程序【大厂面试助手】和公众号【微瞰技术】