mapan0817
BAN USER- -6of 8 votes
Answers2.
- mapan0817 in United States
String encode(List<String> input);
List<String> decode(String input);| Report Duplicate | Flag | PURGE
Google Software Engineer Intern - -5of 7 votes
AnswersThis is two questions I got from a google interview. Not very sure how to solve it. Any comments would be appreciated.
- mapan0817 in United States
1.
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();
}
brief example:
server instantiates your object, calls setQPS(1)
at at time t, user1 makes a request, allowThisRequest() returns true
at time t+0.01 sec, user2 makes a request, allowThisRequest() returns false
at at time t+1, user4 makes a request, allowThisRequest() returns true
at time t+5 sec, user3 makes a request, allowThisRequest() returns true| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Algorithm
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()?
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