Compact Conversation History by Token Budget
Sierra● EasyNEW GRADPHONE SCREENProblem statement
You are given an ordered conversation history messages, a parallel array tokenCounts, and a non-negative context budget tokenBudget. The value tokenCounts[i] is the token cost of messages[i].
If the total token cost exceeds the budget, remove whole messages from the beginning until the retained total is at most tokenBudget.
Return the longest suffix of messages that fits. Preserve the original order of every retained message. A total exactly equal to the budget fits.
Function
compactConversationHistory(messages: String[], tokenCounts: int[], tokenBudget: int) → String[]Examples
Example 1
messages = ["system","user","assistant"]tokenCounts = [4,5,6]tokenBudget = 10return = ["assistant"]The total is 15. Removing "system" leaves 11, so "user" must also be removed. The remaining cost is 6.
Example 2
messages = ["a","b","c"]tokenCounts = [2,3,5]tokenBudget = 8return = ["b","c"]Removing the oldest message lowers the total from 10 to exactly 8, so both remaining messages are retained.
Example 3
messages = ["oversized"]tokenCounts = [12]tokenBudget = 0return = []The only message exceeds a zero budget, so the compacted history is empty.
Constraints
0 <= messages.length <= 10^5tokenCounts.length == messages.length- Every entry in
messagesis a non-empty ASCII string. 0 <= tokenCounts[i] <= 10^90 <= tokenBudget <= 10^9