Rate Limiter (Sliding Window)
Problem
A user may send at most k requests in any window of w seconds. The first line is k and w. Every next line is REQ time user (times never go down). A request at time t is allowed if the user has fewer than k allowed requests with time greater than t - w (that is, in the last w seconds including t). Print allow or deny for each request. Denied requests are not counted.
Constraints
- 1 <= k <= 100
- 1 <= w <= 10^6
- 1 <= requests <= 10^4
Examples
Input
2 10 REQ 1 a REQ 2 a REQ 3 a REQ 11 a
Output
allow allow deny allow
Solutions
Because time never goes backwards, old requests can be removed from the front of a queue. The queue then always holds exactly the requests inside the window, so its size tells whether there is room. O(1) amortised per request.
/*
* Problem : Process lines.
* Input : Several command lines.
* Output : allow or deny for each request.
* Approach: Queue per user.
* Time : O(n)
* Space : O(allowed requests in window)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
// Step 1: Read the limits. Every user has a queue of the times of the allowed requests inside the current window.
String[] limits = lines[0].split(" ");
int k = Integer.parseInt(limits[0]);
long w = Long.parseLong(limits[1]);
java.util.Map<String, java.util.ArrayDeque<Long>> windows = new java.util.HashMap<String, java.util.ArrayDeque<Long>>();
String[] output = new String[lines.length - 1];
for (int i = 1; i < lines.length; i++) {
String[] part = lines[i].split(" ");
long t = Long.parseLong(part[1]);
java.util.ArrayDeque<Long> queue = windows.computeIfAbsent(part[2], key -> new java.util.ArrayDeque<Long>());
// Step 2: Times are not going down, so old requests are at the front. Remove those that left the window.
while (!queue.isEmpty() && queue.peekFirst() <= t - w) {
queue.pollFirst();
}
// Step 3: Allow if there is room. Only allowed requests are remembered.
if (queue.size() < k) {
queue.addLast(t);
output[i - 1] = "allow";
} else {
output[i - 1] = "deny";
}
}
return output;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (2)
- Why is a queue enough?
- Why are denied requests not stored?