PreviousNext
AI-assisted engineering/Verifying AI output

Fix the reference model for a sharded cache

Review the AI's codeMedium15 minUber style

Your task

A coding agent added a sharded in-memory cache to a hot Go service: keys are split across shards, each with its own lock and least recently used (LRU) eviction. Its benchmark showed 3x the throughput. Before trusting that, your team replays real key traces through a reference model of the cache and compares the hits and misses.

An assistant wrote simulate_sharded_cache(keys, shard_count, shard_capacity). It is in the editor. It has a bug. Find it and fix it.

Input and output:

  • keys: the keys accessed, in order. Keys are ASCII.
  • shard_count: how many shards there are.
  • shard_capacity: the most keys one shard holds.
  • Return one boolean per access: true for a hit, false for a miss.

Rules the tests check:

  • If shard_count or shard_capacity is 0 or less, every access is a miss.
  • A key's shard is the sum of the character codes of all of its characters, modulo shard_count. Shards are independent: a key only competes for room in its own shard.
  • Each shard is an LRU cache. A hit, a key already in its shard, makes that key the most recently used.
  • A miss inserts the key as the most recently used. If the shard then holds more than shard_capacity keys, remove its least recently used key.

Examples

simulate_sharded_cache(keys: list[str], shard_count: int, shard_capacity: int) -> list[bool]
Example 1
Inputsimulate_sharded_cache(["a", "b", "a"], 2, 2)
Output[False, False, True]
Example 2
Inputsimulate_sharded_cache(["a", "b", "a", "c", "b"], 1, 2)
Output[False, False, True, False, False]
Example 3
Inputsimulate_sharded_cache(["ab", "ba", "cd", "dc", "ab"], 4, 2)
Output[False, False, False, False, False]