Amazon Intern OA | 亚麻OA这难度稳了

又完成了一场 Amazon Intern OA ，虽然难度有点大，但没问题。有要准备Amazon 或者 Hackrrank题库的OA可关注，titok,google,meta,visa,stripe都OK，全部都稳，分享一下最近刚完成的一套亚麻OA。

Amazon Intern OA 分享

Q1

题目：给定 n 台服务器及其内存数组 memory[i]，系统必须由偶数台服务器组成，其中一半作为 primary，另一半作为 backup，并且每个 primary 都必须匹配一个内存值大于或等于它的 backup。系统的总内存容量定义为所有 primary 服务器内存之和。要求在满足匹配条件的前提下，从给定服务器中选择若干对 primary-backup，使系统内存容量最大，并返回该最大值。

思路：

• 由于每个 primary 都需要一个不小于它的 backup，最优策略是把服务器两两配对，并把每对中较小的当作 primary（较大的是 backup）。
• 为了让这些“较小值”的总和最大，应先对内存容量排序，然后按相邻元素配对。
• 排序后每对的较小值就是下标为 0,2,4,… 的元素；如果 n 为奇数，必须丢掉一个服务器才能组成偶数个，此时丢掉最小的更优，对应从下标 1 开始累加 1,3,5,… 。

代码：

def maximumCapacity(memory):
    a = sorted(memory)
    ans = 0
    i = len(a) % 2
    while i < len(a):
        ans += a[i]
        i += 2
    return ans

Q2

题目：给定 n 台服务器及其计算能力数组 power[i]，可以对任意连续子数组整体增加一个整数 x（每次操作选择一个区间并加上某个 x），目标是在经过若干次这样的区间加法操作后，使整个数组变为非递减序列，同时要求所有操作中增加值 x 的总和最小，最终返回这个最小总和。

思路：

• 从左到右遍历，维护前一个“最终值”t，保证当前处理完后前缀始终非递减。
• 对当前位置 a，若 a < t，则至少需要增加 add = t - a 才能不小于 t。
• 因为一次操作能对连续段整体加同一个 x，用 p_add 表示上一段已经在“尾部”叠加的增量；只有当本位置需要更大的增量时，才把差值 add - p_add 加到答案里。
• 更新 t = a + add 继续扫描，累积出的 ans 就是最小总加值。

代码：

def findMinimumSum(power):
    n = len(power)
    ans = 0
    p_add = 0
    t = power[0]
    for i in range(1, n):
        a = power[i]
        add = max(0, t - a)
        if add > p_add:
            ans += add - p_add
        p_add = add
        t = a + add
    return ans

Amazon Intern OA 更多相关真题可以联系我领取~

准备小结

如果你也在准备 Amazon Intern 或其他大厂的 OA／VO，可以直接联系 interviewAid 了解对应的面试辅助和陪跑支持。如果你想找我辅助面试，或者用 Amazon 面经 中的原题 mock，感受最真实的feedback，欢迎戳我。

全网唯一一家支持 L6 以上 system design mock，只放真实面经。

求职辅助服务，是关于时间和品质的较量。咨询interviewAid，获取最专业的Tech求职辅助。