Herve.Yuancheng
BAN USERit contains an extra loop. this is the corrected one:
public boolean containSubSequence(String s) {
Set<String> table = new HashSet<String>();
for (int i = 0; i < s.length(); i++) {
int sameCharIdx = 0;
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(j) == s.charAt(i) && sameCharIdx == 0)
sameCharIdx = j;
if (sameCharIdx != 0 && table.contains("" + s.charAt(i) + s.charAt(j)))
return true;
table.add("" + s.charAt(i) + s.charAt(j));
}
table.clear();
}
return false;
}
package tests;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import java.util.HashSet;
import java.util.Set;
import org.junit.Test;
public class TestSubSequence {
@Test
public void testSubSequece() {
assertTrue(containSubSequence("abab"));
assertTrue(containSubSequence("acbdalidb"));
assertFalse(containSubSequence("abba"));
assertTrue(containSubSequence("xxyy"));
assertTrue(containSubSequence("abcdabc"));
assertFalse(containSubSequence("abcdaxyz"));
}
public boolean containSubSequence(String s) {
Set<String> table = new HashSet<String>();
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
int sameCharIdx = 0;
for (int k = j + 1; k < s.length(); k++) {
if (s.charAt(k) == s.charAt(j) && sameCharIdx == 0) {
sameCharIdx = k;
}
if (sameCharIdx != 0) {
if (table.contains("" + s.charAt(j) + s.charAt(k))) {
return true;
}
}
table.add("" + s.charAt(j) + s.charAt(k));
}
}
table.clear();
}
return false;
}
}
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 November 12, 2014