fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <deque>
  4. #include <sstream>
  5. #include <unordered_map>
  6. using namespace std;
  7.  
  8. /*
  9. We want to project an API endpoint with an in-memory rate limiter.
  10.  
  11. The rate limiter should be initialized with a value that represents the maximum requests per
  12. second we want to allow. When a request hots the API endpoint, the rate limiter is asked whether
  13. it has capacity to process this request and will reject or accept the request appropriatly.
  14.  
  15. Assume:
  16. - Time is measured in millisecond resolution.
  17. - API request come in sequentially.
  18.  
  19. Design the interface and implement the logic for the rate limiter
  20.  
  21. Example at a max of 2 requests / sec:
  22. 12:00:01.100 PASS
  23. 12:00:01.200 PASS
  24. 12:00:01.300 FAIL
  25. 12:00:02.100 PASS
  26. 12:00:02.150 FAIL
  27. 12:00:01.200 PASS
  28. */
  29.  
  30. int strToInt(string s) {
  31. 	stringstream ss;
  32. 	ss << s;
  33. 	int value = 0;
  34. 	ss >> value;
  35. 	return value;
  36. }
  37.  
  38. long timeToMsec(string timeStr) {
  39. 	long millisec = 0;
  40. 	int count = 0;
  41. 	std::string s;
  42.  
  43. 	for (int i = 0; i < timeStr.size(); i++) {
  44. 		if (timeStr[i] == ':' || timeStr[i] == '.') {
  45. 			if (count == 0) {
  46. 				millisec += strToInt(s) * 60 * 60 * 1000;
  47. 			}
  48. 			else if (count == 1) {
  49. 				millisec += strToInt(s) * 60 * 1000;
  50. 			}
  51. 			else if (count == 2) {
  52. 				millisec += strToInt(s) * 1000;
  53. 			}
  54.  
  55. 			count++;
  56. 			s.clear();
  57.  
  58. 		}
  59. 		else {
  60. 			s.push_back(timeStr[i]);
  61. 		}
  62. 	}
  63.  
  64. 	if (s.size() > 0) {
  65. 		millisec += strToInt(s);
  66. 	}
  67.  
  68. 	return millisec;
  69. }
  70.  
  71. long diff(long time1, long time2) {
  72. 	return abs(time1 - time2);
  73. }
  74.  
  75. bool isRateLimited(std::string curTimestamp, int clientid = 0) {
  76.     // you wouldn't need a queue, the token bucket would be a single counter and
  77.     // "last event timestamp"
  78.     // the idea being the bucket adds a certain amount based on the amount of time that has passed,
  79.     // and then every event (api call) subtracts a certain amount
  80.     // the rate limit is when there isn't enough to subtract, and the max bucket size determines
  81.     // the burst (vs average) tuning
  82.  
  83.     // assuming the expected output is representing an average of 1 request per 500ms,
  84.     // yes, it would work .. the limit target is 2 (N) per 1000ms (T),
  85.     // so you can form the math like this: max bucket size is 2 * 1000 = 2000; at every
  86.     // event, first get the "ms since last event", and multiply that by N (2), then add
  87.     // that to the bucket (but cap the bucket at 2000 max)
  88.     static long N = 2;
  89.     static long T = 1000;
  90.     static long maxBucketSize = N * T;
  91.     static long lastAllowedRequestMs = 0;
  92.     static long bucket = 0;
  93.  
  94.     long curTimestampMs = timeToMsec(curTimestamp);
  95.     long delta = curTimestampMs - lastAllowedRequestMs;
  96.  
  97.     bucket += delta * N;
  98.     if (bucket > maxBucketSize) {
  99.     	bucket = maxBucketSize;
  100.     }
  101.  
  102.     cout << curTimestamp << "...";
  103.  
  104.     if (bucket >= T) {
  105.     	bucket -= T;
  106.     	lastAllowedRequestMs = curTimestampMs;
  107.     	return true;
  108.     }
  109.     return false;
  110. }
  111.  
  112. int main() {
  113. 	// your code goes here
  114.  
  115. 	cout << isRateLimited("12:00:01.100") << endl; // expect true
  116. 	cout << isRateLimited("12:00:01.200") << endl; // expect true
  117. 	cout << isRateLimited("12:00:01.300") << endl; // expect false
  118. 	cout << isRateLimited("12:00:02.100") << endl; // expect true
  119. 	cout << isRateLimited("12:00:02.150") << endl; // expect false
  120. 	cout << isRateLimited("12:00:02.200") << endl; // expect true
  121.  
  122. 	return 0;
  123. }
  124.  
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12:00:01.100...1
12:00:01.200...1
12:00:01.300...0
12:00:02.100...1
12:00:02.150...1
12:00:02.200...0
https://ideone.com/dfgcoS
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!