Rate Limiter with Hourly and Daily Effort Quotas
Updated
Problem statement
Process a finite ordered sequence of requests. Request i belongs to userIds[i], costs efforts[i] units of effort, and arrives at timestamps[i], measured as a nonnegative Unix timestamp in seconds.
The same positive hourlyLimit and dailyLimit apply independently to every user. Define a request's fixed UTC hour bucket as floor(timestamps[i] / 3600) and its fixed UTC day bucket as floor(timestamps[i] / 86400).
Process requests in input order and apply these rules:
- A request is accepted only when adding its effort keeps that user's accepted effort in both its hour bucket and its day bucket at or below the corresponding limits.
- An accepted request adds its effort to both bucket totals.
- A rejected request leaves all limiter state unchanged.
- Different users maintain independent totals.
Return a boolean array in input order, where element i is true exactly when request i is accepted.
Function
applyRateLimits(userIds: String[], efforts: long[], timestamps: long[], hourlyLimit: long, dailyLimit: long) → boolean[]Examples
Example 1
userIds = ["alice","alice","alice","alice","alice"]efforts = [4,6,1,5,1]timestamps = [0,60,120,3600,7200]hourlyLimit = 10dailyLimit = 15return = [true,true,false,true,false]The first two requests fill Alice's first hour to 10. The third request is rejected and consumes no quota. The fourth request enters a new hour and brings the day total to 15; the fifth is rejected by the daily limit.
Example 2
userIds = ["alice","alice","bob","alice","alice"]efforts = [5,4,5,3,8]timestamps = [10,20,20,3601,86400]hourlyLimit = 8dailyLimit = 8return = [true,false,true,true,true]Alice's second request would exceed both quotas and is rejected. Bob has independent totals. Alice can then use the remaining 3 units in a later hour, and the final request is accepted after the UTC day changes.
Example 3
userIds = ["u","u","u"]efforts = [7,4,3]timestamps = [100,100,100]hourlyLimit = 10dailyLimit = 10return = [true,false,true]The rejected effort of 4 does not mutate state, so the final effort of 3 still fits exactly.
Constraints
userIds.length == efforts.length == timestamps.length.- Every
userIds[i]is a non-empty string. - Every
efforts[i],hourlyLimit, anddailyLimitis a positive signed 64-bit integer. - Every
timestamps[i]is a nonnegative signed 64-bit integer, andtimestampsis nondecreasing. - Hour and day buckets use fixed UTC boundaries derived from Unix time.
More Zscaler interview questions
- Merging PalindromesPHONE SCREEN · Seen Sep 2024
- Find the Element With Odd FrequencyPHONE SCREEN · Seen Jun 2024
- Merge IntervalsPHONE SCREEN · Seen Jun 2024
- Sum of Divisors of the Array GCDPHONE SCREEN · Seen Jun 2024
- Asteroid CollisionONSITE INTERVIEW · Seen Sep 2024
- Check Whether a Byte Is NonzeroONSITE INTERVIEW · Seen Sep 2024
- Count Vowel PermutationsONSITE INTERVIEW · Seen Sep 2024
- Longest Common Subsequence LengthONSITE INTERVIEW · Seen Jun 2024
- Run-Length EncodingONSITE INTERVIEW · Seen Jun 2024
- How Many Sentences? 🌿OA · Seen Mar 2024
Similar questions at other companies
- Process On-Call Routing OperationsOpenAI · PHONE SCREENOpenAI interview questions
- Stateful Paginated Fetch NLyft · PHONE SCREENLyft interview questions
- Escape Room LeaderboardPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Role-Based Network Access ControlOkta · PHONE SCREENOkta interview questions
- Track Package Receipt GapsAmazon · PHONE SCREEN
- Transformer KV Cache OperationsNVIDIA · PHONE SCREENNVIDIA interview questions
- Chatter Message WindowReddit · PHONE SCREENReddit interview questions
- Versioned Recipe Shopping CartDecagon · PHONE SCREENDecagon interview questions
- Random Dasher Set OperationsDoorDash · ONSITE INTERVIEWDoorDash interview questions
- Process Banking OperationsVercel · OA
Zscaler interview experiences
- Zscaler Campus Drive Interviews: 4 Experiences (Part 6 of 6)
- Zscaler Java, QA and Cloud Rounds: 8 Experiences (Part 5 of 6)
- Zscaler UI and DevTest Rounds: 8 Experiences (Part 4 of 6)
- Zscaler Intern, QA and SRE Rounds: 7 Experiences (Part 3 of 6)
- Zscaler SDE C++ and OS Rounds: 7 Experiences (Part 2 of 6)
- Zscaler Campus SDE Interviews: 37 Experiences (Part 1 of 6)