Design O(1) cache and moving average

Problem Statement

You are tasked with building a StreamProcessor class that performs two distinct operations on a stream of integer values:

1. LRU Cache: Store up to capacity key-value pairs. If the cache reaches capacity, evict the least recently used item. The put(key, value) and get(key) methods must both execute in O(1) time.
2. Moving Average: Maintain a sliding window of the last k values added to the system. Provide a getMovingAverage() method that returns the current average of these k values in O(1) time.

Implementation Signature

class StreamProcessor:
    def __init__(self, capacity: int, k: int):
        # Initialize cache with capacity and moving average window size k
        pass

    def put(self, key: int, value: int) -> None:
        # Update/insert the key-value pair and include value in the moving average
        pass

    def get(self, key: int) -> int:
        # Return the value for the key, or -1 if not found
        pass

    def getMovingAverage(self) -> float:
        # Return the average of the last k values added (global stream)
        pass

Constraints

• capacity and k are positive integers.
• put is called frequently; get and getMovingAverage must be highly performant.
• The moving average should include all values passed to put, even if the key is already in the cache.

Examples

Example 1 Input: processor = StreamProcessor(2, 3)

• put(1, 10) -> Average window: [10], Avg: 10.0
• put(2, 20) -> Average window: [10, 20], Avg: 15.0
• put(3, 30) -> Average window: [10, 20, 30], Avg: 20.0
• put(4, 40) -> Average window: [20, 30, 40], Avg: 30.0 (Key 1 evicted)

Edge Cases

• Accessing a key that does not exist.
• Calling getMovingAverage before k elements have been added.
• Consecutive put calls with the same key.