Skip to content
Create a gist now

Instantly share code, notes, and snippets.

Embed URL


Subversion checkout URL

You can clone with
Download ZIP
Beust Challenge - Sliding window map
package com.mainaud.slidingwindow;
import java.util.Set;
public class SlidingWindowMap {
private long periodMs;
private SlidingWindow[] keyWindow;
public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs) {
keyWindow = new SlidingWindow[keys.size()];
int i = 0;
for (String key : keys) {
keyWindow[i++] = new SlidingWindow(key, maxCount);
public String getNextKey() {
String key = null;
// Change i initialization to change key usage distribution
for (int i = 0; key == null && i < keyWindow.length; ++i) {
key = keyWindow[i].getKey(periodMs);
return key;
* Keep the last maxCount usage timestamp and test the oldest one. Use an array as a round buffer because it is easy an
* efficient.
private static class SlidingWindow {
private final String key;
private final long[] timestamp;
private int next;
SlidingWindow(String key, int maxCount) {
this.key = key;
this.timestamp = new long[maxCount];
* works when periodMs < currentTimestamp. if paranoid uncomment next line:
// java.util.Arrays.fill(timestamp, Long.MIN_VALUE);
synchronized String getKey(long periodMs) {
long now = System.currentTimeMillis();
if (now > timestamp[next] + periodMs) {
timestamp[next] = now;
next = (next + 1) % timestamp.length;
return key;
} else {
return null;

Many thanks for this, it's really helpful. However, what does 'String key' represent (e.g. line 31)? I can't work it out from your code?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.