design a web counter that returns number of visitors in last 1 mins

Consider storing all the data in a balanced binary search tree, where the keys are the login times and the values are the list of all people who logged in at that time (assuming that there can be multiple logins at exactly the same moment in time). I think there is a much easier way to do this. Return the value of the count from root node of the min heap.īut I am not able to nail down the algorithm for overlapping intervals. Repeat the above step (a) until the min element of the heap satisfiesĬurrent time - last-logged-in time <= t2-t1 minsĬ. If it is greater thanĭelete the value from the hashmap & min_heap.ī. Extract min(root) from the heap and check ifĬurrent time - last-logged-in time > t2-t1 mins. Whenever we want to find out the unique users logged between t2-t1 thenĪ. The min heap and increment the count stored with the root node of min heap.ī) else it's an old user update it's last-logged-in value and do not increment the Lookup in the hashmap with user-id as key.Ī) If no match then insert the new user into hashmap & a new node for user into Number of nodes in the min-heap so we can quickly return the count.

Also at the root store the count of total Min heap - last-logged-in time as key and value as the user-id. Hashmap- will have key as user-id and value as node pointer to corresponding node in IMO combination of Hashmap & min heap would be good as an optimal solution.

Also think about returning total count for overlapping intervals (t1 = 10am, t2 = 10:15am, t3 = 10:30am, return total number of users between 10:10am to 10:20am)īelow is what I am proposing, Would appreciate people's comments? Design an optimal algorithm/data-structure in terms of time complexity to return total number of unique users between given time intervals.įor e.g : Count total number of unique users between interval t1 & t2 and t2 & t3. A Web Server can receive millions of user login request.

Design a web counter that returns number of visitors in last 1 mins