Last active
January 11, 2021 08:41
-
-
Save cegme/7140483 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(); | |
| } |
Author
@cegme If I'm not mistaken we're just using Arrays and HashMaps so yea pretty much vanilla data structures. The idea I'm going to code up this weekend I think I might have a way to constrain how much memory is used but you can blow it out I'm sure if you call it a bunch of times (say 1B maybe) with a certain amount of times, maybe. So I'm gonna see.
@cegme If I'm not mistaken, trying to manage the size of your buffer is one of the biggest challenges with the problem. For example using a circular buffer with a set size of 100 runs fine so long as you don't have 101+ increments within the period, etc. As OP mentioned you could expect this to eventually fail (if you enforce buffer size) or run into the unbounded memory issue (for unbound buffers).
FWIW I think an optimal solution to this problem would run your increment() in O(1) to match the speed at which you're able to call counter.increment(). emphasis on the phrase "realtime counter"
Author
@cwasher I updated it to complete it. I could implement the ring buffer version if you wouldn't want to.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@cwasher I would guess this is a complete solution. You can run this code and it works and this an over the phone interview (45 min).
I would have called
cleanup()fromincrement().There are 2 things I was going to add but I didn't yet. First, is cleaning up by removing items older than a day. Second is fixing the set size and doing the circular buffer.
@wmadisonDev Can you use regular data structures to do this problem at your job? Yea, if you can reset the timer after certain time periods makes it a lot simpler.