Expedia Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
// Time Complexity O(n)
// Space Complexity O(n)
public class OverlappingProblem {
static class Interval {
int start;
int end;
public Interval() {
this.start = 0;
this.end = 0;
}
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
static ArrayList<Interval> getOverlapingInterval(List<Interval> intervals) {
ArrayList<Interval> results = new ArrayList<Interval>();
Collections.sort(intervals, new MyComparator());
int start = intervals.get(0).start;
int end = intervals.get(0).end;
for (int index = 0; index <= intervals.size(); index++) {
if (index == 0) {
start = intervals.get(index).start;
end = intervals.get(index).end;
} else if (index != intervals.size()) {
if (intervals.get(index).start <= end) {
end = (intervals.get(index).end > end) ? intervals.get(index).end : end;
} else {
results.add(new Interval(start, end));
start = intervals.get(index).start;
end = intervals.get(index).end;
}
} else {
results.add(new Interval(start, end));
}
}
return results;
}
public static void main(String args[]) {
List<Interval> listOfIntervals = new ArrayList<Interval>();
listOfIntervals.add(new Interval(1,3));
listOfIntervals.add(new Interval(2,6));
listOfIntervals.add(new Interval(8, 12));
listOfIntervals.add(new Interval(10, 18));
List<Interval> results = getOverlapingInterval(listOfIntervals);
for(Interval result : results) {
System.out.println(result.start+" "+result.end);
}
}
static class MyComparator implements Comparator<Interval> {
@Override
public int compare(Interval a, Interval b) {
int first = a.start - b.start;
return (first == 0) ? (a.end - b.end) : first;
}
}
}
/*
Merge Intervals in-place without using the 'new' operator.
Time: O(nlogn)
Space: O(1)
*/
private static void mergeIntervals(List<Interval> interval) {
if (interval == null) throw new IllegalArgumentException();
if (interval.size() == 0) return;
Collections.sort(interval, new Comparator<Interval>(){
@Override
public int compare(Interval a, Interval b) {
if (a == b) return b.end - a.end;
return a.start - b.start;
}
});
int i = 0;
while (i < interval.size() - 1) {
if (interval.get(i).end >= interval.get(i + 1).start) {
interval.get(i).end = Math.max(interval.get(i).end, interval.get(i + 1).end);
interval.remove(i + 1);
}
else i++;
}
}
Elegant and simple - Time => O(2N)
var intervals = function (array) {
var result = [];
var minIndex = Number.MAX_VALUE;
var maxIndex = Number.MIN_VALUE;
var totalResult = [];
for (var i = 0; i < array.length; i++) {
for (var start = array[i][0]; start <= array[i][1]; start++) {
result[start] = 1;
}
}
for (var i = 0; i < result.length; i++) {
if (result[i] === 1) {
minIndex = Math.min(minIndex, i);
maxIndex = Math.max(maxIndex, i);
}
else {
if (minIndex !== Number.MAX_VALUE && maxIndex !== Number.MIN_VALUE) {
totalResult.push([minIndex, maxIndex]);
minIndex = Number.MAX_VALUE;
maxIndex = Number.MIN_VALUE;
}
}
}
if (minIndex !== Number.MAX_VALUE && maxIndex !== Number.MIN_VALUE) {
totalResult.push([minIndex, maxIndex]);
}
return totalResult;
}
$(intervals([[1, 3], [2, 6], [8, 12], [10, 18]]));
Time O(2N)
/**
* [1,3],[2,6],[8,12],[10,18] => [1,6],[8,18]
* Definition for an interval.
**/
var intervals = function (array) {
var result = [];
var minIndex = Number.MAX_VALUE;
var maxIndex = Number.MIN_VALUE;
var totalResult = [];
for (var i = 0; i < array.length; i++) {
for (var start = array[i][0]; start <= array[i][1]; start++) {
result[start] = 1;
}
}
for (var i = 0; i < result.length; i++) {
if (result[i] === 1) {
minIndex = Math.min(minIndex, i);
maxIndex = Math.max(maxIndex, i);
}
else {
if (minIndex !== Number.MAX_VALUE && maxIndex !== Number.MIN_VALUE) {
totalResult.push([minIndex, maxIndex]);
minIndex = Number.MAX_VALUE;
maxIndex = Number.MIN_VALUE;
}
}
}
if (minIndex !== Number.MAX_VALUE && maxIndex !== Number.MIN_VALUE) {
totalResult.push([minIndex, maxIndex]);
}
return totalResult;
}
$(intervals([[1, 3], [2, 6], [8, 12], [10, 18]]));
public class Interval
{
public int start;
public int end;
public Interval()
{
start =0;
end = 0;
}
public Interval(int s, int e)
{
start = s;
end = e;
}
}
public IList<Interval> Merge(IList<Interval> intervals)
{
IList<Interval> res = new List<Interval>();
intervals = intervals.OrderBy(x => x.start).ToList();
if (intervals == null || intervals.Count == 0)
{
return res;
}
for (int i = 0; i < intervals.Count; i++)
{
var newInterval = new Interval(intervals[i].start, intervals[i].end);
while(i< intervals.Count -1 && newInterval.end >= intervals[i+1].start)
{
if(intervals[i+1].end > newInterval.end)
{
newInterval.end = intervals[i+1].end;
}
}
res.Add(newInterval);
}
return res;
}
We can solve this in C# with O(n) complexity
public class Interval
{
public int start;
public int end;
public Interval()
{
start =0;
end = 0;
}
public Interval(int s, int e)
{
start = s;
end = e;
}
}
public IList<Interval> Merge(IList<Interval> intervals)
{
IList<Interval> res = new List<Interval>();
intervals = intervals.OrderBy(x => x.start).ToList();
if (intervals == null || intervals.Count == 0)
{
return res;
}
for (int i = 0; i < intervals.Count; i++)
{
var newInterval = new Interval(intervals[i].start, intervals[i].end);
while(i< intervals.Count -1 && newInterval.end >= intervals[i+1].start)
{
if(intervals[i+1].end > newInterval.end)
{
newInterval.end = intervals[i+1].end;
}
}
res.Add(newInterval);
}
return res;
}
- PraTrick July 24, 2017