-
-
Save cegme/7140483 to your computer and use it in GitHub Desktop.
| 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(); | |
| } |
@cegme, do you think this is "complete enough" for an interview solution?
Also did you mean to call cleanup() from increment()?
Also your max_size only gets you 100 stored increments(), which surely isn't enough. I think this is a significant part of the problem
There were several errors with my first solution.
My first gotcha was that an array can only hold a max of Integer.MAX elements, which pretty much rendered my whole attempt useless. I'll rethink and try again
@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() from increment().
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.
@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"
@cwasher I updated it to complete it. I could implement the ring buffer version if you wouldn't want to.
I haven't really looked at it yet I wanna take a stab at this. We're currently doing something similar to this at work actually (tracking page views over time and reporting it back on demand). I know this is a contrived example but I'm trying to see if the solution we have or a derivative of it would work here. The difference is there's nanosecond precision whereas we're only doing down to the minute. Also, space really isn't an issue we have pretty beefy cluster where this data lives. I'll probably give it a go in #Golang It's pretty interesting the way we do it but the difference is the time frames are static which makes it easier It's more like 1st, 2nd, 3rd, or 4th quarter of the current hour (or the previous hour if the time requested is in the future) then something similar for a particular hour of a given day. This is a very interesting problem.