课程大纲 第 20 课,共 148 课 · 执着于你自己
执着于你自己

先靠自己:环绕的日志

为什么重要 这是一个完整的陷阱问题,在你写好自己的三种方法之前,导师会一直锁着。留意一下,除了问题本身什么都没有地开始,是一种什么样的感觉。

一台小设备把它的事件日志保存在一个环形缓冲区里:一个按时间顺序写入的固定大小的文件。当它写满时,写入会绕回到开头,覆盖掉最旧的条目。所以这个文件是有序的,但被旋转过:最新的条目后面跟着最旧的条目。从设备的闪存中读取很慢,而且每读取一个值都要计数。

客服人员会成批地问一些问题,比如“从 14:02 起有多少个事件?”,并且每一个都要一个答案。

数据

from creative.budget import Tape
tape = Tape([50, 61, 70, 12, 20, 33])  # written in order, wrapped after 70
queries = [20, 65]
# count_since(tape, queries) -> [5, 1]   (20, 33, 50, 61, 70) and (70)

用你的三种方法作为代码的开头:

my_approaches = ["...", "...", "..."]
轮到你了

先给 my_approaches 赋值:三种你自己的方法,每种至少四个单词(到时导师就会解锁;检查也需要它)。然后编写 count_since(tape, queries)。tape 是一个由互不相同的整数时间戳组成的 Tape,按递增顺序写入,并且可能在一个未知的位置绕回过一次(也可能根本没有绕回过)。它至少包含一个条目。对于 queries 中的每一个值 q,返回有多少个条目 >= q。预算:在 100,000 个条目和 100 个查询的情况下,你最多只能读取 20,000 个值。len(tape) 是免费的。

先有想法,再有提示:当 my_approaches 里有 3 个你自己的思路时,AI 导师才会解锁。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。