Startup OA 面试真题解析：CSAT Tracker with Rolling Average, Updates, and Percentiles

CSAT Tracker with Rolling Average, Updates, and Percentiles

Implement record(conversation_id, score, timestamp) to store CSAT scores from 1 to 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.

Part 2: Updating Scores

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.

Part 3: Percentile Calculation

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.

这道题要求设计一个支持滚动时间窗口的 CSAT 评分管理器：先实现按 conversation_id、score、timestamp 记录评分，再在查询时自动剔除过期记录，计算当前窗口内的平均值；随后还要支持只更新仍在有效窗口内的历史记录，并保持原始时间戳和记录顺序不变；最后实现百分位数查询，按 nearest-rank 规则计算第 p 百分位，同时要求在不排序的前提下高效维护活跃分数。整体考察的是哈希表、时间窗口清理、动态维护统计量，以及对数据结构和查询效率的综合设计能力。