Which approach is the right one in an interview?


  • 0
    I

    The first method that came to mind was the queue method where you remove elements in getHits(). Which one should we actually implement? Should we use a circular array or something else?


  • 2
    F

    Either is the right one in an interview, because they are actually identical solutions.
    You may think using queue is not scale-able, because a solution like this:

    class HitCounter {
        queue<int> m_q;
    public:
        void hit(int timestamp) {
            m_q.push(timestamp);
        }
        int getHits(int timestamp) {
            while(m_q.size() && m_q.front() <= timestamp - 300)
                m_q.pop();
            return m_q.size();
        }
    };
    

    Takes O(Number of all timestamps during past 5 mins, which can be very large) space.
    Then you may think, well, I wrote a wrong one, I should have used the circular array one, because that one only takes O(300) space always.

    However, if you think about the theory behind the both ideas, you will find they are actually same. You can implement a queue using circular array, and you can also use a queue to simulate a circular array. If you realize they are essentially same, you will know you don't have to SWITCH to circular array, instead, you IMPROVE your current solution to make it take O(300) space too.
    Here is a O(300) constant space solution using QUEUE:

    class HitCounter {
        queue<pair<int, int>> m_q;
        int total_count = 0;
    public:
        void hit(int timestamp) {
            total_count ++;
            if (m_q.size() && m_q.back().first == timestamp)
            {
                m_q.back().second ++;
                return;
            }
            if (m_q.size() >= 300) //There can't be >300 distinct timestamps;
            {
                total_count -= m_q.front().second;
                m_q.pop();
            }
            m_q.emplace(timestamp, 1);
        }
        int getHits(int timestamp) {
            while(m_q.size() && m_q.front().first <= timestamp - 300)
            {
                total_count -= m_q.front().second;
                m_q.pop();
            }
            return total_count;
        }
    };
    

    See? You can just IMPROVE your old solution by adding a few lines to make it scale too.
    If this is a real interview, I'd rather code the simpler queue-based solution first and then improve it to be scablable when my interviewer asks me to do so, than directly code the circular array. Because the former way is way easier to code and so easy to be bug free.


  • 0
    This post is deleted!

  • 0

    I did circular array, which guarantees O(M) for hit() and getHits(), check it out.

    class HitCounter(object):
    
        def __init__(self, T=300):
            self.vect = [0] * T
            self.idx, self.sums, self.last, self.T = 0, 0, 0, T
    
        def move(self, steps):
            steps = min(steps, self.T)
            for i in range(steps):
                self.idx = (self.idx + 1) % self.T
                self.sums -= self.vect[self.idx]
                self.vect[self.idx] = 0
    
        def hit(self, t):
            t -= 1
            self.move(t - self.last)
            self.last = t
            self.vect[self.idx] += 1
            self.sums += 1
    
        def getHits(self, t):
            t -= 1
            self.move(t - self.last)
            self.last = t
            return self.sums
    

  • 0
    I

    Can you explain how yours works? WHy do you do t -=1? Isn't it still slower than queue solution though cause you can do hit() in O(1) with the queue?


  • 0
    I

    @StefanPochmann Wait how though? If you do a hit, the only two cases are if the timestamp is equal to the last one added, or if it is not equal. If it is equal, he just increments the count, which does not alter the queue size. If the size of the queue is already 300 and the time you want to add is not equal to the last time, you can just delete the entry at the front of the queue and remove it from the count before pushing the new time, so wouldn't that limit the size to 300?


  • 0

    @IWantToPass I'm pretty certain fentoyal added that if (m_q.size() >= 300) part only after I pointed it out. I'll check when I'm back home, might still have the original code there.


  • 0

    @IWantToPass I do t -= 1 because t is 1-based and my circular array is 0-based.


  • 0
    F

    @StefanPochmann Yes, that part was added later. I noticed the bug and hid it when editing. The funny part was after I reshowed it, I couldn't reply to your old message.


  • 0
    I

    @agave But how does the move() part work? Like why is it that you clear out all the numbers from t - self.last if that's less than 300?


  • 0

    @IWantToPass the move() function makes sure that all the old entries in the circular array are erased before we register the hit or we get the total hits. The old entries are all the elements in the array that lie between idx+1 and idx + max(T, steps) (modulus the size of the array). Try and make a small example by yourself to make sure you understand how it works.

    Oh, and also note that incrementing idx at the beginning of the loop is fundamental.


  • 0
    I

    @fentoyal why do you need queue size >= 300? isn't checking if queue size == 300 enough to start removing in the hit function?


  • 0
    F

    @IWantToPass
    Of source it is. But as the saying goes:
    "A good programmer is someone who always looks both ways before crossing a one-way street."
    I have two conventions of handling the code like this, based on the purpose of the code.

    1. If my purpose is to develop some real world product and I'm debugging my code, I will want my code to crash as soon as possible if anything abnormal occurs. Then i will use "==".
    2. If I just want to write a piece of code that can pass all tests case especially in front of an interviewer, I will want my code NOT to crash and pass all test cases even some tiny bug does exist, then I will choose ">=".

    You can never guarantee the assumption you hold when you are coding (or you will be always bug-free), choosing ">=" or "==" here is a philosophy of how soon you want your code crash if your assumption fails.
    In other words, do you want to die immediately when a car is going wrong way, so you know a car didn't obey the rule. or, do you want to behave like you never saw that car and just walk across the street like nothing wrong happened.


  • 0

    @fentoyal Sounds similar to when I'm too lazy to think whether I'll need an int[1001] array or only needint[1000] and instead just use int[1010] :-)

    Thanks for the clarification about the added code, I'll go remove my obsolete comment...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.