Ebay Interview Question
Software Engineer / DevelopersTeam: Traffic
Country: United States
Interview Type: In-Person
if all users login when the server starts up, and never log out, then between 3pm-4pm of a day, there will be no log. So we have to track back to the beginning of the log.
A naïve solution is track every user id from beginning, until 4pm, then we know at the moment of 4pm, how many users are only.
But what does it mean how many users are only between 3pm-4pm? We assume who ever online even instantly will be counted. Also assume one user login multiple times will be count only once.
So : track from the beginning of the log, up to 3pm, then add all the users log in between 3pm-4pm, that's the number.
However the above is naïve solution, and is super inefficient.
I can't come up with a much more efficient solution.
A slightly better solution would be:
1) first, count all users login and logout between the given interval(say 3pm-4pm), these are all users that online between 3pm-4pm
2) Search back from 3pm, ignore the entries about the users we already know are online between 3pm-4pm. For a certain user, if we see a logout first, then it is offline between 3pm-4pm, if we see a login first, then it is online.
3) We have to keep searching back until: we covered all existing users, or we hit the point that the service started up.
2) Search back from 3pm, ignore thos
Are we assuming that login and logout times dont span across days?
In that case we can maintain an array of size 24 intialized with counter value '0' for 24hours in a day. Depending on the login and logout time, we can increase the counter for the range.
For e.g. the 1st user has login time = 1 and logout time = 4
Then we would increament the value in a[1], a[2], a[3] and a[4]
We can solve this using interval trees.
- hmm January 08, 2014Each node in the tree stores - tStart,tEnd, tMax
tStart - starting timestamp
tEnd - ending timestamp
tMax - max ending timeStamp in the subtree rooted at that node
Recursive algorithm to find interval intersection:-
findIntersection(Node root, Ts start,Ts end,Queue q)
1. if root interval intersects given interval, add to queue and recursive search left and right subtrees.
2. if leftChild is null search right subtree
3. if node.left.tMax < tStart search left subtree.
4. otherwise search leftSubtree
Time Complexity - O(R logN)
Where N-> number of nodes,R-> number of intersecting intervals found