## Ebay Interview Question for Software Engineer / Developers

Team: Traffic
Country: United States
Interview Type: In-Person

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

We can solve this using interval trees.

Each 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

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

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

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

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]

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

1. find when the server started up in the log
2. create a counter
3. read the log from server start
4. if find login, increase counter, if find logout , decrease the counter, there is no need to care about the user id

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

select count(*) from (select distinct user_id from table where start_time >= t1 and end_time <= t2)

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

``````split the input range to first and second
Loop till end of the log file line by line
compare first with login time and second with logout time
if first > login and second < logout

will it work ?

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.