Longest-Prefix LRU Cache

Problem

Simulate an entry-count-limited prefix cache with operations ["put", id, tokens] and ["match", query_tokens]. Put inserts or replaces an ID and makes it most recently used; evict the least-recently-used entry if over capacity. At capacity zero, puts store nothing.

Match chooses the longest stored token list that is a prefix of the query; equal lengths choose the lexicographically smallest ID. A hit refreshes only the chosen entry, and a miss changes no recency. Empty prefixes are allowed. Return {"matches": chosen IDs or null for each match, "lru": live IDs from least to most recently used}. This model counts entries, not KV bytes.

def prefix_lru(capacity, operations):

Constraints

• 0 ≤ capacity ≤16; 0..64 operations; IDs are nonempty ASCII strings.
• Token lists contain 0..32 integers; replacing an ID can change its prefix.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  3,
  [
    [
      "put",
      "a",
      [
        1
      ]
    ],
    [
      "put",
      "b",
      [
        1,
        2
      ]
    ],
    [
      "match",
      [
        1,
        2,
        3
      ]
    ]
  ]
]
Expected result: {
  "matches": [
    "b"
  ],
  "lru": [
    "a",
    "b"
  ]
}

Arguments: [
  2,
  [
    [
      "put",
      "a",
      [
        1
      ]
    ],
    [
      "put",
      "b",
      [
        2
      ]
    ],
    [
      "match",
      [
        1,
        3
      ]
    ],
    [
      "put",
      "c",
      [
        3
      ]
    ]
  ]
]
Expected result: {
  "matches": [
    "a"
  ],
  "lru": [
    "a",
    "c"
  ]
}