FastPrep
Problem · Queue

Dynamic Batch Decode Trace

Learn this problem
● HardxAI logoxAIFULLTIMEONSITE INTERVIEW

Problem statement

There are requests 0..scriptedTokens.length-1 waiting in order. For request r, scriptedTokens[r] lists the successive next tokens returned by the simulated model.

  1. Create batchSize numbered slots and initially fill the lowest slots with the earliest requests.
  2. Each model round consumes one next token for every occupied slot, in ascending slot order. Add r:token to that round's trace.
  3. A request completes after consuming stopToken or its maxTokens-th token.
  4. Only after the entire round completes, free completed slots and refill the lowest free slots with waiting requests in increasing request-ID order.

Return one trace row per model round. A final round may contain fewer than batchSize entries.

Function

dynamicBatchTrace(scriptedTokens: String[][], batchSize: int, maxTokens: int, stopToken: String) → String[][]

Examples

Example 1

scriptedTokens = [["a","b","<STOP>"],["x","<STOP>"],["m","n","o","p"],["q","<STOP>"]]batchSize = 2maxTokens = 3stopToken = "<STOP>"return = [["0:a","1:x"],["0:b","1:<STOP>"],["0:<STOP>","2:m"],["3:q","2:n"],["3:<STOP>","2:o"]]

Request 1 frees slot 1 after round 2, so request 2 enters there. Request 0 then frees slot 0, which request 3 takes. Request 2 finishes by reaching three consumed tokens.

Example 2

scriptedTokens = [["a","b"],["x","y"]]batchSize = 4maxTokens = 2stopToken = "!"return = [["0:a","1:x"],["0:b","1:y"]]

The batch is never full because only two requests exist. Both finish together at maxTokens = 2.

Constraints

  • 1 <= scriptedTokens.length <= 100000.
  • 1 <= batchSize <= 1000.
  • 1 <= maxTokens <= 1000.
  • Each request contains a stop token within its first maxTokens entries or contains at least maxTokens entries.
  • Tokens are non-empty ASCII strings and contain no :.
  • The total number of consumed tokens is at most 1000000.

More xAI problems

drafts saved locally
public String[][] dynamicBatchTrace(
        String[][] scriptedTokens, int batchSize, int maxTokens, String stopToken) {
    // Write your code here.
}
scriptedTokens[["a","b","<STOP>"],["x","<STOP>"],["m","n","o","p"],["q","<STOP>"]]
batchSize2
maxTokens3
stopToken"<STOP>"
expected[["0:a", "1:x", "0:b", "1:<STOP>", "0:<STOP>", "2:m", "3:q", "2:n", "3:<STOP>", "2:o"]]
checking account