本人硕士，申请的是CV算法岗，一个小时两道题，HR告诉我难度是由易到难，但是其实emmmm
之江实验室机试复盘
将试卷m道题分成两组，每组至少有一道试题。n个人参与考试，假设每个人会做的题是连续的。只要一组题满分即可通过考试，求最多可以有多少个人通过考试。
1. 输入
4 8
4 7
1 4
5 8
2 5
2. 描述：4个人，8道题
第一个人会做的题目是4~7
第二个人会做的题目是1~4
第三个人会做的题目是5~8
第四个人会做的题目是2~5
3. 输出
3
4. 解释，可分两组为[4][1,2,3,5,6,7,8]， 共3人可以通过
先说考试情况，我用O(m*n2)暴力搜索，通过率37%，剩下超时。
用两个数组存每个人会的题的边界L[i] 和R[i]，不打乱顺序的情况下，可以用i调用每个人的会做的题的左右边界。
也就是用窗长分别为1~m-1去滑动。
我花了大量时间思考滑动窗和动态规划，目前复盘也没想到解法。
根据和同学的讨论，发现O(mn)的解法：分类讨论
我们直觉将8道题分成1+7两组，大家只用完成任意一组即可通过，这样的通过率是最高的。但是有例外，比如说一半的人会做1~4，一半的人会做5~8
最后是所有人都可以通过考核，但是如果只拿一道题进行匹配，得不到正确结论。
所以我们将最优情况分成两类，一类是我们期待 【只用一道题，大家通过率最高】 以及第二类【用一个边界，将数组分成两半，大家通过率最高】，两种情况取最优解。
最后的时间复杂度从O(mn2)简化到O(mn)，记忆里n的规模在1e6左右，m在5000左右，不知道这种解法能不能AC。
如果还不能AC，需要考虑高级的数据结构替换两个储存边界的数组了。暂时还没有思路，欢迎大佬补充！
-------------------------------------------------------------------------------------------
更新：
用一个1*m矩阵PassNum表示每道题可以通过的人数，如果max(PassNum)不在边界，则表示用这一道题，通过的人数可以达到最多，若max_Pass = max(PassNum)在首尾，则需要考虑第二组题，也就是将试卷分为两组进行匹配。
首尾也就是题号1或8，我们遍历候选者，找出左边界==1的候选者最小右边界，也就是所有可以做出第一道题的人最小公共子区间。
例如：
5 位候选者，5道题
候选者可以完成的题号为：
【1 2 3】【1 2】【1 2】【3 4 5】 【4 5】
PassNum = 【3 3 2 2 2】，显然会做题号为1和2的人最多，1在边界，需要考虑第二组题的通过情况。
这时我们寻找包含题号1的候选者最小公共子区间，也就是【1 2 3】【1 2】【1 2】的最小公共子区间为【1 2】
我们可以把试卷分为【1 2】and【 3 4 5】，最多通过人数为3+1 = 4。
边界在尾同理，附代码（未通过大量测试验证），时间复杂度O(m*n)
while 1:
try:
n,m = map(int, input().split(' '))
L, R = [], []
Lrecord, Rrecord = [],[]
PassNum = [0]*m
max_Pass = 0
for i in range(n):
Li, Ri = map(int, input().split(' '))
for j in range(Li,Ri+1):
PassNum[j-1]+=1
max_Pass = max(max_Pass, PassNum[j-1])
L.append(Li)
R.append(Ri)
head = PassNum.index(max_Pass)
tail = PassNum[::-1].index(max_Pass)
second_cnt = 0
if head==0:
min_threshold = m-1
# 找最小公共子区间1~min_threshold
for i in range(n):
if L[i]==1:
min_threshold = min(min_threshold,R[i])
# 用新的threshold将试卷分成两套，检测有没有人能完成第二套题
for i in range(n):
if L[i]!=1 and L[i]<=min_threshold+1 and R[i]==m:
second_cnt+=1
print(max_Pass+second_cnt)
elif tail ==0:
max_threshold = 1
for i in range(n):
if R[i]==m:
max_threshold = max(max_threshold,L[i])
for i in range(n):
if R[i]!=m and R[i]>=max_threshold-1 and L[i]==1:
second_cnt+=1
print(max_Pass+second_cnt)
else:
print(max_Pass)
except:
break 对称数组问题， 输入m*n的10数组，问最少改多少个数，可以将数组变成轴对称数组？
PS：10数组指的是这个二维数组只有1或者0
考试情况：花了大量时间在思考第一道题，导致没时间做第二道题，第一想法是O(nm），判断数组每个数和其对角线的数是否相等，不等的话cnt++。
首先我并没有提交，所以不知道O(nm)可以不可以过，如果可以过的话，这道题未免太简单了，完全不符合HR说的难度设置，很后悔没时间来后面瞟一眼...
现在暂时没有想到更好的解法，也是欢迎大佬补充思路
写在后面：
根据我的调查这个之江实验室是浙大下属的，偏research大佬很多，本来想面大厂前刷刷野，结果把自己心态搞得有点崩。
分享面经是总结反思的过程，也是积攒人品的过程（我曾经是看不起转锦鲤换杨超越头像的人）... 发现自己相比较CS专业的，coding水平还是有差距，总结如下几点:
1. 一定要注意限时训练，我看到倒计时会很慌，想要早点敲键盘，忽略了思考的过程。
2. 惯性思维是思考算法，我花了大量时间在琢磨滑动窗和dp，甚至想到字典存数据，然后就可以对L[i]和R[i]排序了。但是这道题不按常理出牌，其实用直觉思考是可以分出这两类情况进行讨论的。
3. 不要死磕一道题（好像从小学老师就这么教我，我还是没学会）。机试是为了获得面试机会，要不择手段，不要追求完美，要先追求及格！！！
2022.10.21日更新:
转眼入职之江已经一年多了了. 这一年半有挫折有彷徨,但总的来说我很满意这里的工作环境和气氛. 由于机试和招聘政策的变化,我可能无法提供较为详尽的帮助. 但是如果有小伙伴需要内推或者收到offer, 想了解之江这个科研机构, 可以站内私信我哦
全部评论
(13) 回帖