How should I practice Hierarchical Fixed-Window Rate Limiter?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Headway phone screen problems in FastPrep.

Is Hierarchical Fixed-Window Rate Limiter associated with Headway?

FastPrep tags this as a Headway phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Hierarchical Fixed-Window Rate Limiter

Learn this problem

● Medium

HeadwayFULLTIMEPHONE SCREEN

Problem statement

You are given two parallel arrays describing requests in nondecreasing timestamp order:

timestamps[i] is the request time in whole seconds.
endpoints[i] is the endpoint requested at that time.

Process the requests in order with two fixed-window limits:

For each endpoint, accept at most 2 requests during each integer second.
Across all endpoints together, accept at most 10 requests during each integer minute. Minute m contains timestamps from 60 * m through 60 * m + 59.

A request is accepted only when both limits have remaining quota. Only an accepted request consumes endpoint and global quota; a rejected request changes neither counter.

Return an array answer where answer[i] is 1 when request i is accepted and 0 when it is rejected.

Function

applyRateLimits(timestamps: int[], endpoints: String[]) → int[]

Examples

Example 1

timestamps = [0,0,0,1]endpoints = ["/search","/search","/search","/search"]return = [1,1,0,1]

The first two requests consume the endpoint's quota for second 0. The third is rejected. Timestamp 1 starts a new endpoint window, so the fourth request is accepted.

Example 2

timestamps = [5,5,5,5,5,5,5,5,5,5,5]endpoints = ["/a","/b","/c","/d","/e","/f","/g","/h","/i","/j","/k"]return = [1,1,1,1,1,1,1,1,1,1,0]

No endpoint exceeds its per-second quota, but the first ten accepted requests fill the shared quota for minute 0. The final request is rejected.

Example 3

timestamps = [58,58,58,58,59,60,60]endpoints = ["/x","/x","/x","/y","/y","/x","/x"]return = [1,1,0,1,1,1,1]

The rejected third request does not consume shared quota. Endpoint /y has its own per-second windows at timestamps 58 and 59. Timestamp 60 starts both a new second and a new minute.

Constraints

1 <= timestamps.length = endpoints.length <= 200000
0 <= timestamps[i] <= 1000000000
timestamps is in nondecreasing order.
1 <= endpoints[i].length <= 50
Each endpoint contains only lowercase English letters, digits, /, -, and _.