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

Glassdoor uses cookies to improve your site experience. By continuing, you agree to our use of cookies. OK | Learn More

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.
Answer

Interview Answer

5 Answers

2

array S;
array E;

for(int o=1; o S[i] && S[o] S[i]) || (S[o] == S[i] && 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 && event2start event1start && event2start < event1end)

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

               }
        }
    }

    return anyOverlap;

}

Genc on 13 Aug 2014
2

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

Gilad Darmon on 6 Dec 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.