Password Reset Throttle
A bank's "forgot password" button sends an email with a reset link. Attackers use it to flood someone's inbox, so each email address gets at most 3 reset emails in any rolling hour. "Any rolling hour" is strict: unlike a per-clock-hour counter, nobody can send 3 emails at 9:59 and 3 more at 10:00. When the button is blocked, the page says how long to wait.
This is the sliding-window log from Rate Limiting: it stores the time of every allowed request in the window, which costs more memory than a counter but is exact. It suits low limits on sensitive actions such as logins, sign-ups and reset emails, and the wait time becomes the Retry-After header of an HTTP 429 response.
Your task
Write a class ResetThrottle:
constructor(limit, windowSec).request(email, t): a reset request at timet(whole seconds). Returntrueand record it if the address has had fewer thanlimitallowed requests in the window; otherwise returnfalseand record nothing.waitTime(email, t): return how many seconds fromtuntil a request for this address would be allowed. Return 0 if one would be allowed att. This does not record a request.
The window at time t covers the times greater than t − windowSec and up to t. So a request made at time s stops counting at exactly s + windowSec. Each address is limited separately.
class ResetThrottle
Examples
new ResetThrottle(3, 3600)
.request("kai@mail.test", 0)
.request("kai@mail.test", 600)
.request("kai@mail.test", 1200)
.request("kai@mail.test", 1800)
.waitTime("kai@mail.test", 1800)
.request("kai@mail.test", 3599)
.request("kai@mail.test", 3600)
.waitTime("kai@mail.test", 3600)[null, true, true, true, false, 1800, false, true, 600]
Requests at 0, 600 and 1,200 fill the limit of 3. At 1,800 the request is refused, and the oldest one (at 0) stops counting at 0 + 3,600 = 3,600, so the wait is 3,600 − 1,800 = 1,800 seconds. At 3,599 it still counts. At 3,600 it has left the window, so the request is allowed. Now the window holds 600, 1,200 and 3,600, and the next slot opens when 600 leaves at 4,200: a wait of 600.
new ResetThrottle(2, 60)
.request("mo@mail.test", 58)
.request("mo@mail.test", 59)
.request("mo@mail.test", 60)
.request("mo@mail.test", 61)
.request("li@mail.test", 61)[null, true, true, false, false, true]
A fixed per-minute counter would reset at 60 and allow 4 requests between 58 and 61. Here the window at 60 still contains 58 and 59, so 60 and 61 are refused; the limit of 2 holds in every 60-second span. Another address has its own log.
Constraints
- 1 ≤ limit ≤ 1,000
- 1 ≤ windowSec ≤ 1,000,000
- 0 ≤ t ≤ 1,000,000,000, and t never decreases from one call to the next
- email is a non-empty string of up to 40 characters
- At most 3,000 calls per test
Start with brute force
Store every allowed request forever and, on each call, count the stored times inside the window. With 3,000 calls that is up to about 4.5 million comparisons, and the memory grows with the whole history.
Expired times can never count again, so dropping them from the front of a queue keeps at most limit times per address and makes each call cost O(1) on average.
Hints
0 of 4 shown- Hint 1
At time
t, which of an address's past requests still matter? Once a request is too old for the window att, can it ever matter again, given that time only moves forward? - Hint 2
Old requests leave the window in the order they were made. That is exactly what a queue does: new times join at the back, expired times leave from the front.
- Hint 3
Keep a queue of allowed request times per address. On every call, first drop times
sfrom the front whiles ≤ t − windowSec. Then the queue length is the number of requests in the window. - Hint 4
The queue never holds more than
limittimes, because a request is only recorded when there is room. So when it is full, the slot that frees up first is the one at the front: the wait isfront + windowSec − t.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Keep one queue of allowed request times per address. Every call first throws away the times that have left the window, then the queue length is the count inside it.
Trace the first example, limit 3, window 3,600:
- 0, 600, 1,200: the queue grows to
[0, 600, 1200], all allowed. - 1,800: nothing is ≤ 1,800 − 3,600, so nothing leaves. 3 in the window: refused.
waitTimeis 0 + 3,600 − 1,800 = 1,800. - 3,599: is 0 ≤ −1? No, so 0 stays. Still full: refused.
- 3,600: 0 ≤ 0, so 0 leaves. Two in the window: allowed, queue
[600, 1200, 3600]. waitTimeat 3,600: full again, front is 600, so 600 + 3,600 − 3,600 = 600.
The price of exactness is memory: one timestamp per allowed request, up to limit per address, where a counter needs one number. That is why the log is used for small limits such as 3 an hour, and a token bucket or a sliding-window counter for limits like 1,000 a minute.
class ResetThrottle {
constructor(limit, windowSec) {
this.limit = limit;
this.windowSec = windowSec;
this.logs = new Map(); // email -> allowed request times, oldest first
}
window(email, t) {
if (!this.logs.has(email)) this.logs.set(email, []);
const log = this.logs.get(email);
// drop times that are no longer inside (t - windowSec, t]
while (log.length && log[0] <= t - this.windowSec) log.shift();
return log;
}
request(email, t) {
const log = this.window(email, t);
if (log.length >= this.limit) return false; // full: not recorded
log.push(t);
return true;
}
waitTime(email, t) {
const log = this.window(email, t);
if (log.length < this.limit) return 0;
return log[0] + this.windowSec - t; // the oldest leaves first
}
}from collections import deque
class ResetThrottle:
def __init__(self, limit, window_sec):
self.limit = limit
self.window_sec = window_sec
self.logs = {} # email -> deque of allowed request times, oldest first
def _window(self, email, t):
log = self.logs.setdefault(email, deque())
# drop times that are no longer inside (t - window_sec, t]
while log and log[0] <= t - self.window_sec:
log.popleft()
return log
def request(self, email, t):
log = self._window(email, t)
if len(log) >= self.limit: # full: not recorded
return False
log.append(t)
return True
def wait_time(self, email, t):
log = self._window(email, t)
if len(log) < self.limit:
return 0
return log[0] + self.window_sec - t # the oldest leaves firstshift moves the rest of the array, but the queue never holds more than limit times; a deque avoids even that.)Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.