CODEWITHSUNDEEP
algorithmdata-structures
James
James

Reputation: 47

Data Structure Interview

Given login/logout time of all users for a particular website in the form: (userId, login time, logout time). Store this data, to query the total number of users who logged in and logged out in a given time range.

What data structure should I use? and how to implement it?

Upvotes: 0

Views: 1375

Answers (3)

Tamas Ionut
Tamas Ionut

Reputation: 4410

The data structure you're looking for is called an interval tree and it basically has a binary-search tree like format with the start of the interval (login time) as the values (ordering as in BST).

This DS has the following time complexities:

  • Add an interval (login-logout): O(logN)
  • Remove an interval: O(logN)
  • Given an interval [start-finish], find overlapping intervals: O(logN)

Upvotes: 2

ravi
ravi

Reputation: 10733

I don't think there is any single data structure which would give you better complexities than below mentioned approach :-

  1. Prepare two sorted list one for login times and other for logout times.
    • O(N logN)
  2. For each query, do a binary search on both lists to count the number of logins and number of logouts prior to given time.
    • O(log N)
  3. Then the number of logged in user count would be (logins - logouts).
    • O(1)

Upvotes: 0

seokhoonlee
seokhoonlee

Reputation: 1038

If you want to do this within a program:

Just create a simple array containing class User type variable.

User class should have attributes: userId, loginTime, logoutTime.

Checking the total number of users who logged in and logged out in a given time range will be something like:

for (user in userArray)
  if (user.loginTime > inputLoginTime && user.logoutTime < inputLogoutTime)
    count++;

You can check for the total number of users in O(n) time.

If you want to do it in Server, eg. MySQL.

Create a table User with userId, loginTime, logoutTime as column.

SELECT COUNT(*) FROM User WHERE User.loginTime > inputLoginTime AND User.logoutTime < inputLogoutTime;

Upvotes: 0

Related Questions