本页面用于记录个人的刷题笔记（尤其是那些有启发，有趣的编程题）。部分附个人面试公司， 主要根据题型分类（跨题型随机分类2333）。
-
非递归实现求二叉树的深度（小红书）
- 引入队列，统计当前层次节点数目，逐层遍历
- 二叉树的深度（递归和非递归）---java实现
- 102. 二叉树的层次遍历
-
非递归从左至右打印一颗二叉树中的所有路径（拼多多/字节跳动）
-
判断平衡二叉树（腾讯）
-
寻找二叉搜索树中第一个大于k的节点（微软）
- 中序遍历求值
- 类似于 230. 二叉搜索树中第K小的元素
-
二叉树的完全性检验（Unity）
-
根据前&中序遍历结果重建二叉树（Unity）
- 首先找到根节点，再划分左右子树区域，逐层递归找到左右子节点
- 105. 从前序与中序遍历序列构造二叉树
-
实现一个二叉搜索树迭代器，包括
next()和hasNext()方法（PayPal） -
二叉树的右视图（Shopee）
-
给定一个二叉树根节点和指定路径，判断二叉树中是否存在给定指定路径，且要求指定路径最后一个元素为叶节点（微软）
-
将一颗二叉搜索树转化成一个排序的双向链表
- 不能创建新结点
- 二叉搜索树与双向链表
-
二叉树的最近公共祖先
- 首先判断当前节点是否为指定结点，是则返回
- 递归当前结点的左右子树
- 如果两边均不为null，表示找到，返回当前结点，均为null则返回null，否则返回对应子节点（left / right）
- 236. 二叉树的最近公共祖先
- Lowest Common Ancestor Binary Tree（各种情况详细举例，推荐）
-
二叉树的中序遍历的下一个结点
- 先判断右子结点不为空，返回右子节点最左边的节点
- 若父节点不为空，上溯到根节点的 “/”即返回
- 二叉树的下一个结点
-
红黑树描述及其复杂度分析（插入/查找）（腾讯/阿里）
- 查找、插入、删除时间复杂度 --> O(logN)
- 红黑树 Wiki
- 26 | 红黑树（下）：掌握这些技巧，你也可以实现一个红黑树 （红黑树分析）
-
二叉树的直径
-
二叉树的遍历
-
把一个数组排成最大的数（阿里）
- 剑指 Offer 45. 把数组排成最小的数
- 面试官说需要 通过 补位 思想（普通的compare再sort并不满意，但补位思想似乎不适用于有重复元素的情况）
-
如何给一个很大的无序数组去重（腾讯）
- 26. 删除排序数组中的重复项（给排序数组去重）
-
求两个排序数组的中位数（依图）
- 要求时间复杂度 O(log(m+n))
- 二分查找，递归求整个数组中第K大的元素，完整代码需要仔细考虑多种边界条件
- 4.寻找两个有序数组的中位数
-
求一个循环递增数组的最小值（腾讯）
- 153. 寻找旋转排序数组中的最小值 （无重复元素，二分，总有一半有序，注意边界）
- 154. 寻找旋转排序数组中的最小值 II （有重复元素，需要解除相等时的死循环）
-
数组中的逆序对（星环）
- 归并排序 && 递归的应用
- 引入辅助数组临时存放排序好的数据
- 归并时指向两个指针末尾，逐次向前并统计
- 面试题51. 数组中的逆序对
-
如何找到一个无序数组的中位数（Unity）
- 295. 数据流的中位数 （建立两个堆，最大堆&最小堆，复杂度分析）
- 找出一个无序数组的中位数 （快排，缩小Partition区域 / 取一半元素建堆）
-
链表排序
- 需要 nlog(n) 时间复杂度和常数级空间复杂度
- 归并排序的应用（Bottom Up）
- 找到中点，断开链表（通过快慢两个指针）
- 交替双指针合并
- 148. 排序链表
-
手写主流排序算法 & 各种算法的复杂度/稳定性分析（腾讯/字节跳动/阿里/蜻蜓FM/Unity）
- 常见问题
- 手写快排 / 堆排（Unity）
- 快排的复杂度分析（最好/最坏/平均）
- 堆排中建堆的时间复杂度分析 --> O(n)
- 归并排序的 Top-Down & Bottom-up 策略
- 不同排序的稳定性分析
- 冒泡排序的优化策略（华为）
- 设置flag位，一轮未交换数据即已完成排序，提前结束
- 记住本轮最后一次交换发生的位置lastExchange，下次内层循环到此终止即可
- 排序算法稳定性
- 排序算法可视化
- 快排 Wiki / 堆排 Wiki / 归并排序 Wiki
- 堆排序(Heapsort) （特别好的讲解）
- 冒泡排序算法及其两种优化
- 常见问题
-
（Top K 问题）给定一个无符号，包含10亿个数的数组，如何取出前100大的数（字节跳动/腾讯）
- 答题思路
- 首先询问资源 --> 内存 / 核数 / 单机or多机，如可用多机 --> MapReduce思想
- 堆排 O(nlogk)，可以单机处理海量数据（在内存受限情况下），如果k较小，趋近于 O(n)
- 建立一个容量为k的大/小顶堆
- n个元素逐一比较，O(logk) 完成删除和插入操作
- 全局排序， O(nlogn) （数据量较小时才可行）
- 冒泡（k个），O(kn)
- 快排划分 O(n)， 每次递归处理一侧的数据，理论上可以理解为每次折半，缺点 --> 存在内存不够的问题，因为需要一次读入所有数据
- 算法必学：经典的 Top K 问题（基本思路篇）
- 海量数据处理 - 10亿个数中找出最大的10000个数（top K问题） （各种资源场景分析，面试前可参考）
- 最小的K个数（代码实现，首选堆排）
- 答题思路
-
Java自带的 sort() 方法是如何实现的（阿里）
- Array.sort() / Collections.sort()
- DualPivotQuicksort（双轴快速排序）
- Arrays.sort和Collections.sort实现原理解析
- Collections.sort()和Arrays.sort()排序算法选择
-
写一个快速划分数据集的算法，要求测试集用新数据，训练集用老数据（第四范式）
- 数据格式为 Record（id, timestamp）
- 函数签名为 division(ArrayList dataset, double ratio)， ratio为(0,1)的划分比例
- 要求复杂度为O(n)
-
从一大段文本中找出TOP K 的高频词汇
- System Design Interview - Top K Problem (Heavy Hitters) （系统设计角度思考本题，如何权衡性能和效率，较为高阶）
- 347. 前K 个高频元素 （数字频次代码实现，建堆，时间复杂度为nlog(k)）
- 692. 前K个高频单词 （词汇频次代码实现，思路一致）
-
反转链表（小红书/腾讯/字节跳动）
-
环形链表（星环/微软）
-
判断一个序列是否为合理的出栈顺序（网易）
-
最长有效括号（Wish）
-
旋转链表（字节跳动）
-
删除链表 M 个节点之后的 N 个节点（微软）
- 要求用递归，不能循环
- 删除链表 M 个节点之后的 N 个节点
-
复杂链表的复制
- 连接一个重复链表
- 断链，拆分成两个链表
- 138. 复制带随机指针的链表
-
约瑟夫环问题
- 推数学公式 / 蛮力法
- 面试题62. 圆圈中最后剩下的数字
-
滑动窗口最大值
- 通过设计新的数据结构来降低复杂度，保存最大值&当前值，删除中间无关值
- 239. 滑动窗口最大值
-
如何找出一个字符串中的最大不重复子串（蜻蜓FM/美团/Wish/字节跳动）
- 滑动窗口 --> 滑动窗口直到最后一个元素，每当碰到重复时（可用一个Map记录，表示字母和位置），左指针往后走至当前位置，每轮都进行比较，取最大长度。 / 时间复杂度 --> O(n)
- 3. 无重复字符的最长子串
-
给定一个数，删除K位得到最大值（Unity）
- 单调栈
- 402. 移掉K位数字
-
至多包含 K 个不同字符的最长子串
-
字符串的排列
- 深度优先搜索（DFS） + 剪枝
- 理解递归的构造过程 --> 每次固定一个字符，继续处理剩余字符
- 处理后还原交换（保证所有可能都被遍历到）
- 面试题38. 字符串的排列
- 46. 全排列 （相同思路）
-
至少有K个重复字符的最长子串
- 分治法，递归求解
- 用一个map计数，一个set存储不应该包含的字母（即 count < k）
- 双指针遍历字符串，一旦找到需要剔除的字符，判断该字符左右两边满足条件的最长子串，比较返回较大值
- 395. 至少有K个重复字符的最长子串
- 分割回文串
- 八皇后问题
- 24点问题及其优化（叽里呱啦）
- 大意和 679. 24 点游戏 类似
-
岛屿数量（爱奇艺/依图）
-
连通网络的操作次数（eBay）
-
给定一个二维整形矩阵[m] [n]，输出一个重新排列后的矩阵，满足：
[x] <= [x] >= [x] <= [x] ...
[x] >= [x] <= [x] >= [x] ...
[x] <= [x] >= [x] <= [x] ... 列元素也是相同逻辑，交替大于小于（输出一个候选解即可） （NewsBreak）
-
解数独（微软）
-
一个无向图，实现 isConnected(Node A, Node B) 和 connect(Node A, Node B) 方法（Morgan Stanley）
- 类似 面试题 04.01. 节点间通路，但不完全一样（有向、无向）
-
课程表问题
-
最佳折扣问题（EA）
- double calculateMinPrice(int [] counts, double [] prices, Map<int[], Double> promotions)
- counts表示一个要买的商品数量列表（如0011表示第3件和第4件都买一个），prices表示单价，promotions表示折扣表 比如 0011->9 表示第3件和第4件一起打包买打9折，输出一个最低价格
- 实现类似 动态规划_最小费用购物问题
-
设计一个模糊匹配算法，给定一个字符串列表和一个字符串，输出列表中最匹配的那个（若都不匹配可输出空串）（微软）
- 类似于 72. 编辑距离，基于字符长度配置好阈值（个人实现，不知道是否为意向答案，反正过了）
-
最长回文子串（百度/字节跳动）
-
完全平方数（微软）
-
最长递增子序列（微软）
-
正则表达式匹配
-
零钱兑换
-
鸡蛋掉落
- dp[K] [N] = 1 + max(dp[K - 1] [i - 1] + dp[K] [N - i]) + 1 (i~(1,N)) （K蛋N层，最直观的DP，还有其他解法）
- 887. 鸡蛋掉落
- Egg Dropping Dynamic Programming （画状态转移表）
-
单词拆分
-
完全平方数
-
实现一个线程安全的单例模式（星环/阿里）
- 懒汉模式 --> Lazy初始化
- 饿汉模式 --> 在方法调用前，实例就已经创建好了
- 全部 sychronized 锁住 --> 可以保证线程安全，但销效率低
- “双重检查锁” 机制版本 （面试用，注意
getInstance()方法 和对应 instance 实例 都需要static关键字修饰）- volatile 来保证其线程间的可见性，禁止指令重排序，保证返回的是初始化完全的对象，详见 Why is volatile used in double checked locking
- 同步代码块中使用二次检查，以保证其不被重复实例化
- 枚举enum和静态代码块的特性相似，在使用枚举时，构造方法会被自动调用，利用这一特性也可以实现单例（面试也可稍微提及）
- 高并发下线程安全的单例模式（最全最经典） （单例的N种实现）
- 单例模式（详尽介绍）
-
设计一个方案，提供不同算法调用接口（参数即为需要调用的方法名）（PayPal）
- 这题感觉非常开放，当时答了用 适配器模式，似乎面试官并不是特别满意，适配器模式 属于结构型模式，主要用于解决兼容性问题，实际此题还是以如何创建为主，用 工厂模式 为宜
-
设计一个方案，传入一个类型（如 圆形，矩形，三角形等），求对应的周长和面积，能用设计模式更好（字节跳动）
- 不使用设计模式的版本见 Java小程序之计算三角形/圆形/矩形的周长和面积
- 策略模式 ，将获取周长和面积的方法公共提取，将对应对象（圆/矩形等）作为参数传入，采用不同运算，详见 get-designpatterns
-
（项目相关）个人项目的查询引擎设置 AbstractProvider 这种抽象类用到了什么模式（星环）
- 模板模式（Template Pattern）
- 提取通用方法，便于维护 / 封装不变部分，扩展可变部分
-
设计一个表结构，用于记录高考之后学生的成绩，以及写一个查询得到某个城市的理科前十名（字节跳动）
- 具体题意忘了，
limit即可筛出前n条，但原意应该不止如此
- 具体题意忘了，
-
设计一个消息分发系统的表结构，需要满足 1.对某个用户发消息 2.对某类用户发消息 3.对所有用户发消息 （字节跳动）
-
找出在表A中但不在表B中的记录（根据某一个共同的column）（PayPal）
- 查询A、B表中，A表中B表没有的数据（三种方法）
-
LRU Cache（腾讯/Shopee/PayPal/Morgan Stanley）
- 头尾两个伪节点（避免判断） + 双向链表
- 146. LRU 缓存
-
买卖股票的最佳时机系列（野村证券/字节跳动/携程）
-
实现一个HashMap（微软）
- 要求：1. 定义内部存储结构； 2.实现 insert(key, value) 和 remove(key)；3.不能使用任何Java集合框架。
- 706. 设计哈希映射
- 自己动手实现一个HashMap （将Entry设置为单链表节点，删除时参考 剑指 Offer 18. 删除链表的节点 ）
-
求给定区间内子区间的最大值（区间内最小值*区间元素相加）（字节跳动）
- 要求时间复杂度O(n)
- 原题
-
斐波那契数列的尾递归实现（Wish）
- 面试官原意是斐波那契的递归实现如何优化
- 尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数
- 递归与尾递归总结
-
1到10000有多少个数字7（字节跳动，说思路即可）
- 答案 ：4000
- 腾讯面试题-0到9999这1万个数中有多少个数字7
-
给定精度（如小数点后10位），写一个函数求根号2的具体值（拼多多/字节跳动）
-
给定一个乱序数组[0,100]，替换其中一个数，找出这个被替换的数（字节跳动）
- 类似 142. 环形链表 II 思路，重复数字会形成环，双指针寻找（略奇技淫巧）
- 287. 寻找重复数
-
缺失的第一个正数（字节跳动）
-
顺时针打印矩阵（星环）
-
实现一个int转中文表示的函数，同时设计测试用例（微软）
- 定界数据范围 + 梳理演变规则（以“万”为节，化繁为简，以及“零”如何处理）
- 数字(int型范围内正整数)和中文的相互转换
-
100盏灯问题（百度）
-
给定一个数组，一个闭区间[n,m]，给出该数组中所有最大值在闭区间中的连续子数组数目（Shopee）
- 要求时间复杂度O(n)
- 如 [2,1,4,3]，[2,3]，有[2],[2,1],[3]，返回3
-
字符串相乘（微软）
-
用Java实现一个String转Map（Map<String,Object>）的函数，不能使用String的split和第三方库（喜马拉雅）
-
整数中1出现的次数（从1到n中1出现的次数）
-
单词接龙
- 广度优先 --> 队列 + 暴力搜索（遍历过的单词删除），视频讲解见 花花酱 LeetCode 127. Word Ladder - 刷题找工作 EP71
- 127. 单词接龙
-
分数到小数
- 将除法过程代码化
- 166. 分数到小数
-
只出现一次的数字
-
分糖果
- 从左至右扫一遍，再从右至左扫一遍，取两遍中的最大值
- 135. 分发糖果
-
实现一个命令行逆波兰计算器
-
Largest M-aligned Subset