I am a software engineer at Google on the Android project and the creator of the Java testing framework TestNG. When I'm not updating this weblog with various software-related posts or speaking at conferences, I am busy snowboarding, playing squash, tennis, golf or volleyball or scuba diving. Cedric is a DZone MVB and is not an employee of DZone and has posted 84 posts at DZone. You can read more from them at their website. View Full User Profile

Coding Challenge: a Sliding Window Map

09.03.2012
| 3065 views |
  • submit to reddit

A lot of sites offer programmatic access to their content via API’s. The main advantage for the producer of this content is to be able to control finely what they export and how they export it (and also avoid being scraped) while clients receive the data they need in a structured and documented way. These API’s are usually strictly monitored to make sure that clients can’t abuse them. For example, the producer will typically limit how often clients can call a certain API, how much data they can transfer every minute, etc…

Today’s coding challenge is based on these requirements.

We want to make multiple calls to a site that only allows to use a key 500 times every 10mn. You are given a collection of keys (strings), a max count (e.g. 500) and a time period (e.g. 10mn) and your task is to implement getNextKey() as follows:

public class SlidingWindowMap {
  public SlidingWindowMap(Set<String> keys, int maxCount, long 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() { 
    // Your brilliant solution goes here
  }

}

I’m keeping the statement of the problem as open as possible to encourage exploration, but feel free to ask for clarifications if something is not clear. Please post your solution on a pastebin/gist like site (or wherever your code will be easy to read) and link to it in your comment. All languages are welcome.

 

Published at DZone with permission of Cedric Beust, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)