CareerCup

In my opinion, a combination of data structures should solve the problem. Use a min-heap and a BST augmented by the size field.

1. The BST will store userids as keys along with last-logged-in field.
2. The min heap will have last-logged-in time as key. Along with the key store the userid.
3. When a new user logs in or an old user re-logs into the system, insert a key into the heap. In the BST if the corresponding userid is present, update it's last-logged-in value. Otherwise insert a new key with the userid
4. Whenever we want to find out the unique users logged in the last 10 mins.
a. Extract min from the heap if current time - last-logged-in time > 10 mins
b. For the corresponding Id in the BST, delete the node if current time - last-logged-in time > 10 mins
c. Repeat the above steps a & b until the min element of the heap satisfies current time - last-logged-in time <= 10 mins
d. Return the value of size field of the root node of the BST.

Why can't we use an hashmap in this scenario.

store userid as key and time stamp as value.
whenever a user logins into a server, add that info into the hashmap,
if it is a new user, a new element is inserted into the hashmap.
if the user already logged in, just the value (in this case timestamp) will be updated in the hashmap.
retrieve data using current time - last login time <= 10 mins, in this case we will get unique users

There is one way that I can think of. When ever user logs in put the data into queue. and deque data that is older than 10 minutes say every one minute interval. Parallelly put insert the data (when user logs in) into a map (update timestamp if it already contains this users data). when ever a user info is being dequed from queue, compare data with map and if timestamp is same remove this data.
This map contains information of last login of users upto last 10 minutes. so when it requires detail of number of users logged in at particular time the size of this map will give you the info.

design a data structure with user id and other user information and log in time
create a hash table with this data structure. to count users, discard those user whose last log in is more than 10 mins ago. we can also start a clean up in every 10 mins, delete those entries whose last login is more than 10 mins ago.

Create a Map with userid as key and time stamp that he logged in.
-> when ever user log-in's into the system, store his userid and time stamp into the map and store this into a Queue.
-> When ever time stamp crosses 1 min insert an empty data.
-> So, when the queue reaches 2o min, flush out the first 10 minutes data. As the Queue will hav latest 10 min data.
-> hope this should work.

I though of this solution:
1. Create a min-heap and add users as they login
2. if time > 10 min, delete the root and maintain the min-heap
3. if count needed, traverse the heap (heap sort algo) and tag the corresponding entry of the user in hashtable (this avoids outputting the same user multiple times).
4. Keep the count of new users as you add to the hash
5. return the count (or the entries of the hash, if userIDs are needed) and clear hash.

Generic solution to last N minute
======================================================================

1. Add Login Listener (typically a filter where a user login can be tracked)
[Alternate solution a scheduler @ one minute, but it's the better use rather than scheduler. KInd of ovserver design]

2. Whenever a user logs into the system then Login Event handler manages a TreeMap
where key is minute {1, 2 , ... N .....} and value is corresponding unique user count.
To determine user counter another temporary Set should be used where login user id(s) are stored when next minute comes then Set gets cleared and points to current minute users counter

startTime : Time
// initially 1
currentMinute: Integer
timeMap: TreeMap
function LoginEventHandler(userId : String) {
	endTime: Time
	loginUsers : Set
 	if( (endTime - startTime) / 60*currentMinute > 0 ) {
		// new minute starts
		currentMinute++;

		// clear temp set
		loginUsers.clear();
		loginUsers.add(userId);
		
		// update user counter against minute
		timeMap.put(currentMinute, loginUsers.size());
	} else {
		// continue with current minute
		boolean add = loginUsers.add(userId);
		if(add) {
			//new user
			// update user counter against minute
			timeMap.put(currentMinute, loginUsers.size());
		}
	}
}

3. Now actual trick comes into play ;)
timeMap could be used with HashMap but why TreeMap is used, let's understand
From above code it's oviuos for each minute entry may not be there and it should not there like <minute> => 0

Now N minute is given the trick comes if N does not exist so next existing entry ( less than N) should be picked
That's why TreeMap is used.

Here user should not be mapped because billion users login can happen so it won't be good design. If less user logs in then also it won't be good design to map user id because then whole user id set iterates

Using Splay Trees would provide the best solution here...

-Reasons:
1.)As here we want to keep track of the latest data for the past 10 minutes. Splay trees will have it mostly in the 10 closest node to the root.
2.)Also it solves our problem of one user accessing multiple time by providing faster updates.B'coz Splay trees are designed to give faster 2nd time access which BST does not provide.

You can Google for Splay trees and check for there AWESOME properties...

1) hashmap -> whose every element is userid + pointer to corresponding node in doubly linked list
2) doubly linked list (DLL) -> userid + timestamp

Along with these, we store count of users when the last insert/select operation operation is performed and the threshold timestamp value (last insert/select timestamp - 10 mins) and the pointer to last node in doubly linked list satisfying this threshold timestamp value.

a) Insert -

1) Go to corresponding hashmap entry and check if entry already exists.
2) If not exist, create a new DLL node and add it to beginning of DLL and increment count by s. calculate current threshold value and adjust the pointer and count according to that.
3) If already exists, move this to the beginning of DLL. If prev timestamp is above the threshold, do nothing. Otherwise, increment count by 1. calculate current threshold value and adjust the pointer and count according to that.

b) Finding unique user count:
1) calculate current threshold value and adjust the pointer and count according to that. Return the count.

There are two important points to note here:
1. Focus is on "fastest retrieval of unique user count"
2. The query can come in at anytime and not fixed 10 minute intervals.

We can solve it by using a Hash-table with min-heap. The hashtable uses userid as key and stores last logged in time. The min-heap uses last logged in timestamp as key. Every node in min-heap is pointed to by an element in hashtable with corresponding userid.

Everytime a user logs in:
1. Extract-min from min heap while timestamp at root is more than 10 mins older.
2. Update the timestamp in hashtable for given userid.
3. If the element in hashtable does no point to any node in min-heap,
3.a. Insert a node to min-heap with key as new timestamp and point hashtable element to this node.
ELSE
3.b. update timestamp of the pointed min-heap node and min-heapify at this node.

Everytime user count is required:
1. Extract-min from min heap while timestamp at root is more than 10 mins older.
2. Return heap-size.

How is the user login information stored?

If its in a flat log file, then read the file with the proper fields into memory(assuming that the file can be in memory). Create a hashmap with the user id as the key and the value as the count of times the user has logged in.
While scanning the file filter on the time field such that (current_time - user login time) <= 10 mins.

If the user login is stored in database, query it as:
Select distinct user_id
from user_login_table
where datediff(mi, login_time, getdate()) <= 10

A simple hashset that clears and re-populates every ten minutes should do?