Fair Truncation of a Message Log
Updated
Problem statement
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
kmessages, 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