Internet Question Interview Question Site Reliability Engineers


Team: N/A
Country: United States


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

isn't a greedy problem??

- Hector on January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

1)if it is to be done in O(N) time , that means the list of people with starting and ending time could be traversed at most once. Now this can only lead to us towards a solution , if the list of people was already sorted according to the starting time . Then we can just check the consecutive element's starting time & ending time and decide whether they overlap or not .

2) Other wise we can sort the list of people according to the start time , which will anyway require a pre processing time of O(NlogN) & then a O(N) search as stated in 1 . So eventually it is O(N) .

3) last which I can think of is to overcome the sorting effort , that can be done by keeping the state of the previous persons start and end time . We can do so by some kind of hash table , where we hash according to the start time . when ever any persons start time falls in a bucket , we search in that bucket with all other persons to figure out the overlap . But this is also not O(N) theoretically , as small buckets can be of size N at the worst case , hence leading to O(N) .

- Saikat on January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Very neat solution. I worked out an O(nlog(n)) solution using binary tree, but yours is clearly better. For O(n) I worked out a similar solution (that space complexity depends on range of time) but you reminded me that we could make a hash function and divide (min,max) time range into n buckets, so "on average" this should be roughly O(n) and certainly better than O(nlog(n))

- Polymorpher on January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think instead of checking consecutive elements starting and ending point, keep track of maxima of ending point and check whether current one's ending point is less than that or not. This will cover all cases

- govind on January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Keeping tracking maxima of ending points doesn't cover the case of disjoint intervals. For example: [-10,-9],[9,10],[-1,1]. This is actually what I did in my first attempt.

- Polymorpher on January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

An idea - quantize / discretize the intervals as coarsely as practical, and have an array of quanta covering the range of all the intervals. For each person's interval, fill in all the covered quanta. If the quantum is already filled, they've collided with someone. You have to do this twice, because the first person eg won't know whether he's collided with anyone otherwise. It's all still O(n). If you don't need infinite, split-second precision.

- JeffD on January 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is similar to activity selection problem as described in Coremen where both Dynamic as well as Greedy solutions are presented.

- Learner on February 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Iterate through all the elements (0..N-1) in a loop.
2. if ((f[i+1] > f[i]) && s[i+1]>f[i])) AND ((f[i] > f[i-1]) && (s[i]>f[i-1)) THEN
mark the ith person overlap-free.

Here, one needs to take care about the value of 'i' not falling of the edges of the range i.e (0..N-1).
Also, f[i] = finish time of ith person
s[i] = start time of ith person.

ASSUMPTION: Persons are already sorted on their finish times.

- Learner on February 02, 2012 | Flag Reply


Add a Comment
Name:

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

Books

is a comprehensive book walking you through 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