大厂面试系列(七)：数据结构与算法等

小灰灰 2022-12-20 03:05 247阅读 0赞

# 数据结构和算法 #

## 链表 ##

*  链表，常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分，这个一般必须得完全无误的情况下写出来；
 *  给出两个链表的头结点，找出这两个链表的交点。
 *  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\]、\[c,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\[c\]\]", 返回 "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

> 欢迎搜索关注本人与朋友共同开发的微信面经小程序【大厂面试助手】和公众号【微瞰技术】

![file][] ![file][file 1]

[file]: /images/20221120/02cc8f4c36d1415d99c0818dacea38ab.png
[file 1]: https://img-blog.csdnimg.cn/20201110112947851.png