Katkat
Back

Count Blocked Rate-Limited Requests

RenderSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of rate-limiting logic, sliding-window time-based counting, and data structure design for tracking per-IP and per-(IP, host) request histories.

You are given an in-memory request log for a web platform. Each log entry has:

  • timestamp: an ISO-8601 UTC timestamp
  • request_ip: the client IPv4 address
  • host: the hostname being requested

The log is already sorted by time in ascending order, and you may assume it fits in memory.

A request is evaluated against a sliding window of T seconds. For a request at time t, only earlier requests with timestamps in the interval (t - T, t) are counted. A request that happened exactly T seconds earlier is not in the window.

Important rules:

  • A request that gets blocked must still be counted in the history for future requests.
  • If multiple requests have the same timestamp, process them in input order.
  • In part 2, if a request violates both rules, it should be counted as one blocked request, not two.

Part 1: Per-IP rate limiting

Implement logic to count how many requests would be blocked by this rule:

  • A request from IP x is blocked if there have already been at least IPReqMax requests from the same IP in the previous T seconds.

In other words, the current request is blocked when:

  • count(previous requests from same IP in (t - T, t)) >= IPReqMax

Example

Input log:

timestamp,request_ip,host
2024-01-01T00:00:00+00:00,127.0.0.1,example1.com
2024-01-01T00:00:01+00:00,127.0.0.1,example2.com
2024-01-01T00:01:02+00:00,127.0.0.1,example1.com
2024-01-01T00:01:03+00:00,127.0.0.1,example2.com
2024-01-01T00:01:04+00:00,127.0.0.1,example1.com
2024-01-01T00:02:04+00:00,127.0.0.1,example1.com

With IPReqMax = 1 and T = 60:

  • Request 1 -> succeed
  • Request 2 -> blocked
  • Request 3 -> succeed
  • Request 4 -> blocked
  • Request 5 -> blocked
  • Request 6 -> succeed

So the answer is 3 blocked requests.

Part 2: Per-IP and per-(IP, host) rate limiting

Now add a second rule:

  • A request from IP x to host h is also blocked if there have already been at least IPHostReqMax requests from the same IP to the same host in the previous T seconds.

A request is blocked if either of these is true:

  1. count(previous requests from same IP in (t - T, t)) >= IPReqMax
  2. count(previous requests from same IP and same host in (t - T, t)) >= IPHostReqMax

Again, blocked requests still contribute to both counters for future requests.

Example

Input log:

timestamp,request_ip,host
2024-01-01T00:00:00+00:00,127.0.0.1,example1.com
2024-01-01T00:00:01+00:00,127.0.0.1,example2.com
2024-01-01T00:00:10+00:00,127.0.0.1,example1.com
2024-01-01T00:00:11+00:00,127.0.0.1,example3.com
2024-01-01T00:01:04+00:00,127.0.0.1,example3.com
2024-01-01T00:01:11+00:00,127.0.0.1,example1.com

With IPReqMax = 3, IPHostReqMax = 1, and T = 60:

  • Request 1 -> succeed
  • Request 2 -> succeed
  • Request 3 -> blocked by per-(IP, host) rule
  • Request 4 -> blocked by per-IP rule
  • Request 5 -> blocked by per-(IP, host) rule
  • Request 6 -> succeed

So the answer is 3 blocked requests.

Task

Write an efficient function or program that, given the sorted request log and the parameters:

  • T
  • IPReqMax
  • optionally IPHostReqMax

returns:

  1. the number of blocked requests under the per-IP rule only, and
  2. the number of blocked requests under the combined per-IP and per-(IP, host) rules.

Aim for an approach that is efficient for large logs loaded into memory.