Presale Search Cap
When concert presale opens, fans hammer the seat search, and a few scripts refresh it hundreds of times a minute. The ticket site caps each fan at a few searches per clock minute: the counter for 10:04 starts at zero at 10:04:00 and is thrown away at 10:05:00. Over the cap, the fan gets an HTTP 429 "Too Many Requests" instead of results.
This is the fixed-window counter from Rate Limiting: one small counter per user per window, cheap enough to keep for millions of users in a shared in-memory store. Its known flaw shows up at the window edge, which the examples below make visible.
Your task
Write a class WindowLimiter:
constructor(limit, windowSec): each fan may make at mostlimitallowed requests per window.allow(fan, t): a request fromfanat timet(whole seconds). Returntrueif it is allowed,falseif it is rejected.
Windows are fixed and aligned to 0: a request at time t falls in window number floor(t / windowSec), so with windowSec = 60 the windows are [0, 59], [60, 119], and so on. A request is allowed if the fan has had fewer than limit allowed requests in the same window. Rejected requests do not count. Each fan has separate counts.
class WindowLimiter
Examples
new WindowLimiter(3, 60)
.allow("ana", 10)
.allow("ana", 20)
.allow("ana", 30)
.allow("ana", 59)
.allow("ana", 60)[null, true, true, true, false, true]
Times 10, 20, 30 and 59 are all in window 0 (0 to 59). The first three are allowed, which uses up the limit of 3, so the request at 59 is rejected. Time 60 starts window 1 with a fresh count, so it is allowed.
new WindowLimiter(2, 60)
.allow("ben", 58)
.allow("ben", 59)
.allow("cy", 59)
.allow("ben", 60)
.allow("ben", 61)[null, true, true, true, true, true]
Ben gets 2 requests at 58 and 59 in window 0, then 2 more at 60 and 61 in window 1: 4 requests in 4 seconds, although the limit is 2 per minute. That burst at the edge is the price of fixed windows. Cy has her own count, so her request at 59 is allowed even though Ben used up his.
Constraints
- 1 ≤ limit ≤ 1,000
- 1 ≤ windowSec ≤ 86,400
- 0 ≤ t ≤ 1,000,000,000, and t never decreases from one call to the next
- fan is a non-empty string of up to 20 letters and digits
- At most 2,000 calls per test
Start with brute force
Store every allowed request time for each fan, and on each new request count how many stored times fall in the same window. With 2,000 calls that is up to 2,000 × 2,000 = 4 million checks, and the stored history grows forever.
Since only the current window can matter, a single counter per fan is enough, and both time and memory per fan become constant.
Hints
0 of 4 shown- Hint 1
For one fan, which earlier requests can affect whether the request at time
tis allowed? Do requests from an earlier window matter at all? - Hint 2
Only the current window matters. So for each fan you need just two numbers: which window you are counting, and how many allowed requests are in it.
- Hint 3
Keep a hash map from fan to
[window, count]. When a request arrives in a different window than the stored one, the old count is useless: reset it to 0 for the new window. - Hint 4
Compute
w = floor(t / windowSec). If the fan's stored window is notw, store[w, 0]. Then if the count is below the limit, add 1 and return true; otherwise return false without counting.
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
Only the current window decides anything, so keep one counter per fan, tagged with the window it belongs to. A request in a new window resets the counter.
Trace the first example, limit 3, window 60:
- t = 10: window 0. Ana has nothing stored, so start
[0, 0]. 0 < 3: count 1, allowed. - t = 20 and t = 30: still window 0. Counts 2 and 3, both allowed.
- t = 59: window 0, count 3 is not below 3. Rejected, and the count stays 3.
- t = 60: window 1 differs from the stored 0, so reset to
[1, 0]. Count 1, allowed.
The second example shows the weakness: two windows meet at t = 60, so a fan can fit two full windows of requests into a few seconds. If that burst matters, use a sliding window, as in Password Reset Throttle.
class WindowLimiter {
constructor(limit, windowSec) {
this.limit = limit;
this.windowSec = windowSec;
this.counts = new Map(); // fan -> { window, count }
}
allow(fan, t) {
const w = Math.floor(t / this.windowSec);
let c = this.counts.get(fan);
if (!c || c.window !== w) {
c = { window: w, count: 0 }; // a new window starts from zero
this.counts.set(fan, c);
}
if (c.count >= this.limit) return false; // rejected: not counted
c.count++;
return true;
}
}class WindowLimiter:
def __init__(self, limit, window_sec):
self.limit = limit
self.window_sec = window_sec
self.counts = {} # fan -> [window, count]
def allow(self, fan, t):
w = t // self.window_sec
c = self.counts.get(fan)
if c is None or c[0] != w:
c = [w, 0] # a new window starts from zero
self.counts[fan] = c
if c[1] >= self.limit:
return False # rejected: not counted
c[1] += 1
return TrueRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.