Google Interview Question for Software Engineer Interns


Country: United States




Comment hidden because of low score. Click to expand.
2
of 4 vote

class R implements RateLimit {
		Queue<Long> queries;
	 	int previous_count;
		int qps;

		void setQPS(int qps) {
			this.qps = qps;
			queries = new LinkedList<>();
		}

		boolean allowThisRequest() {
		        if (qps <= 0) return false;
		        long now = System.currentTimeMillis();
		        while(now - queries.peek() < 1000) queries.poll();
		        
		        if(queries.size() < qps){
		        	queries.add(now);
		        	return true;
		        }
		        else
		        	return false;
		}

- Mike October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Clearly the guard of the while loop should be

while(now - queries.peek() > 1000)

and not

while(now - queries.peek() < 1000)

- Mike October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 31, 2020 | Flag
Comment hidden because of low score. Click to expand.
1
of 7 vote

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()

- IgorBrown31 October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- masterjaso October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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) {
 ...
}

- Anonymous October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- IgorBrown31 October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

eg. 0.1 0.9 1.2 and qps = 2. then we have to remove 0.1's count when 1.2 is coming.

- mapan0817 October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()?

- mapan0817 October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :)

- Mike October 30, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
	}
}

- Herve.Yuancheng October 30, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }
    }

- russs November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- pavel.kogan January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;

}

- GrayMouser October 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# 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()

- LZ May 02, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More