Google Interview Question
Software Engineer InternsCountry: United States
Clearly the guard of the while loop should be
while(now - queries.peek() > 1000)
and not
while(now - queries.peek() < 1000)
Why do we need Queue here? We can just initialize global variable oldTimeStamp as 0 and replace it with currentTimeStamp each time function gets called and in the function we can check the difference, simillarly we can have global count variable which can track how many times the function got called and can be reseted to 0.
public class Limiter implements RateLimit {
long time = -1;
int qps;
long qps_millis;
@Override
public boolean allowThisRequest() {
long currentTime = System.currentTimeMillis();
if (time == -1) {
time = currentTime;
return true;
} else {
long result = currentTime - time;
if (result < qps_millis) {
return false;
} else {
time = currentTime;
return true;
}
}
}
@Override
public void setQPS(int qps) {
if (qps < 1 || qps > 1000000) {
throw new RuntimeException();
}
this.qps = qps;
qps_millis = qps * 1000;
}
}
And perhaps synchronize allowRequest()
This is a great solution, particularly for amortizing the connections over time. Another method is to allow each second to be a bucket and implement a connection counter. This would require changing qps_millis to qCount (number of active connections this second) and chaning your conditional check in allowThisRequest to if(qCount < qps) return true. Lastly, you would need to add a check on the time to reset qCount to 0 every 1 second.
This is not a major update, but this would allow for larger 'burst' queries which can limit queue times for use cases where query requests do not come in at a steady pace, but instead come in as large spikes and then subside.
I would encourage providing one of these as the answer but explaining both examples during the follow up to demonstrate mastery.
I do not understand well how your solution works.
Let imagine that qps = 1000000 then qps_millis will be 1000000000 (qps*1000)
Then in your code the "if" test will be true in most cases (and you must allow 1000000 requests in the last second)
long result = currentTime - time;
if (result < qps_millis) {
...
}
public class Limiter2 implements RateLimit {
int qps;
int numQueriesAtCurrentSecond = 0;
long lastUpdateTime = -1;
@Override
public void setQPS(int qps) {
if (qps < 1 || qps > 1000000) {
throw new RuntimeException();
}
this.qps = qps;
}
@Override
public boolean allowThisRequest() {
long currentTime = System.currentTimeMillis();
if (lastUpdateTime == -1) { // first request
lastUpdateTime = currentTime;
numQueriesAtCurrentSecond++;
return true;
} else {
long difference = currentTime - lastUpdateTime;
if (hasSecondPassed(difference)) {
numQueriesAtCurrentSecond = 0;
numQueriesAtCurrentSecond++;
return true;
} else {
if (canAccept1MoreQuery()) {
numQueriesAtCurrentSecond++;
return true;
} else {
// too many queries per second
return false;
}
}
}
}
public boolean canAccept1MoreQuery() {
return numQueriesAtCurrentSecond + 1 <= qps;
}
public static boolean hasSecondPassed(long differenceMillis) {
return differenceMillis >= 1000;
}
}
How about this one? Will it work?
class R implements RateLimit {
long previous_time;
int previous_count;
int qps;
void setQPS(int qps) {
this.qps = qps;
}
boolean allowThisRequest() {
if (qps <= 0) return false;
long now = System.currentTimeMillis();
if (now - previous_time < 1000) {
if (previous_count == qps)
return false;
else {
previous_time = now;
previous_count += 1;
return true;
}
}
else {
previous_time = now;
previous_count = 1;
return true;
}
}
}
s this reasonable? Also, if for supporting multi-thread request, is it ok to just add 'synchronized' for the allowThisRequest()?
Clearly this could not work.
Imagine QPS = 2
You get queries at times 0, 0.2, 0.3, 1.1
Your implementation would do the following
time 0: previous_time = 0 previous count = 1 return true
time 0.2: previoustime = 0.2 previous count = 2 return true
time 0.3 (0.3 - 0 < 1) but QPS == previous count return false
time 1.1: 1.1 - 0.2 = 0.9 return false. BUT it should return true, as it's been more than 1 second since the first query.
You need to keep track of all the queries that were served in the last second (up to QPS), that is the only way :)
package tests;
import java.security.InvalidParameterException;
import junit.framework.TestCase;
import org.junit.Test;
public class TestRateLimit extends TestCase {
interface RateLimit {
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
boolean allowThisRequest();
}
public static class RateLimitImpl implements RateLimit {
@Override
public void setQPS(int qps) {
if (qps < 1 || qps > 100000) {
throw new InvalidParameterException(String.format(
"QPS: %d is not valid", qps));
}
this.qps = qps;
this.serviceTime = 1000.0 / this.qps;
latestStart = MIN_TIME;
}
@Override
public boolean allowThisRequest() {
long crtTime = System.currentTimeMillis();
if (crtTime - latestStart >= serviceTime) {
latestStart = crtTime; // restart
// launch a service here
return true;
} else {
return false;
}
}
private long latestStart;
private int qps;
private double serviceTime;
private static long MIN_TIME = -1;
}
@Test
public void testRateQps() throws Exception {
RateLimit rLimit = new RateLimitImpl();
rLimit.setQPS(1);
long start = System.currentTimeMillis();
assertTrue(rLimit.allowThisRequest()); // request 1 by user1
long elapsed = System.currentTimeMillis() - start;
Thread.sleep(10 - elapsed); // t + 0.01
elapsed = System.currentTimeMillis() - start;
assertTrue(elapsed >= 10 && elapsed <= 11);
assertFalse(rLimit.allowThisRequest()); // request 2 by user2
elapsed = System.currentTimeMillis() - start;
Thread.sleep(1000 - elapsed); // t + 1
elapsed = System.currentTimeMillis() - start;
assertTrue(elapsed >= 1000 && elapsed <= 1001);
assertTrue(rLimit.allowThisRequest()); // request 3 by user4
elapsed = System.currentTimeMillis() - start;
Thread.sleep(5000 - elapsed); // t + 5
elapsed = System.currentTimeMillis() - start;
assertTrue(elapsed >= 5000 && elapsed <= 5001);
assertTrue(rLimit.allowThisRequest()); // request 4 by user3
}
}
interface RateLimit
{
/** Sets the rate, from 1 to 1000000 queries per second */
void setQPS(int qps);
/** accept or reject a request, called when request is received */
bool allowThisRequest();
}
/// <summary>
///
/// </summary>
public class RatingThrottler : RateLimit
{
private long lastTick = 0;//DateTime.UtcNow.Ticks
private long waitPeriod = 0;//default no throttling
private const long NUM_TICKS_PER_SECOND = 10000 * 1000000; //10k ticks per ms
private object syncLock = new object();
public void setQPS(int qps)
{
waitPeriod = NUM_TICKS_PER_SECOND / qps;
}
public bool allowThisRequest()
{
long curTick = DateTime.UtcNow.Ticks;
lock(syncLock){
if ( curTick - lastTick >= waitPeriod)
{
lastTick = curTick;
return true;
}
}
return false;
}
}
It is throttling problem.
double qps = 1; //Max throughput allowed.
double allowance = qps;
bool IsAllowed(double dt) //dt in seconds, since last call
{
allowance += dt * qps;
if (allowance > qps)
allowance = qps; //throttling
if (allowance < 1)
return false;
else
{
allowance -= 1;
return true;
}
}
#include <time.h>
#include <cstdio>
#include <cstdint>
class RateLimiter {
// precision up to nanoseconds
long CLOCK_PRECISION = 1000000000L;
long qps;
long counter;
uint64_t firstRequestTime;
uint64_t getClockTime();
public:
void setQPS(int allowed_qps);
bool allowThisRequest();
};
uint64_t RateLimiter::getClockTime()
{
timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
return CLOCK_PRECISION * ts.tv_sec + ts.tv_nsec;
}
void RateLimiter::setQPS(int allowed_qps)
{
qps = allowed_qps;
}
bool RateLimiter::allowThisRequest()
{
uint64_t now = getClockTime();
uint64_t diff = now - firstRequestTime;
// has a new bucket started ?
if (diff > 1000000000) {
counter = 1;
firstRequestTime = now;
return true;
}
// we are still using the previous bucket, up to qps entries.
else if (++counter <= qps)
return true;
else
return false;
}
# A python o(1) solution
import time
class Solution(object):
def __init__(self, n=0):
"""
:type n: int
"""
self.setLimit(n)
def setLimit(self, n):
"""
:type n: int
"""
if n < 0:
print "invalid input"
return
self.limit = n
self.start = 0
self.bucket = []
def IsRequestAllow(self):
curTime = time.time()
if len(self.bucket) < self.limit:
self.bucket.append(curTime)
return True
elif curTime - self.bucket[self.start] >= 1.0:
self.bucket[self.start] = curTime
self.start = (self.start + 1) % self.limit
return True
else:
return False
obj = Solution()
obj.setLimit(2)
print time.time(), obj.IsRequestAllow()
print time.time(), obj.IsRequestAllow()
print time.time(), obj.IsRequestAllow()
time.sleep(0.5)
print time.time(), obj.IsRequestAllow()
time.sleep(0.5)
print time.time(), obj.IsRequestAllow()
- Mike October 30, 2014