Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Let S = {[a1,b1],[a2,b2],...,[an,bn]} be the set of intervals.
1. Create the following array:
array = {(a1,start),(b1,end),(a2,start),(b2,end),...,(an,start),(bn,end)} (the first coordinate is a number and the second coordinate is a label).
2. Sort the array according to lexicographic order where start<end (the first coordinate is a number).
3. Initialize count=0 (count will mark the current number of overlapping intervals).
4. Initialize maxCount=0 (maxCount will mark the maximum number of overlapping intervals).
5. Define maxStart (maxStatr will mark the start of the interval with maximum overlapping intervals).
6. Initialize maxInterval = null (maxInterval will mark the interval with maximum overlapping intervals).
7. Iterate over the sorted array (beginning to end):
7.1. Increment count whenever you encounter a value whose label is start (x,start).
7.2. Decrement count whenever you encounter a value whose label is end (x,end).
7.3. If count>=maxCount then set maxStart to the current number value of the array element (the x in (x,label)) and set maxCount=count.
7.4. If the current array element is labeled end and after updating count it equals to maxCount-1 it means that the current array point marks the end of the maximum overlapping interval. So we set maxInterval to the interval (maxStart,current_array_element.x).
8. return maxInterval.
Complexity: O(nlogn) worst-case run-time complexity where n is the number of intervals. Space complexity is O(n) for the additional array.
Java Implementation: snipt.org/Bfjaf0
I don't think the maxStart and maxInterval works. my concern is that how do we know which coordinate corresponds to which interval after sorting
it seems like his maxStart will keep advancing as long as coun > maxCount
but that doesnt make sense if that start coordinate doesnt belong to the maxInterval
Why would you need to know for which interval each coordinate corresponds? It suffices to know whether it is a starting coordinate (to increase count) or an ending one (to decrease count).
When count > maxCount both maxStart and maxCount are updated (maxCount to count and maxStart to the current coordinate). The situation where count > maxCount can only occur when we encounter an interval starting coordinate so it will always hold a starting coordinate of some interval.
Maybe I have not understood the question correctly, the algorithm I described above is for finding an interval which overlaps a maximum amount of intervals from the input. For example: if the input intervals are [1,10],[3,6],[5,8] then the output would be [5,6].
If the requirement is to return an interval from the input set which intersects the most set intervals (which, in the example above is [1,10]) then it can be done using Interval Trees (see Wikipedia).
I understand one common approach is to create an array = {(a1,start),(b1,end),(a2,start),(b2,end),...,(an,start),(bn,end)} (the first coordinate is a number and the second coordinate is a label). Sort the array according to lexicographic order where start
What I don't understand when we create the array, we are essentially separating the start time and end time from each interval. So each start time and end time will lose their identify of which interval they belongs to. When we walk through the array, it would not make sense if we just increment/decrement the count without knowing each coordinate corresponds to which interval. If we use a hashmap and map each coordinate to their interval, there might be issues with duplicate start times and end times.
How should we solve this issue?
public class MaximumOverlap {
public static void main(String[] args) {
int[] start = {1, 2, 3, 6};
int[] finish = {6, 7, 5, 8};
QuickSort quick = new QuickSort();
quick.quickSort(finish, 0, finish.length - 1);
quick.quickSort(start, 0, start.length - 1);
int s = 0, f = 0;
int[] count = new int[finish[finish.length - 1] + 1];
int max = 0;
int index = 0;
for (int i = start[0]; i <= finish[finish.length - 1]; i++) {
count[i] = count[i - 1];
if (s < start.length && i == start[s]) {
count[i]++;
s++;
}
if (f < finish.length && i == finish[f]) {
count[i]--;
f++;
}
if (max < count[i]) {
max = count[i];
index=i;
}
}
int k;
for(k=index;k<count.length;)
{
if(count[k]==count[k+1])
{
k++;
}
else
break;
}
System.out.print("interval start time "+index+" interval end time "+(k+1));
}
}
How about this?
Put all the left bounds and right bound of the ranges into an array A, and
sort the array. Do the following.
max = count = 0; // max is the maximum number of overlaps
for (i = 0; i < A.size; i++) {
if (A[i] is a left bound) {
count++;
if (count > max) mx = count;
}
else
count--;
}
Assuming the intervals begin and end at integral values, sort the intervals using their begin values.
Using an auxiliary array aux[n], where n is the maximum end value of all the intervals
Go over aux[] array to find out the maximum value. Do a reverse lookup to find the list of intervals that contain the maximum value of aux[] array.
- Murali Mohan January 22, 2014