Last active
June 27, 2024 01:07
Revisions
-
vprasanth revised this gist
Jun 27, 2024 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -2,7 +2,7 @@ We want to build a rate limiter system for a frontend which receives requests at whole seconds. Assume we have all the requests over an interval of time represented as an array, e.g., requests = [0,0,1,1,1,2,2] The index is the reauest ID and the value is the time stamp. Design a rate limiter that can enforce a limit of Q requests per T seconds. The output should return the timestamp of dropped requests as well as the -
vprasanth revised this gist
Jun 19, 2024 . 1 changed file with 1 addition and 0 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -40,6 +40,7 @@ function processRequests(q, t, requests) { if (buckets[b]) { buckets[b]++; if (buckets[b] > q) { // check if bucket has exceeded limit droppedTimes.add(requests[i]); droppedRequests.push(i); } -
vprasanth created this gist
Jun 19, 2024 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,65 @@ /* We want to build a rate limiter system for a frontend which receives requests at whole seconds. Assume we have all the requests over an interval of time represented as an array, e.g., requests = [0,0,1,1,1,2,2] The index is the reauest ID and the value is the time stamo. Design a rate limiter that can enforce a limit of Q requests per T seconds. The output should return the timestamp of dropped requests as well as the request IDS. eg 1 Requests = [0, 0, 1, 1, 1, 2, 2]; For Q = 2 and T = 1 we get Dropped times = [1] Dropped requests = [4] eg 2 Requests = [0, 0, 0, 1, 1, 2, 2, 2] For Q = 2, T = 2, we get Dropped times = [0, 1, 2] Dropped requests = [2, 3, 4, 7] */ const example1 = [0, 0, 1, 1, 1, 2, 2]; const example2 = [0, 0, 0, 1, 1, 2, 2, 2]; function getBucket(r, t) { return Math.floor(r / t); } function processRequests(q, t, requests) { const droppedRequests = []; const droppedTimes = new Set(); const buckets = {}; for (let i = 0; i < requests.length; i++) { let b = getBucket(requests[i], t); if (buckets[b]) { buckets[b]++; if (buckets[b] > q) { droppedTimes.add(requests[i]); droppedRequests.push(i); } } else { buckets[b] = 1; } } return { buckets, droppedTimes: Array.from(droppedTimes), droppedRequests, requests, q, t, }; } const eg1 = processRequests(2, 1, example1); const eg2 = processRequests(2, 2, example2); console.log(eg1); console.log(eg2);