Google Coding Interview Question: Log Message Truncation by 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.

This problem asks you to fairly truncate a list of log messages by source file. The key idea is to count how many messages each source file emitted, then cap each source at X messages: keep only the first X messages for sources with more than X entries, and keep all messages for sources with X or fewer entries. A hash map for counting and a stable pass to rebuild the output are the main tools.