2

The following is an interview question which shows up here and here:

Given a timer time() with nanosecond accuracy and given the interface

interface RealTimeCounter:
    void increment()
    int getCountInLastSecond()
    int getCountInLastMinute()
    int getCountInLastHour()
    int getCountInLastDay()

The getCountInLastX functions should return the number of times increment was called in the last X

Here's one suggested solution (paraphrased from the above blog entry):

Maintain an ArrayList of timestamps. When asked for a given counter, let's say, the count for the last second, perform a binary search for (timer.time() - ONE_SECOND_IN_NANOSECONDS), and return the list.length() - list_index. Then, as a background process at regular intervals we trim our data. Since we only need to maintain data for the last day, we can delete all entries prior to the last day.

Please critique this solution or offer a better performing one.

ChaimKut
  • 2,759
  • 3
  • 38
  • 64
  • 2
    You realise with a 32-bit signed integer, you can only 2.1474836475 seconds in total? – leppie Jun 30 '15 at 11:51
  • @leppie - I think that the counter is activated not every nanosecond, but far less frequently. Otherwise why have a counter at all? – shapiro yaacov Jun 30 '15 at 11:59
  • @leppie Great, that can be part of your solution. How to maintain an 'infinite' counter. In Java, one could use a BigInteger perhaps. Or perhaps an infinite binary counter discussed here: http://stackoverflow.com/questions/15012113/increment-an-infinite-binary-counter . Or a simple linked list which grows after a threshold is reached: http://www.careercup.com/question?id=15259717 (Since the question of an infinite counter is well discussed in these links, it's probably less interesting for that to become the focus of this StackOverflow quesiton) – ChaimKut Jun 30 '15 at 11:59
  • I was just wondering. It could well be running on some 256-bit platform. – leppie Jun 30 '15 at 12:01

0 Answers0