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

- hmm January 08, 2014 | Flag Reply
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

- gz January 14, 2014 | Flag Reply
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]

- techpanja January 08, 2014 | Flag Reply
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

- whoami March 02, 2014 | Flag Reply
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)

- bijiben May 19, 2014 | Flag Reply
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
              print username

will it work ?

- Vivek January 08, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More