-
-
Save victor-teal/4e636fc541dc7156b1cbb520b3bc9ee2 to your computer and use it in GitHub Desktop.
From the website: http://symbo1ics.com/blog/?p=2055 I implemented an interview questions:
Given a timer time() with nanosecond accuracy and given the interface
interface RealTimeCounter: void increment() int getCountInLastSecond() int getCountInLastMinute() int getCountInLastHour() int getCountInLastDay()
implement the interface. The getCountInL…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.lang.System; | |
| import java.util.Collections; | |
| import java.util.Comparator; | |
| import java.util.ArrayList; | |
| public class RealTimeCounterImpl implements RealTimeCounter { | |
| private static final int MAX_COUNTS = Integer.MAX_VALUE >> 8; | |
| private static final Long SECOND = 1000L; | |
| private static final Long MINUTE = 1000L*60L; | |
| private static final Long HOUR = 1000L*60L*60L; | |
| private static final Long DAY = 1000L*60L*60L*24L; | |
| private ArrayList<Long> listCounter; | |
| public int size() { | |
| return listCounter.size(); | |
| } | |
| public void increment() { | |
| if (listCounter.size() == MAX_COUNTS) { | |
| cleanup(DAY); | |
| } | |
| listCounter.add(System.currentTimeMillis()); | |
| } | |
| public int getCountInLastSecond() { | |
| return timeSince(System.currentTimeMillis(),SECOND); | |
| } | |
| public int getCountInLastMinute() { | |
| return timeSince(System.currentTimeMillis(),MINUTE); | |
| } | |
| public int getCountInLastHour() { | |
| return timeSince(System.currentTimeMillis(),HOUR); | |
| } | |
| public int getCountInLastDay() { | |
| return timeSince(System.currentTimeMillis(), DAY); | |
| } | |
| /** | |
| * This takes the current time and a timeframe | |
| * and returns the number of values in listCounter | |
| * that is larger than the now - timeframe. | |
| */ | |
| private int timeSince(Long now, Long timeFrame) { | |
| if (listCounter.isEmpty()) return 0; | |
| Long currentTime = now - timeFrame; | |
| // Do binary search to find the insertion place | |
| // This is an O(log n) opertation | |
| int insertionPoint = Collections.binarySearch(listCounter, | |
| currentTime); | |
| // If a value is not found with binary search | |
| // the insertion point is defined as (-(insertion point) - 1). | |
| if (insertionPoint >= 0) { | |
| // Exact match | |
| return listCounter.size() - insertionPoint; | |
| } | |
| else { | |
| return listCounter.size() + insertionPoint + 1; | |
| } | |
| } | |
| /** | |
| * Remove all items older than this timeframe. | |
| */ | |
| private void cleanup(Long timeFrame) { | |
| // Find all items older than a day an remove them | |
| Long currentTime = System.currentTimeMillis() - timeFrame ; | |
| int index = Collections.binarySearch(listCounter, currentTime); // O (log n) | |
| index = (index >= 0)?listCounter.size()-index:listCounter.size() + index + 1; | |
| // ArrayList doesnt have range remove | |
| // http://stackoverflow.com/questions/2289183/why-is-javas-abstractlists-removerange-method-protected/2289191#2289191 | |
| //listCounter.removeRange(0, index); | |
| listCounter.subList(0, listCounter.size()-index).clear(); // Possibly O(n) | |
| } | |
| public RealTimeCounterImpl () { | |
| listCounter = new ArrayList<Long>(MAX_COUNTS+1); | |
| } | |
| public static void main(String[] args) throws InterruptedException { | |
| RealTimeCounterImpl rtc = new RealTimeCounterImpl(); | |
| System.err.println("rtc.getCountInLastSecond(): " + rtc.getCountInLastSecond() + " [0]"); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| System.err.println("rtc.getCountInLastSecond(): " + rtc.getCountInLastSecond() + " [4]"); | |
| java.lang.Thread.sleep(5000); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| java.lang.Thread.sleep(500); | |
| System.err.println("rtc.getCountInLastSecond(): " + rtc.getCountInLastSecond() + " [7]"); | |
| System.err.println("rtc.getCountInLastMinute(): " + rtc.getCountInLastMinute() + " [11]"); | |
| java.lang.Thread.sleep(1000); | |
| rtc.increment(); | |
| rtc.increment(); | |
| rtc.increment(); | |
| System.err.println("rtc.getCountInLastSecond(): " + rtc.getCountInLastSecond() + " [3]"); | |
| System.err.println("rtc.size(): " + rtc.size() + " [14]"); | |
| //rtc.cleanup(MINUTE); | |
| rtc.cleanup(SECOND); | |
| System.err.println("cleanup"); | |
| System.err.println("rtc.size(): " + rtc.size() + " [3]"); | |
| System.err.println("rtc.getCountInLastSecond(): " + rtc.getCountInLastSecond() + " [3]"); | |
| } | |
| } | |
| interface RealTimeCounter { | |
| public void increment(); | |
| public int getCountInLastSecond(); | |
| public int getCountInLastMinute(); | |
| public int getCountInLastHour(); | |
| public int getCountInLastDay(); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment