Country: United States

Comment hidden because of low score. Click to expand.
4
of 4 vote

Sort all the login times in one list, sort all the logout times in another list. This is O(NlogN) preprocessing. Now when a query comes along, do a binary search on both lists to count the number of logins and the number of logouts prior to the specified time. Then the number of logged in users is logins minus logouts. This query answering process is O(logN). So for N elements and D queries, we achieve O((N+D) log N) when we count both preprocessing and query cost.

Comment hidden because of low score. Click to expand.
0

struct sessiontime
{
time logout;
};
now sort all the node based on logout in decreasing order .then for given time start from first node and check if logout time is greater and login time is lesser to given time if so count++ and move to next node until logout time <given time .return count;

Comment hidden because of low score. Click to expand.
1
of 1 vote

time complexity o(nlogn)

Comment hidden because of low score. Click to expand.
0

Anonymous: not the same as my algorithm. Mine costs O (NlogN) preprocessing and O (logN) per subsequent query; yours costs up to to O (N) per subsequent query.

@Sukusuku: this problem has both initial preprocessing complexity and per-query complexity that need to be discussed. See my analysis in the original answer.

Comment hidden because of low score. Click to expand.
1
of 1 vote

yes your right in case of more subsequent query urs is efficient thanks for suggestion

Comment hidden because of low score. Click to expand.
0

beautiful solution

Comment hidden because of low score. Click to expand.
0
of 4 vote

segment tree

Comment hidden because of low score. Click to expand.
0

I think fenwick tree is much easier solution for this problem.

2 trees
2 cumulative frequency for logout

new intervals can be added in logN time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) only query the number of users online once O(n): We can compare the each user's login time and logout time to the given time. If the login time is less than or equal to the given time and the logout time is greater than the given time, then then user is online.

2) Query m times the number of users online, where is m is large(O(mlogn + nlogn) instead of O(m*n)): we can precompute the number of users at certain times (times in the login and logout). Then we sort the times. Given a query time, we use binary search to find the largest time less than or equal to the given time and return the number of users online for this time.

``````import java.util.*;

public class UsersOnlineFinder {
private List<Log> logs;
//array size 2.
//array[0]: # of login at this time
//array[1]: # of logout at this time
private List<Integer> times;

public UsersOnlineFinder(List<Log> logs) {
this.logs = logs;
}

public int queryOnceMethod(int time) {
int sum = 0;
for(Log log : logs) {
int logoutTime = log.getLogoutTime();
if(loginTime <= time && time < logoutTime) {
sum++;
}
}
return sum;
}

public int preComputeMethod(int time) {
int index = Collections.binarySearch(times,time);
if(index < 0) {
index = -index - 1;
index--;
}
if(index < 0) {
return 0;
}else {
return array[0] - array[1];
}
}

public void preCompute() {
for(Log log : logs) {
}

Collections.sort(times);

int sumLogout = 0;
for(int time : times) {
sumLogout += array[1];
array[1] = sumLogout;
}
}

//type 0 -- login, 1 -- logout
public void updateLoginandout(int time, int type) {
if(array == null) {
array = new int[2];
}
array[type]++;
}

public static void main(String[] args) {
List<Log> logs = new ArrayList<Log>();
UsersOnlineFinder finder = new UsersOnlineFinder(logs);
System.out.println(finder.queryOnceMethod(0));
System.out.println(finder.queryOnceMethod(6));
System.out.println(finder.queryOnceMethod(8));
System.out.println(finder.queryOnceMethod(10));
System.out.println(finder.queryOnceMethod(11));
System.out.println("--------------");
finder.preCompute();
System.out.println(finder.preComputeMethod(0));
System.out.println(finder.preComputeMethod(6));
System.out.println(finder.preComputeMethod(8));
System.out.println(finder.preComputeMethod(10));
System.out.println(finder.preComputeMethod(11));
}
}

class Log {
private int logoutTime;

public Log(int loginTime, int logoutTime) {
this.logoutTime = logoutTime;
}

}

public int getLogoutTime() {
return logoutTime;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

segment tree is the best solution if there are huge number of users.

Comment hidden because of low score. Click to expand.
0

Do you have a strategy to beat O((N+D) logN) using segment trees, where N is the number of entries and D the number of queries?

A full answer would explain in what way segment trees are to be used.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

O(n)
Consider every login/logout pair, count it if login happened prior to the given time, and logout happened after the given time.

``````int users_logged_in(const vector<pair<int, int> >& logs, int curr_time) {
int logged_in = 0;
for (int i = 0; i < logs.size(); i++) {
if (logs[i].first <= curr_time && logs[i].second > curr_time)
logged_in++;
}
return logged_in;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Interval tree is also fine

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.