Weride-NG-OA01 解答。求大米!

首先感谢yelv的问题帖子：

我三道OA，前两道全对，第三道有少数TLE，所以思路应该是正确的。也希望大佬指点下如何提升Q3的效率。

Disclaimer：以下code来自local IDE debug的脚本，与最终提交有一些差别，所以仅供参考。

BTW: 个人非常喜欢美国的OA，只要无脑写码就行，没有乱七八糟的心理测评，阅读理解，和IQ测试。希望国内的公司能够优化下招聘流程。

以下是解答。

————————————————————————————————————————————————————————————————————

Q1

Q1的思路比较简单：通过滑动窗口算法，在一个排序好的开发者技能列表中，找到一个长度为k的子序列，使得子序列中前半部分与后半部分的技能差值最小。

代码实现如下：

def findMinimumEffort(developerSkill, k):
    developerSkill.sort()


    m = k
    sm = 0
    sm1 = 0
    j = 0
    j1 = m
    ind = m // 2


    # Initial effort for the first m developers
    for i in range(m // 2):
        sm += developerSkill[i]
        sm1 += developerSkill[(m + 1) // 2 + i]

    ans = sm1 - sm

    # Sliding window approach to calculate the effort
    for i in range((m + 1) // 2, len(developerSkill) - (m + 1) // 2):
        sm += (developerSkill[ind] - developerSkill[j])
        sm1 += (developerSkill[j1] - developerSkill[i])
        ans = min(ans, sm1 - sm)
        ind += 1
        j += 1
        j1 += 1

    return ans


Q2

Q2相对比较难。但好在之前做过一道Citadel的OA。题干跟这题是一模一样的：

Q2的思路如下。我们的目的是判断一个无向树是否是一个特殊的树，并输出与这种特性有关的节点。首先，将输入的树简化，剔除叶子节点。然后，对简化后的树使用DFS，来找到最大深度的节点。最后，输出与这种特性有

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

    nodes = [1] + visitNodes + [n]
    total_dist = 0
    # Find parent and level of each node using BFS
    parents = {}
    levels = {}
    visited = set()
    queue = deque([(1, 0)])
    while queue:
        node, level = queue.popleft()
        visited.add(node)
        levels[node] = level
        for neighbor in tree[node]:
            if neighbor not in visited:
                parents[neighbor] = node
                queue.append((neighbor, level + 1))
    for i in range(1, len(nodes)):
        lca = find_LCA(nodes[i-1], nodes[i], parents, levels)
        # Use LCA to compute the distance between two nodes
        total_dist += distances_from_start[nodes[i-1]] + distances_from_start[nodes[i]] - 2 * distances_from_start[lca]
    return total_dist

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

billcipher 发表于 2023-11-17 21:30
lz做出来这么多都没收到vo吗，这公司的bar也太夸张了

今年太卷了，申请人数是录取人数的上百倍，OA几乎全对，都还要根据本科院校等，进步筛选lol。

Velocibird 发表于 2023-8-21 11:25
我跟lz相反，第二题有3个cases没过（不知道是不是tle）但第3题全过了。

第三题我的思路是，既然给定的是 ...

兄弟可以加一下v吗，号：jiahuanzhong

楼主有消息了吗

小亩_f9be5bb 发表于 2023-8-23 12:30
楼主有消息了吗

还没有唉，我还在等他家的回复。

小亩_f44c962 发表于 2023-8-24 05:08
还没有唉，我还在等他家的回复。

没消息就是好消息hh，我已经收到拒信了，应该是OA做的不太好

想问一下 题目是需要自己从stdin里读取input吗？ 还是只需要写相应的function就可以了

我也做了这个。

小亩_f44c962 发表于 2023-8-24 05:08
还没有唉，我还在等他家的回复。

不对，好像题目是一样的，但是我的做法和你不太一样。
第三题是树形dp,dfs出来1-n的路径然后for一for就行了。

有收到vo的一起交流准备一下的吗？我是C++ infra的