美团二面

做笔试跟打牌似的，还玩上葫芦了。如果问的是随机抽五张牌，凑成葫芦的概率，这个能算吗？

整体感觉还是挺难，选择题考察面比较广，包括概率论，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) 时间。

第一题, 类似两数之和, 维护一下前面和他互补的数出现的次数 #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...

TimeLine:京东：2月~6月实习，5月底答辩，7月下offer美团：6月底~至今实习，8月上提交自评，8月中offer都是比较核心的部门，以后外卖只用🐶和🦘！许愿秋招顺利🙏！