东子笔试816

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