Key-Value Store with QPS Calculation

Design a key-value store that supports put(key, value), get(key), and getQPS(windowSeconds) operations. put and get each count as one operation. getQPS(w) must return the average number of operations (puts + gets) per second over the last w seconds. All operations arrive with an integer timestamp (seconds since epoch); the same timestamp may be given to multiple operations and they are not necessarily in chronological order. You may assume the system has a single thread of execution and the current time is the maximum timestamp seen so far. Implement the three methods efficiently so that each runs in O(1) average time and the store uses O(N) space where N is the total number of operations whose timestamps fall inside any active query window.