## Expedia Interview Question for Software Developers

Country: United States
Interview Type: In-Person

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

``````/**
* [1,3],[2,6],[8,12],[10,18] => [1,6],[8,18]
* Definition for an interval.
**/
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};

bool compare(Interval a, Interval b) {
return a.start < b.start;
}

vector<Interval> merge(vector<Interval> &A) {
vector<Interval> result;
vector<Interval>::iterator it;
sort(A.begin(), A.end(), compare);
if (A.empty()) {
return result;
}
else {
result.push_back(*A.begin());
for (it = (A.begin() + 1); it != A.end(); ++it) {
if ((*it).start > result.back().end)
result.push_back(*it);
else
result.back().end = max(result.back().end, (*it).end);
}
}
}``````

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

``````// 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 {
start = intervals.get(index).start;
end = intervals.get(index).end;
}
} else {
}

}

return results;
}

public static void main(String args[]) {

List<Interval> listOfIntervals = new ArrayList<Interval>();

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;
}

}

}``````

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

This is not O(n) if you are sorting the array.

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

/*
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++;
}
}``````

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

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]);
}
}

\$(intervals([[1, 3], [2, 6], [8, 12], [10, 18]]));``````

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

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]);
}
}

\$(intervals([[1, 3], [2, 6], [8, 12], [10, 18]]));``````

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

``````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;
}
}
}
return res;
}``````

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

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;
}
}
}
return res;``````

}

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.