public
Created

Solution to the SlidingWindowMap coding challenge by Cedric Beust

  • Download Gist
slidingwindowmap.py
Python
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
# 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()

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.