最近我们接触到一道 Decagon 的 Coding Interview 真题。题目围绕客户满意度评分（CSAT）展开，要求候选人实现一个支持时间窗口的评分追踪系统。

这道题的业务背景并不复杂，甚至第一眼看起来只需要一个队列就能解决。但随着面试推进，面试官逐步加入了评分更新、过期数据清理，以及百分位数计算等要求。特别是最后一部分，明确提出不能依赖排序来优化查询。

这也是这道题值得关注的地方：它考察的不只是候选人能否写出正确代码，更重要的是能否在不断变化的需求下，保持数据结构与业务逻辑的一致性。

本次面试题目分为三个部分，围绕一个 CSAT Tracker 逐步扩展功能。

Part 1: Basic CSAT Tracker

Original Question:

• Implement record(conversation_id, score, timestamp) to store CSAT scores (1–5).
• Implement get_average(current_time) to calculate the average score within a rolling time window.
• Remove expired records and return None if the window is empty.

中文题意：

实现一个客户满意度评分系统，支持记录评分，并计算最近一段时间内的平均分。过期记录需要被清理，如果窗口内没有有效数据，则返回 None。

第一部分主要考察滑动时间窗口（Sliding Window）。

最直接的实现方式是使用队列保存记录，在查询平均分时，先删除已经超过时间窗口的记录，再计算剩余评分的平均值。

不过，如果每次查询都重新遍历整个队列求和，随着记录数量增加，查询效率就会下降。

更好的方式是维护一个运行中的评分总和（Running Sum）。新增记录时增加总和，记录过期时扣除对应评分，这样在完成过期清理后，平均值就可以在 O(1) 时间内计算出来。

这里面试官可能进一步关注时间戳是否按顺序到达、窗口边界是否包含某个时间点，以及系统如何处理空窗口。

这些细节虽然没有复杂算法，却很容易影响最终实现的正确性。

Part 2: Updating Scores

Original Question:

• Implement update(conversation_id, score) to modify an existing conversation's score.
• Only update records still within the active window.
• Ignore expired or nonexistent records.
• Preserve the original timestamp and record order.

中文题意：

支持修改已有会话的评分，但只能修改仍在有效时间窗口内的记录。过期或不存在的记录直接忽略，并且更新后必须保持原来的时间戳与记录顺序。

第二部分开始增加难度。

如果只使用队列，系统虽然可以高效删除过期记录，但要找到某个 conversation_id 对应的记录，就可能需要 O(N) 的遍历。

因此，一个常见的优化方向是结合 Hash Map 和队列：

队列负责维护时间顺序，Hash Map 负责根据 conversation_id 快速定位记录。

但新的问题随之出现。

当某条评分被修改时，除了更新记录中的 score，还必须同步调整此前维护的 Running Sum。否则，系统虽然保存了新的评分，平均值却仍然是旧的。

另外，记录过期并被删除时，也需要同步清理 Hash Map 中的索引，避免后续更新操作错误地访问已经失效的数据。

这一部分真正考察的是：当系统同时维护多种数据结构时，候选人能否保证它们始终保持一致。

有一个容易忽略的细节：题目要求保留原始时间戳和记录顺序。这意味着不能简单地删除旧记录、再把更新后的记录插入队尾，否则就可能改变其过期时间。

Part 3: Percentile Calculation

Original Question:

• Implement get_percentile(now, p) to calculate the p-th percentile of active scores.
• Use the nearest-rank method: rank = ceil(p × N / 100).
• Remove expired records before calculating.
• Return None if the window is empty.
• Optimize percentile calculation without sorting.

中文题意：

实现百分位数查询，使用 Nearest-Rank 方法计算当前有效评分的第 p 百分位数。查询前需要清理过期记录，窗口为空时返回 None，并要求优化计算过程，避免每次排序。

第三部分是整道题最有意思的地方。

最直接的方案是提取窗口内所有有效评分，对其排序，然后按照公式找到对应排名。

假设当前评分为：

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

如果查询第 50 百分位数：

rank = ceil(50 × 7 / 100) = 4

因此结果为第 4 个分数，也就是 4。

这个方案完全正确，但每次查询排序的时间复杂度为 O(N log N)。

而面试官明确要求优化，并且不能依赖排序。

解决这个问题的关键，在于题目中的一个业务限制：

CSAT 评分只有 1 到 5 分。

既然评分的取值范围固定，就没有必要保存一个用于百分位查询的完整有序列表。

可以使用长度为 5 的频率数组，分别记录当前窗口内每个分数出现的次数。

例如：

计算百分位数时，只需要按照评分从低到高累加频率，找到累计数量首次达到目标 rank 的分数。

由于一共只有 5 种评分，整个查询过程最多检查 5 个计数器。

因此，在完成过期记录清理后，百分位数计算的时间复杂度可以视为 O(1)。

当然，引入频率数组之后，系统又多了一份需要维护的状态。

新增记录时需要增加相应评分的频率，修改评分时需要减少旧评分的频率并增加新评分的频率，记录过期时也需要减少对应计数。

这与第二部分的 Running Sum 本质上是同一个问题：如何保证所有辅助数据结构在每次操作后都是正确的。

从三个部分可以看出，Decagon 并没有要求候选人使用特别冷门的算法。

队列、Hash Map、Sliding Window 和 Frequency Counting 都属于常见知识点。

但如果把题目看成一个完整系统，就会发现每增加一个需求，都会影响此前的设计。

第一部分只需要维护时间窗口和评分总和；第二部分要求快速定位指定记录；第三部分又要求快速查询评分分布。

最终，一个比较合理的方案是：

• 使用队列维护记录的时间顺序。
• 使用 Hash Map 支持快速查找和更新。
• 使用 Running Sum 高效计算平均值。
• 使用 Frequency Array 高效计算百分位数。

在时间戳按顺序到达、会话 ID 唯一等常见假设下，新增和更新操作可以做到 O(1)，每条记录的过期清理也只需要处理一次。百分位数计算本身同样是 O(1)。

不过，面试中还需要明确一些题目没有完全定义的行为，例如重复的 conversation_id 如何处理、更新操作以什么时间为准判断是否过期、百分位参数的有效范围是什么。

这些边界条件如果没有和面试官确认，即使选择了正确的数据结构，也可能出现实现与测试预期不一致的情况。

我们提供北美科技公司技术面试辅助服务，覆盖 Coding Interview、算法题分析、系统设计等常见面试场景，帮助候选人在准备过程中理解真实面试题型、梳理解题思路、识别容易遗漏的边界条件，并通过针对性训练提升英文技术沟通和现场解题能力。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~