美团二面

第一题, 类似两数之和, 维护一下前面和他互补的数出现的次数 #include <iostream> #include <vector> #include <unordered_map> using namespace std; typedef long long LL; const int M = 998244353; int main() { int n, m; cin >> n >> m; vector<LL> a(n + 10, 0); unordered_map<LL, vector<LL>&g...

整体感觉还是挺难，选择题考察面比较广，包括概率论，Python, c++语法，数据库，大数据，机器学习，深度学习等。编程第一题没啥思路，暴力搜索超时（已看网上大佬解答，应该有右边界一定等于n，之后线性扫描维护两个哈希表更新最优解即可求解，关键没看出来右边界这个事，em还是刷题少）；第二题还好有点思路，用滑动窗口+两个单调队列求解即可。贴一下，求进面试## 1. 选择题#### 1.1 概率轮#### 1.2 C++#### 1.3 Python#### 1.4 数据库#### 1.5 大数据#### 1.6 机器学习## 2. 编程题####  2.1 给定一个长度为n的序列，a1, a2, …, an, 在其中选择一个区间[L, R]，将区间中的元素全部加1之后变成数组b，求最大化逆序对差 inv(a)-inv(b)，逆序对满足性质i<j, ai>aj。​分析：任意选择一个区间[L, R]，将其中元素加1之后，选定区间中的逆序对数量不变，但是可以会导致R之后序列中逆序对的数量增加，**因此R一定取值为n**。之后我们需要确定区间左边界L的值；区间中元素加1之后，会使得[0, L-1]中逆序对的数量减少，因此我们只需要**求一个左边界L使得序列a中的逆序对减少量最大**。​为了完成上述任务，我们需要两个哈希表，哈希表1用于记录a序列中每一个元素左边元素x出现的次数；哈希表2用于记录a序列中每一个元素右边元素x出现的次数；之后遍历a序列，同时动态更新最大可以减少的逆序对的数量，记录最大减少量即为最优解。#### 2.2 在一场跳水比赛中，共有n位裁判依次为选手打分（打分为非负整数）。根据比赛规则，需要从所有裁判的打分中，选取连续的m个打分来计算选手的最终成绩。具体计算方式为：从这m个打分里去掉1个最高分和1个最低分，最后取剩余分数的平均值作为该选手的最终成绩。现在需要找到所有可能的连续m个打分区间中，最终成绩最高的那个区间，并输出该区间的起始裁判编号（从1开始计数）。如果有多个区间的最终成绩相同，输出起始编号最小的那个。​分析：对每个长度为 m 的连续区间，最终成绩$$\text{avg}=\frac{\text{sum} - \text{max} - \text{min}}{m-2}$$​因为 $m$固定，比较谁更大只需比较 **分子**$\text{sum}-\text{max}-\text{min}$。用两个 **单调队列** 分别维护窗口内的最大值与最小值（同时维护窗口总和）。这样每次滑动只需均摊 O(1) 时间。

测开，AI挺会帮我总结的，有些地方我真是梦到哪句说哪句了，结果AI听懂了还帮我做总结，收获还是挺大的，后面再面试就知道怎么回答了，感觉比真人面体验好很多 但不知道美团靠不靠AI面筛人，我刷牛客看其他公司有被AI面筛掉的面试题： 1. 自我介绍 2. 选择语言：选了Java，介绍一下JVM内存结构，堆和栈 3. 请描述一个熟悉的自动化测试框架 4. 介绍简历上的项目，会根据回答进行追问 5. 如何用大模型分析测试报告？ 6. 说一个预测成功的潜在问题

本来是想继续找实习的，莫名其妙给我约一个秋招，而且我不记得投过这个部门...硬着头皮面...项目1. 项目中分布式id如何实现的，为什么要使用时间戳+redis自增序列，只用其中的一个行不行2. 雪花算法的组成，为什么要加上机器号3. 分布式锁怎么实现的，为什么要加上线程标识，不加lua脚本哪种情况下会出现锁误删4. 实际业务中可能业务还没执行完锁就释放了，可能出现并发问题，怎么解决实习5. 分布式延迟队列怎么实现的八股6. 所有的数据放在同一个zset里面可能产生大key问题，怎么解决7. zset底层原理，跳表和普通链表相比有什么优点，时间复杂度8. Redis持久化方式，RDB写时复制原理9. Redis网络模型10. IO多路复用，epoll性能为什么比select高手撕11. 滑动窗口最大值12. 单词搜索