How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Render.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Render during technical interviews.

Count Blocked Rate-Limited Requests | Render Coding Question

Count Blocked Rate-Limited Requests

Company: Render

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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: ```text 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: ```text 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.

Quick Answer: 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.

Given sorted request logs, count blocked requests for per-IP rate limiting and for combined per-IP/per-(IP,host) limiting. Prior blocked requests still count in history; timestamps exactly T seconds earlier expire.

Constraints

Logs are sorted ascending by timestamp
Same-timestamp requests are processed in input order

Examples

Input: ([['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']], 60, 1, None)

Expected Output: [3, 3]

Input: ([['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']], 60, 3, 1)

Expected Output: [1, 3]

Input: ([[0, 'a', 'h'], [0, 'a', 'h'], [1, 'a', 'h']], 10, 2, 1)

Expected Output: [1, 2]

Hints

Maintain deques of timestamps per key and evict expired entries.

Quick Overview

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.