FastPrepFair Truncation of a Message Log
Problems/Fair Truncation of a Message Log

Fair Truncation of a Message Log

Google logoGoogle● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A phone screen report describes a log of messages, each tagged with a category such as A, B, or C. The task was to cut the log down to at most K messages and be fair to every category. When asked what fair means, the interviewer said one shared limit for every category, not a share in proportion to its size. The report also covered three edge cases: an empty log, K = 0, and K larger than the log. Its two examples used K = 9, and the first two examples here use the same tag order.

The report does not say which messages of a category to keep or what to return. Here, each category keeps its earliest messages, and you return the kept positions in log order. Slots can stay empty when raising the shared limit by one would go over K. The size limits are our choice.

Our version is about 85% the same as the reported question.

You are given a message log as an array categories, where categories[i] is the category of the message at position i, for example the sender that wrote it. Cut the log down to at most k messages while treating every category the same way.

To do this, pick one cap: the most messages any single category may keep.

  • Each category keeps its earliest messages, up to the cap. A category with fewer messages than the cap keeps all of them.
  • Use the largest cap for which the total number of kept messages is at most k.
  • If the whole log has at most k messages, every message is kept.

Return the 0-based positions of the kept messages in increasing order.

Some of the k slots can stay empty. The same cap applies to every category, so no category may keep more messages than the cap, even when there is room left.

Function

truncateLog(categories: String[], k: int) → int[]

Examples

Example 1

categories = ["A","B","A","A","B","B","C","C","A","C","B","A","C","C","B"]k = 9return = [0,1,2,3,4,5,6,7,9]

A, B and C each have 5 messages. A cap of 3 keeps 3 + 3 + 3 = 9 messages, which fits. A cap of 4 would keep 12, which is too many. So each category keeps its first 3 messages: A at positions 0, 2 and 3, B at 1, 4 and 5, and C at 6, 7 and 9.

Example 2

categories = ["A","B","A","A","B","B","A","C","B","A","B"]k = 9return = [0,1,2,3,4,5,6,7,8]

A and B have 5 messages each, and C has 1. A cap of 4 keeps 4 + 4 + 1 = 9 messages. A cap of 5 would keep 11. So A keeps positions 0, 2, 3 and 6, B keeps 1, 4, 5 and 8, and C keeps its only message at 7.

Example 3

categories = ["X","Y","X","Y","X","Y","Z"]k = 6return = [0,1,2,3,6]

X and Y have 3 messages each, and Z has 1. A cap of 2 keeps 2 + 2 + 1 = 5 messages. A cap of 3 would keep 7, which is more than 6. So the cap is 2 and only 5 messages are kept. The sixth slot stays empty, because no category may go over the shared cap.

Example 4

categories = ["P","Q","R","S"]k = 3return = []

Each of the 4 categories has one message. A cap of 1 would keep all 4 messages, which is more than 3. So the cap is 0 and no message is kept.

Constraints

  • 0 <= categories.length <= 1000
  • Each categories[i] has 1 to 10 uppercase English letters.
  • 0 <= k <= 10^9

More Google Phone Screen questions

  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
  • Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • All Index Pairs Sum to KJP Morgan Chase · PHONE SCREENJP Morgan Chase interview questions
  • Versioned ArrayTrueFoundry · PHONE SCREEN
  • HTTP Log QueriesDatadog · PHONE SCREEN · ONSITE INTERVIEWDatadog interview questions
  • Future-Effective Employee SalaryRippling · ONSITE INTERVIEWRippling interview questions
  • Insert Delete GetRandom O(1)Charta Health · PHONE SCREENCharta Health interview questions
  • Longest Consecutive SequenceKotak Mahindra Bank · PHONE SCREENKotak Mahindra Bank interview questions
  • Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
  • Longest Increasing SubsequenceByteDance · PHONE SCREENByteDance interview questions
  • Propagating Fraud DetectorAffirm · PHONE SCREEN · ONSITE INTERVIEWAffirm interview questions
  • Top K Frequent Elements with a Recency TiebreakSwiggy · PHONE SCREEN

Interview reports that mention this question

  • Google SWE III ML Loops in India: 10 Experiences (Part 2 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int[] truncateLog(String[] categories, int k) {
        // Write your code here.
    }
}
Checking account…