Google Interview Question
Senior Software Development EngineersCountry: United States
Here the solution that will use a definable number of slots vs. tracking requestLimit-Amount of items in the queue. Que size never exceed slotCt.
class RateLimitter
{
private:
queue<std::pair<long long, unsigned int>> requests_;
long long intervalUs_;
unsigned int requestLimit_;
unsigned int slotCt_;
long long slotLengthUs_;
unsigned int reqsPerInterv_;
public:
RateLimitter(long long intervalMs, unsigned int requestLimit, unsigned int slotCt = 100)
: intervalUs_(intervalMs * 1000), requestLimit_(requestLimit), slotCt_(slotCt),
slotLengthUs_(intervalMs * 1000 / slotCt), reqsPerInterv_(0) {
if (slotLengthUs_ == 0) throw invalid_argument("intervalMs > slotCt");
}
bool processRequest() {
long long nowUs = duration_cast<microseconds>(steady_clock::now().time_since_epoch()).count();
long long slotId = nowUs / slotLengthUs_;
// is oldest slot expired
if (!requests_.empty() && requests_.front().first <= slotId - slotCt_) {
reqsPerInterv_ -= requests_.front().second; // all that were in this slot get freed
requests_.pop(); // remove it
}
// is there "space"?
if (reqsPerInterv_ < requestLimit_) {
reqsPerInterv_++;
if (!requests_.empty() && requests_.back().first == slotId) {
requests_.back().second++; // append to open slot
} else {
requests_.push({slotId, 1}); // create new slot with count 1
}
return true;
}
return false;
}
};
Using a circular array and Decorator design pattern.
#include <iostream>
#include <vector>
#include <unistd.h>
using namespace std;
class Server {
public:
virtual void ProcessRequest() = 0;
};
class MyServer : public Server {
public:
virtual void ProcessRequest()
{
cout << "request processed\n";
}
};
class RateLimiter : public Server {
public:
RateLimiter(Server *server, int interval, int limit)
{
server_ = server;
limit_ = limit;
interval_ = interval;
counts_.resize(interval, 0);
start_time_ = 0;
rate_ = 0;
}
virtual void ProcessRequest()
{
if (RequestAllowed()) {
server_->ProcessRequest();
} else {
cout << "request discarded\n";
}
}
private:
bool RequestAllowed()
{
uint32_t current_time = time(NULL);
start_time_ = max(start_time_, current_time - interval_ * 2);
while (start_time_ <= current_time - interval_) {
rate_ -= counts_[start_time_ % interval_];
counts_[start_time_ % interval_] = 0;
++start_time_;
}
if (rate_ >= limit_) {
return false;
} else {
++counts_[current_time % interval_];
++rate_;
return true;
}
}
int interval_, limit_, rate_;
uint32_t start_time_;
vector<int> counts_;
Server *server_;
};
int main() {
MyServer my_server;
RateLimiter rate_limiter(&my_server, 60, 10);
Server *server = &rate_limiter;
while (true) {
server->ProcessRequest();
sleep(1);
}
}
@ChrisK. It may be worth to check if back() of the queue is too old and if so, to clear the queue (maybe by replacing it with another instance). E.g. there are millions requests within the interval, then, no requests within a time greater than the interval. In this case, currently, the first request that comes after the gap will be iterating the millions of requests sitting in the queue.
@Alex, not sure I understood your question... Are you saying the queue is full with 1 Mio item because that's the limit per interval. Then at least a whole interval passes with no requests and now an other burst arrives?
Then, when the first of these requests arrives, it will see, the queue is full, it will only remove the oldest item and place itself in the back. The next item does the same until one item arrives that can't remove from the front because the front is not old enough - that would work with 1 Mio items, if you want to spend the memory for that. If it's a ring-buffer it's the same, nothing ever get's moved, copied or iterated. I would question the 1 Mio / interval and whether it's worth spending the memory for that purpose, but it would work. If it's 1 Mio, I definitely would start to think about compacting into sub-intervals and counting. Solution would still be O(1) but much more complicated.
I think that's the charm of the solution, it does never need to iterate, so it's always plain O(1) - not compensated, neat for high throughput.
We can use a semaphore (using same queue concept), to give a specific number of threads access and keep remaining waiting.
Java code -
public class Process {
Semaphore semaphore = new Semaphore(5);
public static void main(String[] args) {
Process example = new Process();
example.work();
}
public void work(){
Counter counter = new Counter();
for(int i = 0; i <= 40; i++){
Thread t = new Thread(new Runner("T"+i, semaphore, counter));
t.start();
}
}
}
class Runner implements Runnable{
String name;
Semaphore semaphore;
Counter counter;
public Runner(String name, Semaphore semaphore, Counter counter) {
super();
this.name = name;
this.semaphore = semaphore;
this.counter = counter;
}
@Override
public void run() {
try {
semaphore.acquire();
counter.incrementCount();
System.out.println("Running thread " + name + " current active count = " + counter.getCount() + " No. of threads on wait = " + semaphore.getQueueLength());
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}finally{
counter.decrementCount();
semaphore.release();
}
}
}
class Counter{
private static int count = 0;
private static final Object countLock = new Object();
public void incrementCount() {
synchronized (countLock) {
count++;
}
}
public void decrementCount() {
synchronized (countLock) {
count--;
}
}
public int getCount() {
synchronized (countLock) {
return count;
}
}
}
package com.ds.general;
import java.time.*;
import java.util.*;
public class RateLimiter {
static class Req{
Instant start;
int id;
Req(Instant s,int i){
start = s; id = i;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Queue<Req> queue = new ArrayDeque<Req>();
int limit = 3, interval = 5;
for(int i=0;i<=10;i++) {
try {
Req req = new Req(null,i);
boolean b = false;
while(!b) {
b = process(queue,req,limit,interval);
System.out.println("Request id:"+i+" processed:"+b);
Thread.sleep(1000);
}
}
catch(Exception e) {
}
}
}
static boolean process(Queue<Req> queue, Req req,int limit, int interval) {
boolean out = false;
if(queue.size() < limit) {
req.start = Instant.now();
queue.offer(req);
out = true;
}
else{
Req head = queue.peek();
long t = timeDiff(head.start,Instant.now());
if(t >= interval * 1000) {
queue.poll();
req.start = Instant.now();
queue.offer(req);
out = true;
}else {
out = false;
}
}
return out;
}
static long timeDiff(Instant start, Instant end) {
return Duration.between(start, end).toMillis();
}
}
- Chris November 29, 2017