# Review AI-Generated LRU and LFU Cache Changes You are modifying an existing codebase with an AI coding assistant. Add an LRU cache and an LFU cache, create tests, and measure their performance. Explain how you will direct the assistant, inspect its changes, catch semantic errors, and decide whether the implementation is ready rather than accepting generated code on appearance. ### Constraints & Assumptions - Both caches have a fixed positive capacity. - `get` returns a stored value or a defined miss result; `put` inserts or updates. - LRU evicts the least recently used key. - LFU evicts the least frequently used key, breaking equal-frequency ties by least recent use. - Expected average time for `get` and `put` is `O(1)`. ### Clarifying Questions to Ask - What are the existing repository interfaces and error conventions? - Does updating an existing key count as access for each policy? - Which concurrency guarantees are required? - What workload should the performance measurement represent? ### Part 1 - Plan and AI collaboration Describe how you would decompose the task, give the assistant bounded context, and require it to explain affected invariants before editing. #### What This Part Should Cover - Repository inspection before prompting - Small reviewable diffs and explicit interfaces - Human ownership of policy decisions - Refusal to expose secrets or unrelated files ### Part 2 - Correctness review and tests State the data-structure invariants and build tests that distinguish LRU from LFU, exercise tie-breaking, updates, capacity pressure, and edge cases. #### What This Part Should Cover - Hash lookup plus recency/frequency bookkeeping - Deterministic LFU tie-breaking - Property, regression, and interface tests - Review for stale links, counters, and accidental complexity ### Part 3 - Performance measurement Design a benchmark that compares policies without mistaking warmup, allocation, or unrealistic key distributions for algorithmic improvement. #### What This Part Should Cover - Reproducible workloads and seeds - Hit ratio, throughput, latency percentiles, and memory - Warmup and repeated trials - Correctness checks during benchmark runs ```hint Ask for invariants before code Generated code is easier to review when the assistant first states which map, list, frequency bucket, and tie-breaking invariants every operation must preserve. ``` ### What a Strong Answer Covers - A controlled AI-assisted workflow with small diffs and explicit human review - Correct LRU and LFU invariants, including update and tie behavior - Tests designed to expose plausible generated-code defects - A fair benchmark tied to workload goals rather than one headline number ### Follow-up Questions 1. Which LFU bug can pass simple examples but fail after a key's frequency bucket becomes empty? 2. How would thread safety alter the data structures and benchmark? 3. What evidence would make you reject an apparently faster generated implementation?