2024年3月27日19:00-20:40，淘天集团2025届暑期实习生技术笔试。
总限时 100 分钟，共 100 分。前面有若干道单选/不定项选择，难度较大，包括 Linux 命令、权限，缓存、锁降级、锁高速缓存，Java 抽象类、抽象方法，设计模式，HTTP、Web Socket 等等。最后是三道算法题，分值分别为为 15/15/25 分。
编程题使用 ACM 模式，即需要自己处理输入输出。语言不限，不能用本地IDE（阿里系基本都是）。
Note: 试题回忆可能有错漏，且我的思路及解法较为笨拙，不敢保证正确性。抛砖引玉，敬请指正。
Q1 小苯的比赛上分
有一款著名的大型多人电子竞技游戏网站”喜爱福”，网站通常会举办一些比赛。通常一名参赛选手只有一个账号，但不难猜到，总会有人“开小号”上分。
小苯就是一位该游戏的忠实玩家，他总共有几个账号，每个账号的分数分别为 a_i。
他深谙游戏中一位著名玩家 st….lk的一句名言：“只要你永远打分更低的号，那么你的 maxRating 单调不降”（maxRating 指一名玩家分最高的账号的分数）
现在我们记录了小苯 m 次的比赛记录，已知小苯每次都会谨记st….lk的名言，从而使用分数最低的账号参赛，现在我们想知道小苯每次参赛后，他的maxRating 是多少，请你编写代码来算算吧。
输入描述
输入包含三行。
第一行两个正整数 n,m（1≤n,m ≤ 10^5），分别表示小苯的账号个数，和小苯新参加的比赛记录数。
第二行 n个整数a_i（0 ≤ a_i ≤ 10^9），表示小苯每个账号目前的分数。
第三行 m个整数（0≤ b_j ≤10^9），分别表示小苯每次比赛后，分数的变化值。（例如如果小苯使用分数为 x 的账号参赛，那么他在参加完第j场比赛后，该账号分数会变为x + b_j ）
输出描述
输出包含 m 行，每行一个整数，表示小苯参与完第 j 场比赛后，他的 maxRating 的值。
示例 1
输入
1
2
3
56
1145 1500 1600 1538 1222
10 400 500 1000 2000 10000
输出
1
2
3
4
5
6
1600
1600
1722
2500
3538
11555
说明
共比赛了6场，每场赛后都输出小苯当前分数最高的分数，如样例所示，前两场比赛后小苯分数为1145的账号涨到了 1555，因此第三场比赛使用当前分数最低的1222参赛，涨了500分变为1722，成为小苯分数最高的账号，因此第三场赛后输出1722。
My Solution
使用优先队列（最小堆），通过100%，较为简单。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import heapq
n, m = 5, 6
a = [1145, 1500, 1600, 1538, 1222]
b = [10, 400, 500, 1000, 2000, 10000]
max_rating = max(a)
heapq.heapify(a)
for i in range(m):
rating = b[i]
cur = heapq.heappop(a) + rating
max_rating = max(max_rating, cur)
heapq.heappush(a, cur)
print(max_rating)
Correct Solution
1
# The Same
Q2 小苯的区间删除
本题类似 1574. 删除最短的子数组使剩余数组有序，略微提升了难度。
小苯有一个长度为n的数组 a，他想要使得数组a有序（单调不降）。
为此，他必须选择一段区间 [L, R]（1≤ L ≤ R ≤ n），将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。
现在他想知道有多少种不同的选择区间的方案。
注：小苯认为，空数组也满足有序，即你可以选择 [1, n] 这个区间。
输入描述
输入包含两行。
第一行一个正整数n，（1 ≤ n ≤ 2 * 10^5），表示数组的长度。
第二行n个正整数 a_i，（1 ≤ a_i ≤ 10^9），表示数组 a。
输出描述
输出一行一个正整数表示答案。
示例 1
输入
1
2
3
1 2 3
输出
1
6
示例 2
输入
1
2
5
1 3 2 2 5
输出
1
10
My Solution (X)
基于力扣 1574 题的双指针思路，累加可能的删除区间数，通过了比赛时的两个测试用例。但提交后通过0%，原因不详，待 debug。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = 5
a = [1, 3, 2, 2, 5]
def count_range(a, n):
j = n - 1
ans = 0
while j > 0 and a[j - 1] <= a[j]:
j -= 1
if j == 0:
return n * (n - 1)
ans = n - j
for i in range(n):
while j < n and a[i] > a[j]:
j += 1
ans += n - j
return ans
print(count_range(a, n))
Correct Solution
1
# TODO
Q3 小苯的魔法染色
小红面前有一个长为n的墙a，（墙由一个个格子构成，方便起见用一个字符串表示），小红想将墙 a 染成全红色的，因此她找到了小苯。小苯是一个魔法师，可以对墙进行施法。墙上施法后的部分会被染红。
施法的具体过程：首先，小苯会选择一段区间 [L, R]（1≤ L ≤ R ≤ n），接着立马，墙上的［L, R] 这段区间就会被染红。例如a= WRWWR，小苯选择 [1, 3]后，a就会变成 RRRWR。（其中R表示红色，W表示白色。）
小苯可以施法不超过 m 次，但小红不想小苯因使用魔法太多而走火入魔，因此她限制小苯每一次选择施法的区间长度都必须在k以内。
（区间 [L, R] 的长度为 R - L + 1）
现在小苯想知道自己施法能使得墙全部被染红的最小 k 值是多少，请你帮帮他吧。
输入描述
输入包含两行。
第一行两个正整数n, m（1 ≤ m ≤ n ≤ 2×10^5 ），分别表示数组a的长度和小苯施法的最多次数。
第二行一个长度为n的字符串，表示墙的初始颜色。
（保证只出现“W”和”R”两种字符）
输出描述
输出包含一行一个正整数，表示k的最小值。
示例 1
输入
1
2
5 2
WRWWR
输出
1
2
说明
小苯可以进行 m = 2 次操作，每次操作的长度必须在2以内。
一种可能的染色方式是：选择 [1, 2] 再选择 [3, 4]，操作后整面墙都会被染红，可以证明不存在单次操作比2更小的长度。
Correct Solution
1
# TODO