Solution to the SlidingWindowMap coding challenge by Cedric Beust

slidingwindowmap.py

# solution to http://beust.com/weblog/2012/09/02/coding-challenge-a-sliding-window-map/

import heapq
import time

class SlidingWindowMap(object):
    def __init__(self,api_keys,max_count,period_minutes):
        self.period = period_minutes * 60
        self.pq = []
        for api_key in api_keys:
            for count in range(max_count):
                stamp = time.time() - self.period - 1
                key = "%s-%s" % (str(count),api_key)
                entry = [stamp,key]
                heapq.heappush(self.pq,entry)

    def get_next_key(self):
        stamp,key = heapq.heappop(self.pq)
        if stamp >= time.time() - self.period:
            return None
        new_entry = [time.time(),key]
        heapq.heappush(self.pq,new_entry)
        return key.split('-')[1]

if __name__ == "__main__":
    api_keys = ['abc','def','g']
    swm = SlidingWindowMap(api_keys,500,10)
    print swm.get_next_key()