High-Performance QPS Counter with Sliding Time Window

databricks Design a system to calculate QPS (queries per second). Functional Requirements hit(): Record a request, initializing a timestamp. getHits(timestamp): Return the number of requests in the past 5 minutes (including the past 5 minutes from the given timestamp). Data Scale Timestamps are incrementing integers, potentially reaching a range of 10^9. Number of requests could be thousands per second. Ensure performance such that the time complexity is less than O(n) in the worst case. Example Input 0