Solve Throughput, Rate Limiting, and LFU

Problem Statement

You are tasked with building a high-performance request handling component for a web service. The component must support three primary operations:

1. LFU Cache (Least Frequently Used): Design a cache that stores key-value pairs. When the cache reaches capacity, it must evict the entry with the lowest frequency. If there is a tie, evict the least recently used entry among those with the same frequency. All operations (get and put) must run in O(1) time.
2. Fixed Window Rate Limiting: Implement a method that determines if a specific user ID is allowed to make a request, given a limit of N requests per T seconds.
3. Throughput Calculation: Given a log of request timestamps as an array of integers, calculate the maximum number of requests processed in any rolling window of size W milliseconds.

Implementation Signature

class RequestManager:
    def __init__(self, capacity: int, limit: int, window_size: int):
        # capacity: for LFU cache
        # limit: max requests per window
        # window_size: duration for rate limiting and throughput analysis
        pass

    def get_cache(self, key: int) -> int: ...
    def put_cache(self, key: int, value: int) -> None: ...
    def is_allowed(self, user_id: int, current_time: int) -> bool: ...
    def max_throughput(self, timestamps: list[int]) -> int: ...

Constraints

• capacity, limit, window_size are positive integers up to 10^5.
• timestamps is sorted in non-decreasing order.

Example

• LFU: If capacity is 2, put(1,1), put(2,2), get(1), put(3,3), key 2 should be evicted because it was used 0 times (or less than 1).
• Throughput: timestamps = [100, 200, 300, 500, 600], window_size = 250. The window [300, 550] contains 2 requests, but [100, 300] contains 3. Max is 3.