Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Coding challenge: a sliding window map

By: mhward07 on Sep 5th, 2012  |  syntax: Java 5  |  size: 3.92 KB  |  views: 83  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import java.util.*;
  2.  
  3. public class SlidingWindowMap
  4. {
  5.         public final static int         s_MaxKeyCount = 500;
  6.  
  7.         public final static long        s_NumMSIn10Min
  8.                                 = 10 /*min*/ * 60 /*sec/min*/ * 1000 /*ms/sec*/;
  9.  
  10.         public final static int         s_NumberOfRequestsIn10Min_OnePerSecond
  11.                                 = 10 /*min*/ * 60 /*sec/min*/ * 2;  // 2 per second or every 500 ms
  12.  
  13.         public final static long        s_TimeBetweenRequestsInMs = 500;
  14.        
  15.         // Input data members
  16.         private Set<String>             m_Keys;
  17.         private Iterator<String>        m_KeysIterator;
  18.         private int                     m_MaxCount;
  19.         private long                    m_PeriodMs;
  20.         private KeyStyle                m_KeyStyle;
  21.  
  22.         // Throttled data members
  23.         private long                    m_LastTime;
  24.        
  25.         // Non-throttled data members
  26.         private int                     m_CurrentCount;
  27.        
  28.         enum KeyStyle
  29.         {
  30.                 NoThrotle,
  31.                 Throtle
  32.         }
  33.  
  34.         public static void main(String[] args)
  35.         throws Exception
  36.         {
  37.                 KeyStyle ks = KeyStyle.Throtle;
  38.                
  39.                 if(args.length == 1)
  40.                 {
  41.                         String keyStyle = args[0];
  42.                         if(keyStyle.equalsIgnoreCase("-throttled"))
  43.                         {
  44.                                 ks = KeyStyle.Throtle;
  45.                         }
  46.                         else if(keyStyle.equalsIgnoreCase("-nonthrottled"))
  47.                         {
  48.                                 ks = KeyStyle.NoThrotle;
  49.                         }
  50.                 }
  51.                
  52.                 Set<String> keys = generateKeys();
  53.                
  54.                 SlidingWindowMap m = null;
  55.                 m = new SlidingWindowMap(keys, 500, s_NumMSIn10Min, ks);
  56.                
  57.                 long start = System.currentTimeMillis();
  58.                
  59.                 boolean firstNullAchieved = false;
  60.                 // Rate is greater than 500 in 10 min. ==> 2 per second. Null's should occur                   
  61.                 for(int i=0; i<s_NumberOfRequestsIn10Min_OnePerSecond; i++)
  62.                 {
  63.                         String key = m.getNextKey();
  64.                         System.out.println(key);
  65.                        
  66.                         if(key == null && firstNullAchieved == false)
  67.                         {
  68.                                 long firstNull = System.currentTimeMillis();
  69.                                 long whenFirstNullAchieved = firstNull - start;
  70.                                 System.out.println("Time Of First Null = "+whenFirstNullAchieved);
  71.                                 firstNullAchieved = true;
  72.                         }
  73.                        
  74.                         Thread.sleep(s_TimeBetweenRequestsInMs);
  75.                 }
  76.  
  77.                 long stop = System.currentTimeMillis();
  78.  
  79.                 long total = stop - start;
  80.  
  81.                 System.out.println("Total Time = "+total);
  82.         }
  83.        
  84.         private static Set<String> generateKeys()
  85.         {
  86.                 Set<String> keys = new HashSet<String>();
  87.                 for(int i=0; i<s_MaxKeyCount; i++)
  88.                 {
  89.                         keys.add("Key"+i);
  90.                 }
  91.                 return keys;
  92.         }
  93.  
  94.         public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs)
  95.         {
  96.                 this.m_Keys             = keys;
  97.                 this.m_KeysIterator = keys.iterator();
  98.                 this.m_MaxCount         = maxCount;
  99.                 this.m_PeriodMs         = periodMs;
  100.         }
  101.        
  102.         public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs, KeyStyle keyStyle)
  103.         {
  104.                 this(keys, maxCount, periodMs);
  105.                
  106.                 this.m_KeyStyle = keyStyle;
  107.         }
  108.  
  109.         /**
  110.          * @return a key that has been used less than 'maxCount' times during the
  111.          * past 'periodMs' milliseconds or null if no such key exists.
  112.          */
  113.         public String getNextKey()
  114.         {
  115.                 String key = null;
  116.                 if(this.m_KeyStyle == KeyStyle.NoThrotle)
  117.                 {
  118.                         key = getNonThrottledNextKey();
  119.                 }
  120.                 else if(this.m_KeyStyle == KeyStyle.Throtle)
  121.                 {
  122.                         key = getThrottledNextKey();
  123.                 }
  124.                 return key;
  125.         }
  126.  
  127.         /**
  128.          * To allow some keys to be accessible through the entire 10 min period.  
  129.          * Return a null for any additional requests over the rate of 0.8333 requests per second.  
  130.          * Every 1.2 seconds a valid key can be provided.
  131.          */
  132.         private String getThrottledNextKey()
  133.         {
  134.                 String key = null;
  135.  
  136.                 long currentTime = System.currentTimeMillis();
  137.                 if(currentTime - this.m_LastTime >= 1200)
  138.                 {
  139.                         if(this.m_KeysIterator.hasNext())
  140.                         {
  141.                                 key = this.m_KeysIterator.next();
  142.                                 this.m_LastTime = currentTime;
  143.                         }
  144.                 }
  145.  
  146.                 return key;
  147.         }
  148.  
  149.         /**
  150.          * First come first serve, all keys may be used up in the first few minutes, leaving a range of
  151.          * time at the end of the period that no keys are returned to any requests.
  152.          */
  153.         private String getNonThrottledNextKey()
  154.         {
  155.                 String key = null;
  156.                 if(this.m_CurrentCount != this.m_MaxCount)
  157.                 {
  158.                         if(this.m_KeysIterator.hasNext())
  159.                         {
  160.                                 key = this.m_KeysIterator.next();
  161.                         }
  162.                 }
  163.                 return key;
  164.         }
  165. }