Implementing Circular Buffer

Question

Found this interview question and trying to solve it with Java.

Q:Design a function to gives real time statistics of your web traffic,count one day's website visit ，count one week's website visit.

I understand that this will require a circular data structure. Which one will be appropriate in case of Java implementation CircularBuffer or Circular LinkedList.
If circular buffer is not right solution then what is?

What make you think a circular buffer would be an appropriate structure for this process? — OldCurmudgeon, Nov 04 '13 at 14:16
I guess, It would require to capture data in every 7 days. Circular Buffer has O(1) complexity of retrieving and adding the data. If you think of a better solution, please let me know. — Himanshu Yadav, Nov 04 '13 at 14:19
What's the difference between a "circular buffer" and a "circular linked list"? Isn't a buffer a *use* of a linked list? Are you asking about a specific implementation? — Dave Newton, Nov 04 '13 at 14:48
I am not sure if Java API has a circular buffer/linkedlist implementation out of the box. Yes I am asking about the implementation if possible. — Himanshu Yadav, Nov 04 '13 at 14:50
@HimanshuYadav see [java-ring-buffer](http://stackoverflow.com/questions/7266042/java-ring-buffer) **, or** [how-would-you-code-an-efficient-circular-buffer-in-java-or-c-sharp?](http://stackoverflow.com/questions/590069/how-would-you-code-an-efficient-circular-buffer-in-java-or-c-sharp?lq=1) — nawfal, Jun 08 '14 at 09:52

score 1 · Answer 1 · answered Nov 04 '13 at 14:50

1

I would do this like this.

private long dayCount = 0;
private long lastSixDaysCount = 0;

// called once per day
public void rollDayCount() {
    saveDayCountToDB(dayCount);
    lastSixDaysCount = sumLastSixDaysFromDB();
    dayCount = 0;
}

public void incrementCount() {
    dayCount++;
}

public long getDayCount() {
    return dayCount;
}

public long getWeekCount() {
    return dayCount + lastSixDaysCount;
}

If you need to, you can make the fields volatile and synchronized on incrementCount()

answered Nov 04 '13 at 14:50

Peter Lawrey

525,659
79
751
1,130

Thanks for the implementation. How would this data be kept?Lets say I want to access count for a day `Monday`? – Himanshu Yadav Nov 04 '13 at 14:53
@HimanshuYadav I would store it in some database or file. You want to be able to keep this information even if the process dies or is restarted. You don't want to wait a week for the counts to be repopulated as you might need to restart the application after a week. – Peter Lawrey Nov 04 '13 at 14:55

score 0 · Answer 2 · answered Nov 04 '13 at 14:18

0

Nothing to do with circular buffers - however, have a look at Buffer Utils from apache

The trick is to drop data when you capacity is exceeded, you can do this by creating an array with fixed size. Then use a readpointer and writerpointer. when the writepointer overlaps and is at the same position with the readpointer, move both.

If you show your existing code, we'll help you.

answered Nov 04 '13 at 14:18

MemLeak

4,456
4
45
84

I didn't write any code yet. Still trying to come up with a proper data structure. – Himanshu Yadav Nov 04 '13 at 14:25

score 0 · Answer 3 · answered Nov 04 '13 at 14:49

If it is simply counting the no of visitors than it is a tricky multithreading question to count no of unique visitors. This is one of the best places where you can use AtomicInteger.

AtomicInteger atomicInteger = new  AtomicInteger();
public void increment(){
    Integer present=null;
    Integer expect=null;
    do{
        present=atomicInteger.get();
        expect = present+1;
    }while(!atomicInteger.compareAndSet(present, expect));
}

If you have to clear it after some threshold than it's also simple. Hope it helps.

score 0 · Answer 4 · answered Nov 04 '13 at 14:53

0

Maybe a CircularFifoBuffer is what you are looking for. As others wrote, I don't know if a circular structure is really what you need, but the Common-Collection-Utils from Apache already implement a circular buffer

answered Nov 04 '13 at 14:53

ThanksForAllTheFish

7,101
5
35
54

Implementing Circular Buffer

4 Answers4