首页 > 浙江之江实验室机试面经
头像
神盾局使命必达
编辑于 2022-10-21 09:44
+ 关注

浙江之江实验室机试面经

本人硕士,申请的是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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

热门推荐