美团 2025 届校招开始了，岗位 and 原题抢先看！！
美团 2025 届校招开始了，岗位 and 原题抢先看！！
美团校招 - 启动
前几天我们写了 阿里巴巴 开启 2025 届的校招计划，其实比阿里巴巴更早的是 美团。
你看，互联网大厂启动校招计划尚且争先恐后，你还有什么理由不马上行动？！
先来大概浏览一下本次校招「技术类」相关的常规岗位：
几乎所有岗位都可以 base 北京，少部分可以选择 上海 和 成都 。
然后再详细列举一下于公主号读者相关性更高的几个岗位：
前端 & 客户端
后端
自然语言处理
计算机视觉
除了这些常规校招岗位，美团本次还延续了「北斗计划」的开展，都是一些细分领域的算法岗。
北斗计划是美团面向全球精尖校园科技人才的招聘项目，性质有一点点类似于华为的「天才少年」，但难度和待遇自然是不能和华为比的，可简单将「北斗计划」理解为算法岗中的 SP/SSP 吧。
由于美团的校招规则是「最多可投递3个职位，但同一时间仅有1个职位流程处于进行中，第一志愿将被优先考虑」，因此建议对算法岗有意向的同学，可适当调整「常规校招算法岗」和「北斗计划」的投递顺序。
...
回归主线。
不管是开发还是算法，常规还是北斗，算法都是在校招中无法绕过的环节。
来都来了，做一道和「美团」相关的算法原题，这是一道去年的校招原题。
题目描述
平台：LeetCode
题号：808
有 A 和 B 两种类型 的汤，一开始每种类型的汤有 n 毫升。
有四种分配操作：
- 提供
100ml的 汤A 和0ml的 汤B 。 - 提供
75ml的 汤A 和25ml的 汤B 。 - 提供
50ml的 汤A 和50ml的 汤B 。 - 提供
25ml的 汤A 和75ml的 汤B 。
当我们把汤分配给某人之后，汤就没有了。
每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。
如果汤的剩余量不足以完成某次操作，我们将尽可能分配。
当两种类型的汤都分配完时，停止操作。
注意 不存在先分配 100 ml 汤B 的操作。
需要返回的值：汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2。
返回值在正确答案
的范围内将被认为是正确的。
示例 1:
输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。
示例 2:
输入: n = 100
输出: 0.71875
提示:
数学 + 动态规划
四种分配方式都是
的倍数，因此我们可以将
进行除以
上取整的缩放操作，并将四类操作等价成：
- 提供
4ml的 汤A 和0ml的 汤B 。 - 提供
3ml的 汤A 和1ml的 汤B 。 - 提供
2ml的 汤A 和2ml的 汤B 。 - 提供
1ml的 汤A 和3ml的 汤B 。
定义
为 汤A 剩余
毫升，汤B 剩余
毫升时的最终概率（
）。
最终答案为
为最终答案，考虑任意项存在为
情况时的边界情况：
- 若
且
，结果为
，即有
- 若
且
，结果为
，即有
，其中
- 若
且
，结果为
，即有
，其中
其余一般情况为
和
均不为
，由于四类操作均为等概率，结合题意和状态定义可知：
由于
，即使进行了除
的缩放操作，过多的状态数仍会导致 TLE。
此时需要利用「返回值在正确答案
的范围内将被认为是正确的」来做优化（一下子不太好想到）：由于四类操作均是等概率，单个回合期望消耗汤 A 的量为
，消耗汤 B 的量为
。
因此当
足够大，操作回合足够多，汤 A 将有较大的概率结束分配，即当
足够大，概率值会趋向于
。
我们考虑多大的
能够配合精度误差
来减少计算量：一个可行的操作是利用上述的 DP 思路 + 二分的方式找到符合精度要求的验算值（不超过
）。
Java 代码：
class Solution {
public double soupServings(int n) {
n = Math.min(200, (int) Math.ceil(n / 25.0));
double[][] f = new double[n + 10][n + 10];
f[0][0] = 0.5;
for (int j = 1; j <= n; j++) f[0][j] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
double a = f[Math.max(i - 4, 0)][j], b = f[Math.max(i - 3, 0)][Math.max(j - 1, 0)];
double c = f[Math.max(i - 2, 0)][Math.max(j - 2, 0)], d = f[Math.max(i - 1, 0)][Math.max(j - 3, 0)];
f[i][j] = 0.25 * (a + b + c + d);
}
}
return f[n][n];
}
}
C++ 代码：
class Solution {
public:
double soupServings(int n) {
n = min(200, (int)ceil(n / 25.0));
vector<vector<double>> f(n + 10, vector<double>(n + 10, 0));
f[0][0] = 0.5;
for (int j = 1; j <= n; ++j) f[0][j] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
double a = f[max(i - 4, 0)][j], b = f[max(i - 3, 0)][max(j - 1, 0)];
double c = f[max(i - 2, 0)][max(j - 2, 0)], d = f[max(i - 1, 0)][max(j - 3, 0)];
f[i][j] = 0.25 * (a + b + c + d);
}
}
return f[n][n];
}
};
Python 代码：
class Solution:
def soupServings(self, n: int) -> float:
n = min(200, math.ceil(n / 25))
f = [[0] * (n + 10) for _ in range(n + 10)]
f[0][0] = 0.5
for j in range(1, n + 10):
f[0][j] = 1
for i in range(1, n + 1):
for j in range(1, n + 1):
a, b = f[max(i - 4, 0)][j], f[max(i - 3, 0)][max(j - 1, 0)]
c, d = f[max(i - 2, 0)][max(j - 2, 0)], f[max(i - 1, 0)][max(j - 3, 0)]
f[i][j] = 0.25 * (a + b + c + d)
return f[n][n]
TypeScript 代码：
function soupServings(n: number): number {
n = Math.min(200, Math.ceil(n / 25.0));
const f: number[][] = Array(n + 10).fill(0).map(() => Array(n + 10).fill(0));
f[0][0] = 0.5;
for (let j = 1; j <= n; j++) f[0][j] = 1;
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= n; j++) {
let a = f[Math.max(i - 4, 0)][j], b = f[Math.max(i - 3, 0)][Math.max(j - 1, 0)];
let c = f[Math.max(i - 2, 0)][Math.max(j - 2, 0)], d = f[Math.max(i - 1, 0)][Math.max(j - 3, 0)];
f[i][j] = 0.25 * (a + b + c + d);
}
}
return f[n][n];
};
- 时间复杂度：
，其中
为验算值
- 空间复杂度：
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。