Design O(1) cache and moving average

## Problem You are asked two coding questions: ### 1) O(1) cache data structure Design a data structure that supports the following operations in **O(1)** average time: - `get(key) -> value` (return a sentinel such as `-1`/`null` if missing) - `put(key, value)` Assume the cache has a fixed capacity `C`. When inserting a new key and the cache is full, it must evict one existing entry according to a well-defined policy (state the policy you choose, e.g., least-recently-used). ### 2) Moving window average Implement a structure that receives a stream of numbers and returns the average of the **last K values** each time a new value arrives: - initialize with window size `K` - `next(x) -> average_of_last_up_to_K_values` If fewer than `K` values have been seen, average over all values so far. ## Constraints - Aim for O(1) per operation time. - Use standard in-memory data structures.