Amazon OA 2022

分享一下今年准备 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,下面会提到。...

08-11 · 14 min

Sum of Total Strength of Wizards

前两天做了一道算法题,虽然没能成功解决,但是是一道很有意思的题目。 抛开题面的包装不谈,核心内容就是给定一个数组,计算它的所有子数组的最小值与加和的乘积的总和。 (这里要注意子数组的定义,一定是连续的,如果不连续的话叫做子序列。) 比如对于 [1, 2, 3] 来说,一共有六种情况: [1]: 1 * 1 = 1 [2]: 2 * 2 = 4 [3]: 3 * 3 = 9 [1, 2]: 1 * (1 + 2) = 3 [2, 3]: 2 * (2 + 3) = 10 [1, 2, 3]: 1 * (1 + 2 + 3) = 6 最后答案为 1 + 4 + 9 + 3 + 10 + 6 = 33。...

07-26 · 3 min

Python heapq 源码阅读

Heap 作为一种重要的数据结构,有许多应用场景,比如优先级队列,每次出队的都是最大值或者最小值的元素。很多语言都集成了相关实现,比如 Java 的 PriorityQueue,而 Python 提供了 heapq 模块。 因为 Heap 通常用数组而不是链表存储,所以 Python 里面的 Heap 实质上就是一个列表,而 heapq 提供的几个函数也是以列表对象作为参数的: from heapq import heappush, heappop, heappify, heapreplace, heappushpop heap = [] heappush(heap, 1) item = heap[0] # 第一个元素代表堆顶元素 heappop(heap) heapify([3, 2, 1, 5, 6, 4]) # 把普通列表转化为堆结构 [1, 2, 3, 4, 5, 6] heapreplace([3, 4, 5], 1) # 直接将堆顶元素 3 替换为 1,最后堆结构为 [1, 4, 5] heappushpop([3, 4, 5], 1) # 先将 1 插入堆中,再 pop 出堆顶元素,最后堆结构为 [3, 4, 5] 为什么 heapq 提供的是最小堆而不是更常见的最大堆呢?这就得从源码中找答案了。...

11-29 · 4 min

Python OrderedDict 实现 LRU 缓存

LRUCache 是一种经典的缓存机制,它的基本思路是按照最近使用的时间对元素排序,在清理时优先把搁置最久的删除掉。 如果不想给每个缓存元素都记录一个时间戳的话,可以应用哈希链表来简单地实现 LRU 算法。也就是对一个哈希表中的所有元素增加指针,从而串起一个双链表,这样既可以快速 get value,又可以通过把最近使用过的元素放到头部来维护顺序,删除的时候从末尾开始就好了。 手写双链表并不困难,但是借助 OrderedDict 的话,可以写出非常简短的代码: from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.capacity = capacity self.hashtable = OrderedDict() def get(self, key: int) -> int: if key in self.hashtable: self.hashtable.move_to_end(key, last=False) return self.hashtable[key] return -1 def put(self, key: int, value: int) -> None: self.hashtable[key] = value self.hashtable.move_to_end(key, last=False) if len(self.hashtable) > self.capacity: self.hashtable.popitem() 其中最神奇的就是 move_to_end 和 popitem 方法(后者默认是弹出最后面的元素)的使用,这也得益于 OD 可以保证 key-value pair 的顺序。那么 OD 是如何做到的呢?其实还是双链表,下面是它的 Python 实现:...

11-28 · 3 min

Understand Recursion Better

在 Simple Recursion 之后,我一度把递归当作一种算法。但通过比较 Divide and Conquer 和 Dynamic Programming,我才发现之前的理解有点问题。 一切还是要从 Algorithmic Paradigm 说起: An algorithmic paradigm or algorithm design paradigm is a generic model or framework which underlies the design of a class of algorithms. An algorithmic paradigm is an abstraction higher than the notion of an algorithm, just as an algorithm is an abstraction higher than a computer program. 算法范式,是在算法的层面上抽象出来的一种更泛化的思想,常用的有: Brute-force search 暴力解法 Backtracking 回溯算法 Greedy algorithm 贪心算法 Divide and conquer 分治法 Dynamic programming 动态规划 Divide and Conquer 的基本思路是把复杂的问题分解成多个类似的简单问题,解决之后再组合起来得到最终结果。这种算法有很多应用,比如排序中的 Merge Sort,先将数列分解成单个元素,然后再归并,这时子数组都已经排好顺序了,所以过程很快。...

11-08 · 2 min