public
Last active

Cedric's Coding challenge: a sliding window map (http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/)

  • Download Gist
SlidingWindowMap.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
package com.beust.coding.challenge.slidingwindowmap;
 
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
/**
*
* @author rnaufal
*
*/
public class SlidingWindowMap {
 
private final Set<String> keys;
private final int maxCount;
private final long periodMs;
private final Map<String, SlidingWindow> slidingWindowByKey = new HashMap<String, SlidingWindow>();
 
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
this.keys = keys;
this.maxCount = maxCount;
this.periodMs = periodMs;
}
 
/**
* @return a key that has been used less than `maxCount` times during the
* past `periodMs` milliseconds or null if no such key exists.
*/
public String getNextKey() {
for (String key : keys) {
SlidingWindow slidingWindow = slidingWindowByKey.get(key);
if (slidingWindow == null) {
slidingWindow = new SlidingWindow();
slidingWindowByKey.put(key, slidingWindow);
return key;
}
if (slidingWindow.isValidForUse(maxCount, periodMs)) {
slidingWindow.incrementUse(periodMs);
return key;
}
}
return null;
}
 
private class SlidingWindow {
 
private int countUses = 1;
private long period = System.currentTimeMillis();
 
public boolean isValidForUse(int maxCount, long period) {
return isCountValid(maxCount) && isPeriodValid(period);
}
public void incrementUse(long period) {
incrementCount();
incrementPeriod(period);
}
 
private boolean isCountValid(int maxCount) {
return countUses < maxCount;
}
 
private boolean isPeriodValid(long periodMs) {
return System.currentTimeMillis() - period <= periodMs;
}
private void incrementCount() {
this.countUses++;
}
 
private void incrementPeriod(long period) {
this.period = System.currentTimeMillis() + period;
}
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.