数据结构和算法.md

数据结构和算法

链表

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