OA: Throttle requests per client

An API gateway has to stop any one client from flooding the servers. Over four levels you'll build RequestThrottle, which decides for each incoming request whether to let it through.

Every method takes a timestamp first: an integer number of seconds, 0 <= timestamp <= 10^9. Across all calls, timestamps never decrease, and several calls can share a timestamp. Client names are non-empty strings.

• RequestThrottle(limit, window): the default rule, with limit >= 1 and window >= 1. Time is cut into back-to-back windows [0, window), [window, 2·window), and so on. Each client may have at most limit requests let through in each window.
• allow(timestamp, client) -> bool: a request from client arrives. Return True and count it if the client still has room in the current window; otherwise return False.

Clients are counted separately, and a refused request does not count towards anything.

rt = RequestThrottle(2, 10)     # 2 requests per client in each 10-second window
rt.allow(1, "alice")    # True
rt.allow(5, "alice")    # True
rt.allow(9, "alice")    # False  (window [0, 10) is used up)
rt.allow(9, "bob")      # True   (bob has his own count)
rt.allow(10, "alice")   # True   (a new window, [10, 20), has started)
rt.allow(19, "alice")   # True
rt.allow(20, "alice")   # True

Expect up to 200,000 calls and many clients; each call should take O(1) time.