CareerCup

If we need to maintain statistics for only a week than "Circular buffer" will be the right candidate.
It will contain 7 buckets (day, count).
As we will reach at 7th day (completed cycle), it will override first day.

And we will maintain a single global counter for "week".
Each time we will move from Sunday to Monday and will overiride Monday than we will remove its count value from the week counter.

Mon->Tue->Wed->Thu->Fri->Sat->Sun->Mon

We can easily get count for one day with O(1), and for week with O(1)

We may want to use Synchronized keyword for each of the update functions, as multiple threads in the web app can call that function and their updates should be mutually exclusive.

Firstly， I thought it's easy one. but when I run two threads and simulate 0.5 billion visits, I always got some problems. After several hours debugging and changing, finally I made code work.

OK, let's stop talk and show my c# code.

public static class WebVisitCounter
    {
        //Double buffers
        private static long[,] DailyCounts = new long[2,7];
        private static int _CurrentBufferIndex = 0;        
        private static object sync = new object();
        
        public static void IncrementDailyCounter()
        {
            Interlocked.Increment(ref DailyCounts[_CurrentBufferIndex,(int)DateTime.Now.DayOfWeek]);
        }

        public static long GetDailyCounter(DayOfWeek dw)
        {
            return DailyCounts[_CurrentBufferIndex,(int)dw];
        }

        public static long GetWeeklyCounter()
        {
            long lRet = 0;

            lock(sync)
            {
                for (int i = 0; i < 7; i++)
                {
                     lRet += DailyCounts[_CurrentBufferIndex,i];
                }                
            }
            return lRet;
        }        

        public static void RetSetCounters()
        {            
            //Switch buffer
            if (_CurrentBufferIndex == 0)
            {
                _CurrentBufferIndex = 1;
                PrintCounters();                
                Array.Clear(DailyCounts, 0, 7);
            }
            else
            {
                _CurrentBufferIndex = 0;
                PrintCounters();                
                Array.Clear(DailyCounts, 7, 7);
            }            
        }

        public static void PrintCounters()
        {
            long lTotal = 0;
            for (int j = 0; j < 2; j++)
            {
                Console.WriteLine("==========buffer index = ["+j.ToString()+"] =============");
                lTotal = 0;
                for (int i = 0; i < 7; i++)
                {
                    lTotal += DailyCounts[j, i];
                    Console.WriteLine(i.ToString() + " -- " + DailyCounts[j,i].ToString());
                }
                Console.WriteLine("Weekly = " + lTotal.ToString());
            }
        }
    }

   public class WebVisitCounterManager
    {
        #region Private members

        private static object sync = new object();
        private System.Timers.Timer resetTimer = new System.Timers.Timer(1000); //1 second
        private bool _ResetDone = false;

        private WebVisitCounterManager()
        {
        }

        private static WebVisitCounterManager _instance = null;
        #endregion

        #region Public members

        public static WebVisitCounterManager Instance
        {
            get
            {
                if (_instance == null)
                {
                    lock (sync)
                    {
                        if (_instance == null)
                        {
                            _instance = new WebVisitCounterManager();                            
                        }
                    }
                }

                return _instance;
            }
        }

        #endregion

        public void Init()
        {
            resetTimer.Elapsed += onReset;
            resetTimer.AutoReset = true;
            resetTimer.Enabled = true;
        }

        public void Stop()
        {
            resetTimer.Stop();
        }

        private void onReset(object source, System.Timers.ElapsedEventArgs e)
        {
            if (DateTime.Now.DayOfWeek == DayOfWeek.Monday)
            {
                resetTimer.Stop();
                if (IsMonday())
                {
                    WebVisitCounter.RetSetCounters();
                }
                resetTimer.Start();
            }
        }

        private bool IsMonday()
        {
            DateTime dt1 = DateTime.Parse(DateTime.Now.ToShortDateString() + " 00:00:00");                       
            
            TimeSpan ts = new TimeSpan();
            ts = DateTime.Now - dt1;            
            
            //Make sure reset only once per week
            if (ts.TotalSeconds < 0.5 && !_ResetDone)
            {
                _ResetDone = true;
                Console.WriteLine("========It's the Monday, reset all of daily counters!======");
                //Thread.Sleep(500);
                return true;
            }
            else
            {                
                _ResetDone = false;
                return false;
            }
        }
    }

     public static void TestWebVisistCounter()
        {
            WebVisitCounterManager.Instance.Init();

            Thread t1 = new Thread(new ThreadStart(Counting));
            Thread t2 = new Thread(new ThreadStart(Counting));

            t1.Start();
            t2.Start();

            t1.Join();
            t2.Join();

            WebVisitCounter.PrintCounters();

            WebVisitCounterManager.Instance.Stop();
            
            Console.WriteLine("============End of the test =============");
        }
        static void Counting()
        {
            //0.25 billion times
            for (int i = 0; i < 250000000; i++)
            {
                WebVisitCounter.IncrementDailyCounter();
            }
        }

Output:

========It's the Monday, reset all of daily counters!======
==========buffer index = [0] =============
0 -- 60511274
1 -- 50673865
2 -- 38735856
3 -- 38527673
4 -- 37408341
5 -- 37447992
6 -- 38037093
Weekly = 301342094
==========buffer index = [1] =============
0 -- 0
1 -- 7673
2 -- 0
3 -- 0
4 -- 0
5 -- 0
6 -- 0
Weekly = 7670
==========buffer index = [0] =============
0 -- 0
1 -- 0
2 -- 0
3 -- 0
4 -- 0
5 -- 0
6 -- 0
Weekly = 0
==========buffer index = [1] =============
0 -- 0
1 -- 198657906
2 -- 0
3 -- 0
4 -- 0
5 -- 0
6 -- 0
Weekly = 198657906
============End of the test =============

Guess what! 301342094 + 198657906 = 500000000! Bingo!!

Note:
1 why it's different
==========buffer index = [1] =============
0 -- 0
1 -- 7673
2 -- 0
3 -- 0
4 -- 0
5 -- 0
6 -- 0
Weekly = 7670

Look at code in PrintCounters()

lTotal += DailyCounts[j, i]; // 7670

                     //when print, it changed to 7673
                    Console.WriteLine(i.ToString() + " -- " + DailyCounts[j,i].ToString());

Because those two threads keep visiting, there are three visits happened between two lines of code.

2 Why not count 7670/7673 in, because 198657906 already contains those visits.

If we need to maintain statistics for only a week than "Circular buffer" will be the right candidate.
It will contain 7 buckets (day, count).
As we will reach at 7th day (completed cycle), it will override first day.

And we will maintain a single global counter for "week".
Each time we will move from Sunday to Monday and will overiride Monday than we will remove its count value from the week counter.

Mon->Tue->Wed->Thu->Fri->Sat->Sun->Mon

We can easily get count for one day with O(1), and for week with O(1)

how it is O(1), we have go thru the entire list to find for a particular day is it not O(n)