分享一下今年准备 Amazon OA 时整理的题目。

按照低中高的难度简单分了下类,最后的难题能理解思路是最好的,不建议死记硬背。

Easy

1. Maximum quality sent via a channel

给一个 packets 数组和 k 个 channel,要求每个 channel 里面必须至少有一个数组里面的元素,每个元素只能在一个 channel 里面。其中 packets 中的元素数量是大于等于 k 的。要求算出所有channel中位数之和的最大值。

def solution(packets: List[int], channels: int) -> int:
    """
    将 packets 排序,依次把最大的一个元素分配给各 channel,
    剩下的元素放到最后一个 channel。
    """
    packets.sort()
    total = 0
    length = len(packets)
    for i in range(length - channels + 1, length):
        total += packets[i]
    rest = length - channels + 1
    if rest % 2 == 0:
        sum = packets[(rest - 1) // 2] + packets[rest // 2]
        total += sum // 2 if sum % 2 == 0 else sum // 2 + 1
    else:
        total += packets[rest // 2]
    return total

这是当时做 OA 的第一题,很轻松搞定,结果第二题非常 Hard,下面会提到。

2. Minimum swaps to make max & min corners

大意是对于一个数组,把最小值和最大值分别移动到左右两端最少需要多少次交换。

def solution(nums: List[int]):
    '''
    先遍历出最小值和最大值的下标,再计算距离即可。
    如果两个值会出现交换则结果减一。
    '''
    min_, max_ = float('inf'), -float('inf')
    index_min = index_max = 0
    for i in range(len(nums)):
        num = nums[i]
        if num < min_:
            index_min = i
            min_ = num
        if num > max_:
            index_max = i
            max_ = num
    swaps = index_min + len(nums) - 1 - index_max
    return swaps - 1 if index_max < index_min else swaps

3. Grouping digits

给定一个只包含 0 和 1 的数组,将所有的 0 和 1 分别放置到数组的任意两端,最少需要多少次交换。

def solution(array: List[int]):
    '''
    思路是先假设把所有的 1 交换到右端,
    从左遍历数组,累积记录交换次数。
    当然也可以把 1 交换到左端,所以最后比较选择更小值。
    '''
    res1 = num_of_1 = 0
    for digit in array:
        if digit == 1:
            num_of_1 += 1
        else:
            res1 += num_of_1
    num_of_0 = len(array) - num_of_1
    return min(res1, num_of_0 * num_of_1 - res1)

更详细的解释可以参考 Stackoverflow

4. Minimum swaps to make binary palindrome

给一个只有 0 和 1 的数组,找到形成回文结构的最小交换次数。

def solution(binary: List[int]):
    """
    双指针从两端开始看,记录 diff 总数。
    如果 diff 为偶数,那么交换次数为 diff 的一半即可,比如 0101;
    如果 diff 为奇数但是总位数为偶数则不可能做到,比如01;
    如果 diff 为奇数总位数也为偶数则也交换 diff 的一半次数即可,比如011。
    """
    n = len(binary)
    count = 0
    for i in range(n // 2):
        if binary[i] != binary[n - i - 1]:
            count += 1
    if count % 2 == 1 and n % 2 == 0:
        return -1
    return (count + 1) // 2

5. Max subarray length with product 1

给一个只有 -1 和 1 的数组,找到最长的子数组长度,条件是乘积为 1。

def solution(array: List[int]):
    """
    思路是如果整个数组中包含偶数个 -1,那么结果为总长度;
    否则找到两端的 -1,然后比较两个剩余长度。
    """
    neg_count = 0
    neg_first = neg_last = 0
    length = len(array)
    for i in range(length):
        if array[i] == -1:
            if neg_first == 0:
                neg_first = i
            neg_last = i
            neg_count += 1
    return length if neg_count % 2 == 0 else max(length - neg_first - 1, neg_last)

6. Valid discount coupon

大意是对于一个字符串来说,Valid 的条件是空字符串,或者一个 Valid 字符串两端加上相同字符,或者两个 Valid 字符串相连。

def solution(s: str):
    stack = []
    for char in s:
        if not stack or stack[-1] != char:
            stack.append(char)
        else:
            stack.pop()
    return len(stack) == 0

7. Linked list max pair

给一个偶数个节点的链表,对于每对第 n 个和倒数第 n 个的和,求最大值。

def solution(head: ListNode):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    first = head
    second = slow.next
    slow.next = None

    # 这里需要自己实现一个 reverse
    second = reverse(second)
    res = -float('inf')
    while first:
        res = max(res, first.val + second.val)
        first = first.next
        second = second.next
    return res

8. Combine if left is smaller than right

大意是对一个数组(package 之类的)进行合并,条件是左边元素小于右边,求合并之后数组中的最大值。

def solution(nums: List[int]) -> int:
    """
    注意要从后往前遍历。
    """
    if not nums:
        return 0
    res = cur = nums[-1]
    for i in range(len(nums) -2, -1, -1):
        if nums[i] < cur:
            cur += nums[i]
        else:
            cur = nums[i]
        res = max(res, cur)
    return res

9. Minimum number of rounds

Deliver boxes,一次只能运送两个或三个相同重量的 box,求最小运送次数。

def solution(weights: List[int]):
    from collections import Counter
    counts = Counter(weights)
    ans = 0
    for k, v in counts.items():
        if v == 1:
            return -1
        else:
            ans += v // 3
            ans += 1 if v % 3 != 0 else 0
    return ans

10. Kindle pages

大意是在一个 0 和 1 的序列中找到满足 010/101 的组合数量。

def solution(s: str) -> int:
    n = len(s)
    n1 = s.count('1')
    n1_cur = 0
    res = 0
    for i, char in enumerate(s):
        if char == '0':
            res += n1_cur * (n1 - n1_cur)
        else:
            res += (i - n1_cur) * (n - n1 - i + n1_cur)
            n1_cur += 1
    return res

参考 Leetcode 选择建筑的方案数

11. Nearest restaurant

选择最近的 k 个点。

def solution(points: List[List[int]], k: int) -> List[List[int]]:
    heap = []
    import heapq
    for p in points:
        x, y = p
        element = [-x**2-y**2, p]
        if len(heap) == k:
            heapq.heappushpop(heap, element)
        else:
            heapq.heappush(heap, element)
    return [item[1] for item in heap]

参考 Leetcode 最接近原点的 K 个点

12. MEX array

很有意思的一道题。

The MEX of an array is equal to the smallest positive integer that is not present in the array.

给一个大小为 N 的正数数组,元素值各不相同。对于每个元素,如果去掉的话,找到对应的 MEX,返回同样大小为 N 的结果数组。

def solution(nums: List[int], n: int):
    length = 100001
    hashtable = [0] * length
    for i in range(n):
        hashtable[nums[i]] = 1
    mex = 0
    for i in range(1, length):
        if hashtable[i] == 0:
            mex = i
            break
    res = [0] * n
    for i in range(n):
        if nums[i] < mex:
            res[i] = nums[i]
        else:
            res[i] = mex
    return res

参考 Construct MEX array from the given array

Medium

1. Maximum number of engineering teams

一个数组表示 engineers,数值表示 skill,组建 team_size 个人的团队,每个团队的 skill 差距不能超过 maxdiff。求最多能组建多少个团队。

def solution(team_size: int, maxdiff: int, skill: List[int]):
    """贪心,将 skill 排序后从头查找即可。"""
    i = 0
    teams = 0
    skill.sort()
    while i < len(skill):
        if i + team_size - 1 >= len(skill):
            break
        if skill[i+team_size-1] - skill[i] > maxdiff:
            i += 1
            continue
        teams += 1
        i += team_size
    return teams

2. Decreasing ratings

给一个数组,求连续下降的子数组个数。

def solution(ratings: List[int]) -> int:
    """
    大致思路是滑动窗口找单调递减的子数组。
    过程中不断叠加子数组长度即可,比如 [...1, 2, 3...],
    满足条件的有 1, 2, 3, 1 2, 2 3, 1 2 3 一共 1 + 2 + 3= 6 个。
    """
    res = 0
    left = 0
    for right in range(len(ratings)):
        if right > 0 and ratings[right - 1] - ratings[right] != 1:
            left = right
        res += right - left + 1
    return res

3. Maximum sustainable cluster size

Question on AWS power consumption, given BootingPower[i], processingPower[i], powerMax.

For maximum utilization, the data center wishes to group these processors into clusters.

Clusters can only be formed of processors located adjacent to each other.

For example, processors 2,3,4,5 can form a cluster, but 1,3,4 cannot. cluster of k processors defined as (i, i+1,…., i+k-1)

Net power consumption = maximum booting power among the k processors + (sum of processing power of processors)*k.

A cluster is said to be sustainable if it’s net power consumption does not exceed a given threshold value powerMax.

Example:

bootingPower = [3,6,1,3,4]

processingPower = [2,1,3,4,5]

powerMax = 25

If k = 2, any adjacent pair can be choosen.

The highest usage is the pair [4,5] with net power consumption 4 + (4 + 5)2 = 22.

Next, try k = 3. Group the first 3 processors together as:

Here,

Max booting power = max(3,6,1)

Sum of processing power = 2 + 1+ 3 = 6

Net power consumption = 6 + 63 = 24 <= powerMax

Thus, k = 3 is a sustainable cluster.

Example:

bootingPower = [8,8,10,9,2]

processingPower = [4,1,4,5,3]

powerMax = 33

If k = 2, consisting of first 2 processors.

Net power consumption = max(8,8) + (4+1)*2 = 18 <= 33 (powerMax)

Thus, k = 2 is a sustainable cluster.

Example:

bootingPower = [11,12,19]

processingPower = [10,8,7]

powerMax = 6

k = 0, not possible to form any sustainable clusters.

def solution(booting_power, processing_power, power_max) -> int:
    """用单调栈定位 booting_power max,再配合滑动窗口找 max size。"""
    size = 0
    i = j = 0
    total = 0
    from collections import deque

    dq = deque([])
    while j < len(processing_power):
        total += processing_power[j]
        # 注意没有等号,但是如果保存下标的话就可以用等号
        while dq and dq[-1] < booting_power[j]:
            dq.pop()
        dq.append(booting_power[j])
        while i <= j and dq[0] + total * (j - i + 1) > power_max:
            if processing_power[i] == dq[0]:
                dq.popleft()
            i += 1
        size = max(size, j - i + 1)
        j += 1
    return size

4. WIFI router

Amazon has installed WiFi routers on the houses along a straight street. The city’s buildings are arranged linearly, denoted by indices 1 to n. There are m Amazon routers, and each has a certain range associated with it. Router j installed at a certain building location /can only provide Internet to the buildings in the range [(i - routerRangelin, (i+ routerRange(iN] inclusive, where routerRangeli] is the range parameter of router j.

A building is considered to be served if the number of routers providing Internet to the building is greater than or equal to the number of people living in it. Given a list of the number of people living in each building, the locations of the buildings where the routers will be installed and each router’s range, find the number of served buildings in the city.

Example:

buildingCount = [1, 2, 1, 2, 2]

routerLocation = [3, 1]

routerRange = [1, 2]

There are 5 buildings with tenant counts shown in buildingCount.

Routers are located in buildings 3 and 1 with ranges 1 and 2 as shown in routerLocation and routerRange.

The first router is in building 3 and provides Internet to buildings in the range [2, 4].

def solution(buildings: List[int], locations: List[int], ranges: List[int]):
    """
    思路是使用差分数组做优化,达到 O(n) 复杂度。
    差分数组每一位 i 的值是 nums[i] - nums[i-1],
    所以更新 [i, j] 只需要更新 i 和 j 两个位置,前者加,后者减,
    最后对差分数组求前缀和就是原数组。
    """
    length = len(buildings)
    cover = [0] * length
    for i in range(len(locations)):
        start = min(locations[i] - ranges[i] - 1, 0)
        end = max(locations[i] + ranges[i], len(locations))
        cover[start] += 1
        if end < len(locations):
            cover[end] -= 1
    res = pre = 0
    for i in range(length):
        cover[i] += pre
        pre = cover[i]
        if cover[i] >= buildings[i]:
            res += 1
    return res

关于差分数组的应用可以参考 Leetcode 航班预订统计

5. Robot with strings

There are three robots named Ray, Ben, and Kevin. Initially Ray has a string S of length N, while the other two robots have empty strings. We can make either of the following moves:

Move 1: Remove the first character from Ray’s string and append it to Ben’s string.

Move 2: Remove the last character from Ben’s string and append it to Kevin’s string.

You must perform either fo the two moves mentioned above in such a way that the strings left with Ray and Ben are empty and the string left with Kevin is lexicographically smallest string that Kevin has after completing this activity.

def solution(s: str):
    '''
    主要思路是先找到(第一个)最小的 char 的 index,把中间的字母都入栈,再往后找。
    找到之后也需要和栈顶的元素比较,如果栈顶元素更小就不断出栈,即优先使用栈顶元素。
    '''
    res = []
    stack = []
    length = len(s)
    index = 0
    while index < length:
        smallest = index
        char = s[index]
        for i in range(smallest + 1, length):
            if s[i] < char:
                smallest = i
                char = s[i]
        for i in range(index, smallest):
            stack.append(s[i])
        while stack and stack[-1] <= char:
            res.append(stack.pop())
        res.append(char)
        index = smallest + 1
    while stack:
        res.append(stack.pop())
    return ''.join(res)

6. Demolition robots

Given a matrix with values 0 (trenches) , 1 (flat) , and 9 (obstacle) you have to find minimum distance to reach 9 (obstacle). If not possible then return -1.

The demolition robot must start at the top left corner of the matrix, which is always flat, and can move on block up, down, right, left.

The demolition robot cannot enter 0 trenches and cannot leave the matrix.

Sample Input :

[1, 0, 0],

[1, 0, 0],

[1, 9, 1]]

Sample Output :

3

def solution(grid: List[List[int]]) -> int:
    """BFS/DFS 均可。"""
    m, n = len(grid), len(grid[0])
    res = 0
    from collections import deque
    dq = deque([(0, 0)])
    grid[0][0] = 0
    while dq:
        res += 1
        for _ in range(len(dq)):
            i, j = dq.pop()
            for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
                if 0 <= x < m and 0 <= y < n and grid[x][y] != 0:
                    if grid[x][y] == 9:
                        return res
                    if grid[x][y] == 1:
                        dq.appendleft([x, y])
                        grid[x][y] = 0
    return -1

7. Prime air route

This problem is a variant of closest pair sum. You’ll be given two arraysarr1 = { {1, 2000}, {2, 3000}, {3, 4000} }arr2 = { { 1, 5000 }, {2, 3000} }the first element of every pair represents id and the second value represents the value.and a target x = 5000Find the pairs from both the arrays whose vaue add upto a sum which is less than given target and should be closest to the target.

Output for the above example:{ {1, 2} } // Note that the output should be in id’s

def prime(
    data_in: List[List[int]], data_out: List[List[int]], target: int
) -> List[List[int]]:
    """
    思路大概和 closest 3sum 一致:
    1. 两个列表排序
    2. sum 大于 target 则 high--
    3. sum 小于等于需要进一步划分
      1. 如果 distance 小于之前则清空结果列表,否则不动
      2. 加入当前 pair,并且对于 low 和 high 继续往中间查找相同元素,取笛卡尔积并保存结果
    """
    from itertools import product

    data_in.sort(key=lambda x: x[1])
    data_out.sort(key=lambda x: x[1])
    low, high = 0, len(data_out) - 1
    sum, distance = 0, float("inf")
    res = []
    while low < len(data_in) and high >= 0:
        m, n = data_in[low][1], data_out[high][1]
        sum = m + n
        if sum <= target:
            if abs(sum - target) < distance:
                res.clear()
                distance = abs(sum - target)
            lefts, rights = [], []
            while low < len(data_in) and data_in[low][1] == m:
                lefts.append(data_in[low][0])
                low += 1
            while high >= 0 and data_out[high][1] == n:
                rights.append(data_out[high][0])
                high -= 1
            for id1, id2 in product(lefts, rights):
                res.append([id1, id2])
        else:
            high -= 1
    return res

8. Kindle brackets

There is a string with the charcater [,(,),],? find the number of possible ways to divide the string into two substring (Continuoes) such that number of open and closing bracket should be same in both substring with same type, you can use ? as a wild card to satisfy either opening or closing bracket of any type.

def brackets(s: str):
    from collections import Counter, defaultdict
    right = Counter(s)
    left = defaultdict(int)
    ans = 0

    for i, c in enumerate(s[:-1]):
        right[c] -= 1
        left[c] += 1

        left_bra_diff = abs(left['['] - left[']'])
        left_par_diff = abs(left['('] - left[')'])
        left_diff = left_bra_diff + left_par_diff

        right_bra_diff = abs(right['['] - right[']'])
        right_par_diff = abs(right['('] - right[')'])
        right_diff = right_bra_diff + right_par_diff

        if (left_diff <= left['?'] and (left['?'] - left_diff) % 2 == 0) and (right_diff <= right['?'] and (right['?'] - right_diff) % 2 == 0):
            ans += 1

    return ans

9. DNA sequencing

Trie 的应用,主要在于通过倒序插入字符来匹配 Stream 中出现的相似 Pattern。

参考 Leetcode 字符流

10. Insert & View

自定义一个堆,实现 Insert 和 View 两个接口。每次 View 的时候都会查找下一个最小值,比如第一次查找最小值,第二次查找倒数第二小值,依次类推。

import heapq

class MaxHeapObj:
    def __init__(self, val, name):
        self.val = val
        self.name = name

    def __lt__(self, other):
        if self.val == other.val:
            return self.name > other.name
        return self.val > other.val

    def __eq__(self, other):
        return self.val == other.val and self.name == other.name

    def __str__(self):
        return str(self.val)


class CustomHeap:
    def __init__(self):
        # 主要思路还是保证 max heap 中有 view_count 个最小的元素,
        # 这样 min heap 顶端的元素就是第 k 小的,view 的时候直接返回即可
        self.min_heap = []
        self.max_heap = []
        self.view_count = 0

    def addToHeap(self, name, value):
        heapq.heappush(self.min_heap, (value, name))
        val, name = heapq.heappop(self.min_heap)
        heapq.heappush(self.max_heap, MaxHeapObj(val, name))

        # maintain the size property
        if len(self.max_heap) > self.view_count:
            max_heap_obj = heapq.heappop(self.max_heap)
            val, name = max_heap_obj.val, max_heap_obj.name
            heapq.heappush(self.min_heap, (val, name))

    def view(self):
        self.view_count += 1
        # 这种情况出现在连续多次 view 的时候;
        # 应该不用考虑 view 次数超过 item 数量的情况,那样的话 min_heap 空了会报错
        while len(self.max_heap) < self.view_count - 1:
            val, name = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, MaxHeapObj(val, name))
        return self.min_heap[0][1]

11. Province connected

参考 Leetcode 省份数量

12. Best combo inventory

Amazon Shopping has n items in inventory. Each item has a rating that may be negative. The team wants to work on an algorithm that will suggest combinations of these items that customers might buy, or, combos for short.

Example:

n = 3, popularity = [3, 5, -2], k = 3

Output [8, 6, 5]

大意应该是找出最贵的前 k 个组合。

原有的非优解法代码已移除

经过评论里的好心人提醒,我发现这道题已经在 Leetcode 中添加了。同时要修正下,这道题实属 Hard,放在 Medium 中屈尊了。。

主要有两个难点:

  1. 将所有正数的和作为最大值;通过绝对值的方式统一看待正负数。
  2. 利用最大堆(或者最小堆)和二元选择找到排序数组的 Top K 子序列的和。

最后的时间复杂度为 O(n*logn+k*logk),前面是为了数组排序,后面是 Top K 算法的成本。

参考这份题解,里面的视频讲解可能更好理解一些。

Hard

1. Maximum password strength

大意是给一个字符串,对每一个子串计算不同字符的个数,最后求所有子串计算结果的总和。

def solution(s: str):
    """
    对于重复 letter 也计算,但只算一次。
    对于 i 字母结尾的子串,做出的贡献是到前面重复字母之间的长度。
    """
    res = count = 0
    last = {}
    for i, char in enumerate(s):
        count += i - last.get(char, -1)
        res += count
        last[char] = i
    return res

参考 Leetcode 字符串的总引力

另外还有一道题很类似,但是计算时只考虑出现一次的字符,重复的则忽略:计算子串中的唯一字符

2. Shipment imbalance

给一个数组,对于所有的子数组计算其中最大元素与最小元素的差值,返回所有的差值的和。

def solution(nums: List[int]) -> int:
    """
    主要是单调栈的应用。
    下面的代码还可以进一步简化,比如求两个最小栈可以通过一次循环得到。
    """
    length = len(nums)
    min_left, max_left = [0] * length, [0] * length
    min_stack, max_stack = [], []
    for i in range(length):
        # min_left 和下面的 min_right 要保证一开一闭,不然会遗漏或重复计算
        while min_stack and nums[min_stack[-1]] > nums[i]:
            min_stack.pop()
        min_left[i] = min_stack[-1] if min_stack else -1
        min_stack.append(i)

        # max_left 和 max_right 同理
        while max_stack and nums[max_stack[-1]] <= nums[i]:
            max_stack.pop()
        max_left[i] = max_stack[-1] if max_stack else -1
        max_stack.append(i)

    min_right, max_right = [0] * length, [0] * length
    min_stack, max_stack = [], []
    for i in range(length - 1, -1, -1):
        while min_stack and nums[min_stack[-1]] >= nums[i]:
            min_stack.pop()
        min_right[i] = min_stack[-1] if min_stack else length
        min_stack.append(i)

        while max_stack and nums[max_stack[-1]] < nums[i]:
            max_stack.pop()
        max_right[i] = max_stack[-1] if max_stack else length
        max_stack.append(i)

    res = 0
    for i in range(length):
        res += (i - max_left[i]) * (max_right[i] - i) * nums[i]
        res -= (i - min_left[i]) * (min_right[i] - i) * nums[i]
    return res

参考 Leetcode 子数组范围和

3. Minimum swaps to sort an array

基于归并排序计算数组中的逆序对,参考 Leetcode 剑指 Offer 51,官方视频讲解非常好,一定要看。

4. Package shipping minimum cost

一道 DP 题目,大致参考 Leetcode 解决智力问题

5. Piles of products

def solution(piles: List[int]):
    '''
    dp[i] 表示以 i 位置元素结尾的最大 products 数,则 dp[i] = 等差数列求和[j..i] + dp[j]。
    利用单调栈寻找 j 的位置,即 last smaller element,条件为横坐标的差值。
    等差数列求和公式:n * (a1 + an) / 2。
    '''
    res = 0
    stack = []
    length = len(piles)
    dp = [0] * length
    for i in range(length):
        while stack and piles[stack[-1]] >= piles[i] - (i - stack[-1]):
            stack.pop()
        # 注意这里要对 i+1 和 piles[i] 取更小值,因为即使 products 够多,横向可能也不够长
        len = min(i + 1, piles[i]) if not stack else i - stack[-1]
        dp[i] = (piles[i] + piles[i] - len + 1) * len / 2 + (0 if not stack else dp[stack[-1]])
        res = max(res, dp[i])
        stack.append(i)
    return res

6. Power subset sums

第二题碰到的便是这个,算是很有难度的一道了。可惜准备不足,当场没有写出理想的解法,后来还专门写了一篇做记录:Sum of Total Strength of Wizards(Leetcode 有原题)。真的碰到不会的话最好写个暴力解法,至少还可以过一些 Simple cases,应该不至于影响最终结果。

7. Max deviation of all strings

一道 DP 题目,参考 Leetcode 最大波动的子字符串

准备的时候尝试看了看,没有特别理解,于是便放弃了,好在也没碰到。


希望能帮助到有需要的人,Good luck!