Facebook Interview Question: Given two unsorted arrays, on... | Glassdoor.co.uk

## Interview Question

Software Engineer Interview London, England

# Given two unsorted arrays, one with event start times and

one with end times, find out if any two events overlap.

2

array S;
array E;

for(int o=1; o S[i] &amp;&amp; S[o] S[i]) || (S[o] == S[i] &amp;&amp; E[o] == E[i]))
print "Event " + o + " intersect event " + (i+1);
}
}

Matteo Gobbi on 5 Oct 2013
1

I'm sorry, the condition in the second for cycle is: i

Matteo Gobbi on 5 Oct 2013
1

Best I could figure out (algorithm):
1. Sort the two arrays (using heap sort), while keeping the correlation between the start and end date.
2. Traverse the start date array, checking neighbouring intervals for any overlap (left, right or inside).
time O(n log n); space O(1)

Anonymous on 24 Jan 2014
0

// NOTE: I haven't tested in an editor, may not compile.
// Please think as a pseudo code

public static void main(String[] args){

// we assume the lists are populated
// and there is a correlation between arrays
ArrayList eventstart;
ArrayList eventend;

printInterlappingEvents(eventstart, eventend);

if(anyOverlap == false){
System.out.println("Good! There is no overlap!");
}
}

public static void printInterlappingEvents(ArrayList eventstart, ArrayList eventend){

// assumption : arrays have same size
for(int index1 = 0; index1 event1start &amp;&amp; event2start event1start &amp;&amp; event2start &lt; event1end)

){
// then there is an overlap
System.out.println(event1start + ":" + event1end + " overlaps with " + event2start + ":" + event2end);

}
}
}

return anyOverlap;

}

Genc on 13 Aug 2014
3

http://www.geeksforgeeks.org/merging-intervals/

Gilad Darmon on 6 Dec 2014