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.