Internet Question Interview Question for Site Reliability Engineers

• 0

Team: N/A
Country: United States

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

isn't a greedy problem??

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) .

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

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))

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

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

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

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.

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.

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.

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.

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.