Google OA 面试真题解析：按 source file 截断日志消息

You are given a list of log messages, each associated with some source file which emitted them.

struct LogMessage {
    string source_file;
    string message;
};

Your goal is to truncate the list down to size max_log_messages. That is, you want to return a subset of the original list. However, you want to perform the truncation in a fair way.

For the sake of this problem, our "fair" truncation algorithm is as follows:

Let X be the max log messages maintained per source file.

• If the source file has emitted more than X messages, truncate the log messages for that source file to X messages.
• If the source file has emitted X or fewer messages, do not truncate the log messages for that source file.

这道题考察的是对日志流按做“公平截断”。核心思路通常是先统计每个 source file 的消息数量，再根据总配额和每个来源的上限 X 做筛选：对于消息数超过 X 的来源，只保留 X 条；少于等于 X 的来源则全部保留。实现时常用哈希表记录每个 source 的计数，再按原顺序或要求的输出顺序重建结果，因此重点在于计数、分组和稳定地保留指定数量的日志。