Repeated N-Gram Blocking

Problem

Return the sorted unique token IDs that would create a previously seen n-gram if appended to history. Match the last n−1 tokens against prefixes of complete n-grams already in history.

For n=1, every previously seen token is blocked. If history is too short to supply either a matching suffix or a previous full n-gram, return [].

def blocked_ngram_tokens(history, n):

Constraints

• history contains 0..64 nonnegative integer token IDs; 1 ≤ n ≤ 16.
• Overlapping n-grams count; return IDs in ascending numeric order.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  [
    1,
    2,
    1
  ],
  2
]
Expected result: [
  2
]

Arguments: [
  [
    3,
    1,
    3
  ],
  1
]
Expected result: [
  1,
  3
]