Amazon Interview Question
SDE-2sTeam: AWS
Country: United States
Interview Type: In-Person
Look up an interval O(1)
Insert a new, non-overlapping interval O(n)
Insert an interval that partially overlaps some existing interval(s) O(n + k) where `k` is the number of overlapping intervals.
function IntervalCache () {
this.intervals = {}
}
IntervalCache.prototype.find = function (interval) {
return this.intervals[interval.join(',')]
}
IntervalCache.prototype.insert = function (interval) {
var intersections = []
for (var key in this.intervals) {
if (({}).hasOwnProperty.call(this.intervals, key)) {
if ((interval[1] >= this.intervals[key][0] && interval[1] <= this.intervals[key][1]) ||
(interval[0] >= this.intervals[key][0] && interval[0] <= this.intervals[key][1]) ||
(interval[0] < this.intervals[key][0] && interval[1] > this.intervals[key][1])) {
intersections.push(this.intervals[key])
delete this.intervals[key]
}
}
}
if (intersections.length === 0) {
this.intervals[interval.join(',')] = interval
return
}
var min = interval[0]
var max = interval[1]
while (intersections.length) {
interval = intersections.pop()
if (interval[0] < min) {
min = interval[0]
}
if (interval[1] > max) {
max = interval[1]
}
}
this.intervals[[min, max].join(',')] = [min, max]
}
var cache = new IntervalCache()
cache.insert([25,100])
cache.insert([250,550])
cache.insert([1000, 1200])
cache.insert([400, 700])
cache.insert([30, 60])
console.log(cache)
public void MergeIntervals(List<Interval> Intervals)
{
foreach (var interval in Intervals.ToList())
{
if(ListOfInterval == null)
{
ListOfInterval = new List<Interval>
{
new Interval(interval.Start, interval.End)
};
}
else
{
foreach(var existingInterval in ListOfInterval.ToList())
{
if (interval.Start > existingInterval.Start && interval.End < existingInterval.End)
{
interval.IsDealt = true;
continue; // Within a existing range
}
else
if (interval.Start < existingInterval.Start && interval.End > existingInterval.End)
{
ListOfInterval.Remove(existingInterval);
ListOfInterval.Add(new Interval(interval.Start, interval.End));
interval.IsDealt = true;
break;
}
else
if (interval.Start > existingInterval.Start && interval.Start < existingInterval.End
||
interval.End > existingInterval.Start && interval.End < existingInterval.End)
{
ListOfInterval.Remove(existingInterval);
ListOfInterval.Add(new Interval(
Math.Min(interval.Start, existingInterval.Start),
Math.Max(interval.End, existingInterval.End)
));
interval.IsDealt = true;
break;
}
}
if (! interval.IsDealt)
ListOfInterval.Add(new Interval(interval.Start, interval.End));
}
}
}
Update: As the problem looks like it need a data structure like cache to hold elements and perform operations. LinkedHashMap may be suitable to implement this as insertion and deletion are easy on it.
My below code is written using ArrayList and I am creating a result list every time when insert request comes which is not optimal.
Previously:
Possibility-1: This problem is combination of merge intervals and insert intervals case if the problem says the problem start with list of unsorted intervals.
Possibility-2 : If the problem is to assume one interval comes at a time as input, then it is straight forward insert interval case.
Java Solution:
Interval object can be stored as below.
Key points:
1. As the question is not clear, if the intervals are sorted or not incase of more intervals as a preprocessing step.
We can take initial List of initial set of inputs and sort them and merge them and keep it ready.
This can be a preprocessor step.
Merge (preprocess step) can be like below
2. After step-1, for every new interval, it is a insert interval scenario (data is already sorted in step-1)
- joboj January 22, 2017