Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
pubic boolean isConflict(List<Interval> slots){
Collection.sort(slots,new Comparator<Interval>(){
int compareto(Interval one , Interval two){
return one.getStartTime().compareTo(two.getStartTime());
}
}
);
Interval prev = null;
for(Inteval el:slots){
if(prev==null){
prev == el;
continue;
}
if(el.getStartTime()< prev.getEndTime()){
return true;
}
prev = el;
}
return false;
}
Create a array representing 24 hours, each hour's cooresponding element set to 0 (or true, to represent open). Iterate the schedule list, and if the start or end time values are not 0 (open) in the array, return True. Otherwise, set all values between start and end to 1 (closed).
in python:
def detect_sched_conflict(sched_list):
slots = [0 for x in range(0,24)]
for sched in sched_list:
if slots[sched[0]] != 0 or slots[sched[1]] != 0:
return True
for x in range(sched[0],sched[1]+1):
slots[x] = 1
return False
This has O(n) runtime, where n is the length of the slots list. This is because you only have 24 (in this case) available slots, and at least one is lost in each iteration. No matter how many schedule entries you have, if you fill the slots array, you will return.
Caveats:
- For sub-hour scheduling, such as half hour or quarter hour increments, you would have to reconfigure to some degree, but the overall concept stays the same.
- This version doesn't allow schedules to intercent end-to-start (i.e. a 2-5 and 5-7 will not work because they have 5 in common) so it uses atomic assumption that any hour involved is used entirely
- requires use of 24-hour notation rather than 12 hour notation
package com.practice.careercup;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class FB {
public static void main(String[] args) {
FB facebook = new FB();
List<TimeInterval> allMeetings = new LinkedList<FB.TimeInterval>();
//1427207458;//Tue, 24 Mar 2015 14:30:58 GMT
//1427211058;//Tue, 24 Mar 2015 15:30:58 GMT
TimeInterval interval = new TimeInterval(new Date(1427207458), new Date(1427211058));
//1427209258 Tue, 24 Mar 2015 15:00:58 GMT
//1427211898 Tue, 24 Mar 2015 15:44:58 GMT
TimeInterval interval2 = new TimeInterval(new Date(1427209258), new Date(1427211898));
allMeetings.add(interval);
allMeetings.add(interval2);
facebook.hasConflicts(allMeetings);
allMeetings.remove(interval2);
//1427295658 Wed, 25 Mar 2015 15:00:58 GMT
//1427297458 Wed, 25 Mar 2015 15:30:58 GMT
interval2 = new TimeInterval(new Date(1427295658), new Date(1427297458));
allMeetings.add(interval2);
facebook.hasConflicts(allMeetings);
}
public boolean hasConflicts(List<TimeInterval> meetings){
if(meetings != null && !meetings.isEmpty()){
//this meetings could be in any order
Map<String, List<String>> allMeetings = new HashMap<String, List<String>>();
for(TimeInterval interval : meetings){
long currIntervalStartTime = interval.getStartTimeInMillSeconds();
long currIntervalEndTime = interval.getEndTimeInMillSeconds();
String currentIntervalTimeRange = currIntervalStartTime + "-" + currIntervalEndTime;
String currentIntervalDay = interval.getStartMonthDayYear();
List<String> meetingTime = null;
if(allMeetings.containsKey(currentIntervalDay)){
meetingTime = allMeetings.get(currentIntervalDay);
for(String tR : meetingTime){
String[] split = tR.split("-");
long currMeetStartTime = Long.valueOf(split[0]);
long currMeetEndTime = Long.valueOf(split[1]);
if(fallsInRange(currMeetStartTime, currMeetEndTime, currIntervalStartTime)
|| fallsInRange(currMeetStartTime, currMeetEndTime, currIntervalEndTime)){
System.out.println("Meetings have conflicts");
return true;
}
}
}else{
meetingTime = new LinkedList<String>();
}
meetingTime.add(currentIntervalTimeRange);
allMeetings.put(currentIntervalDay, meetingTime);
}
}
System.out.println("No conflicts in meetings.");
return false;
}
public boolean fallsInRange(long startTime, long endTime, long currentValue){
return currentValue >= startTime && currentValue <= endTime;
}
public static class TimeInterval{
public Date startTime;
public Date endTime;
public TimeInterval(Date startTime, Date endTIme){
setStartTime(startTime);
setEndTime(endTIme);
}
public String getStartMonthDayYear(){
return startTime.getMonth()+"/"+startTime.getDay()+"/"+startTime.getYear();
}
public Date getStartTime() {
return startTime;
}
public void setStartTime(Date startTime) {
this.startTime = startTime;
}
public Date getEndTime() {
return endTime;
}
public void setEndTime(Date endTime) {
this.endTime = endTime;
}
public long getStartTimeInMillSeconds(){
return getStartTime().getTime();
}
public long getEndTimeInMillSeconds(){
return getEndTime().getTime();
}
}
}
since time is not defined in this question, I just use integer to represent time. this should be easily convert to any time representation data type.
def IsInrange(value, range):
if value > range[1] and value < range[0]:
return True
else:
return False
def IsMeetingConflict(schedule):
#schedule = [[s1, e1], [s2, e2], [s3, e3]]
for i in schedule:
for j in schedule:
if i != j:
if not IsInrange(i[0], j) or not IsInrange(i[1], j):
return False
return True
How about this?
private boolean isThereAConflict(int[] start, int[] end) {
boolean conflict = false;
int[] hours = new int[24];
for(int i = 0; i < start.length ; i++) {
for(int j = start[i]; j < end[i]; j++) {
if(hours[j] == 1) {
conflict = true;
break;
} else {
hours[j] = 1;
}
}
if(conflict)
break;
}
return conflict;
}
How about this
private boolean isThereAConflict(int[] start, int[] end) {
boolean conflict = false;
int[] hours = new int[24];
for(int i = 0; i < start.length ; i++) {
for(int j = start[i]; j < end[i]; j++) {
if(hours[j] == 1) {
conflict = true;
break;
} else {
hours[j] = 1;
}
}
if(conflict)
break;
}
return conflict;
}
1. Sort intervals by start time
2. Iterate thru intervals
3. Check if current interval's end time is greater than the next interval's start time => conflict
// interval => { start, end }
function checkConflicts(intervals) {
intervals.sort( function (a, b) { return a.start - b.start; });
for (var i = 0; i < intervals.length - 1; i++) {
var curr = interval[i], next = interval[i + 1];
if (curr.end > next.start) {
console.log("conflict:", curr, next);
}
}
}
Here is C++ version of solution, this algorithm assumes the start time and end time of meeting is given as integer. (i.e Mon 2p.m. - 4p.m. will be different from Tue 2p.m. - 4p.m.)
struct sched {
int start;
int end;
sched(int s, int e):start(s), end(e){}
};
bool check_conflict(sched *input, int len)
{
quicksort(input, 0, len-1);
int last = -1;
for (int i = 0; i < len; i++)
{
if (last !=1 && last > input[i].start)
return true;
last = input[i].end;
}
return false;
}
You can sort the list of intervals by starting time first, then traverse the list from beginning to the end and compare the element.
//O(NlogN) for sorting, O(N) for checking bool HasConflict(List<Interval> intervals) { if (intervals == null || intervals.Count == 0) return false; intervals = intervals.OrderBy(x => x.Start).ToList(); for (int i = 0; i < intervals.Count - 1; i++) { if (IsOverlap(intervals.ElementAt(i), intervals.ElementAt(i + 1))) { return true; } } return false; } bool IsOverlap(Interval i1, Interval i2) { if (i1.Start < i2.Start) { return i1.End > i2.Start; } if (i1.Start > i2.Start) { return i1.End < i2.End; } return false; }Testing :
- DP March 30, 2015List<Interval> list = new List<Interval>{ new Interval(1, 3), new Interval(9, 16), new Interval(2, 5) }; List<Interval> list2 = new List<Interval>{ new Interval(1, 3), new Interval(5, 10), new Interval(20, 50) }; Assert.IsTrue(HasConflict(list)); Assert.IsFalse(HasConflict(list2));