Per-Domain Request Limiter
Updated
Problem statement
A server receives n requests. Request i comes from the domain domains[i] at second times[i]. The requests are listed in the order they arrive, so times never decreases.
To protect the server, each domain may have at most limit accepted requests in any window seconds. Process the requests in order. A request from domain d at second t is accepted if fewer than limit earlier requests from d were accepted at a second s with t - window < s <= t. Otherwise it is rejected.
- Only accepted requests count toward the limit. A rejected request does not use up any of its domain's room.
- Each domain has its own limit. Requests from other domains never affect it.
- Requests at the same second are handled in the order they appear.
Return a boolean array answer where answer[i] is true if request i is accepted and false if it is rejected.
Function
limitDomainRequests(domains: String[], times: int[], limit: int, window: int) → boolean[]Examples
Example 1
domains = ["alpha.com","alpha.com","beta.org","alpha.com","alpha.com","beta.org"]times = [1,2,2,3,6,7]limit = 2window = 5return = [true,true,true,false,true,true]With window = 5, a request at second t looks back at seconds t - 4 to t.
- Requests 0 and 1 (
alpha.comat seconds 1 and 2) are accepted. - Request 2 is the first from
beta.org, so it is accepted. - Request 3 (
alpha.comat second 3) sees 2 acceptedalpha.comrequests in seconds -1 to 3, at seconds 1 and 2. That is the limit, so it is rejected. - Request 4 (
alpha.comat second 6) looks at seconds 2 to 6. The request at second 1 no longer counts, so only 1 accepted request remains in that window, and request 4 is accepted. - Request 5 (
beta.orgat second 7) looks at seconds 3 to 7. Thebeta.orgrequest at second 2 is outside, so request 5 is accepted.
Example 2
domains = ["x.io","x.io","x.io","x.io"]times = [0,0,5,10]limit = 1window = 10return = [true,false,false,true]Only 1 request per 10 seconds is allowed. Request 0 at second 0 is accepted. Requests 1 and 2, at seconds 0 and 5, are rejected because the request at second 0 is still in the window.
Request 3 at second 10 looks at seconds 1 to 10. The accepted request at second 0 is now outside, and the rejected request at second 5 does not count, so request 3 is accepted.
Example 3
domains = ["api.site","cdn.site","api.site","cdn.site"]times = [4,4,4,4]limit = 1window = 1return = [true,true,false,false]All four requests arrive at second 4 and are handled in the order given. Each domain gets its own limit of 1, so the first request from each domain is accepted and the second from each is rejected.
Constraints
1 <= domains.length <= 1000times.length == domains.length1 <= domains[i].length <= 30domains[i]contains only lowercase English letters, digits,'.'and'-'.0 <= times[i] <= 109times[i] <= times[i + 1]1 <= limit <= 10001 <= window <= 109
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
- Longest Subsequence That Is a SubstringOA · Seen Oct 2024
Similar questions at other companies
- Per-Client Sliding-Window Rate LimiterGeneral Motors · OA
- Per-Client API Rate LimiterDocker · PHONE SCREEN
- Per-Client Sliding-Window Rate LimiterCVS Health · PHONE SCREEN
- Sliding-Window Rate LimiterAmazon · ONSITE INTERVIEW
- Sliding-Window Rate LimiterUber · PHONE SCREENUber interview questions
- Rate Limiter with Global and Per-User LimitsOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Delayed Streaming Duplicate SuppressionGoogle · PHONE SCREENGoogle interview questions
- Metric Counter with a Fake ClockSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- Per-Client Sliding-Window Rate LimiterNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
- Completions API Rate LimiterCursor · PHONE SCREENCursor interview questions
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)