Facebook Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Also make sure to do the last check with the last entry's end time with first entry's start time.
This algorithm just work for this case:
1-3 2-4 3-7 6-2
However does not work for
1-7 2-4 3-5
nor
1-4 5-6 3-2
Maintain a bitset of size(7*24*60*60) i.e. num of seconds in a week.
Now, for each interval, mark these bits true.
In the end, if all bits are 1, then the entire week is covered, else not.
Assuming the input to be number of seconds since Sunday 00:00:00, there will be 2
Special cases:
1. an interval spans more than a week, we need to immediately return true.
2. an interval starts at let's say friday and ends on tuesday next week.
For this, we need to set bits for friday-saturday night, and shift offsets of sunday-tuesday by 7*24*60*60
This algorithm makes use of minimum heap to short the non-crossing interval (here after extent).
One assumption this algorithm makes is that 00:00:00 of last day of week equals to (7*24*60*60).
This algorithm divide input intervals into two groups:
1) non-crossing intervals, where start < end
2) crossing intervals where start > end
Running Time will be O(N log N) due to the heap operations (add, extract), where N is the number of input intervals.
Any suggestions or critics are welcomed.
struct extent {
int start;
int end;
extent ():start(-1), end(MAX_INT32){}
}
bool is_overlap(extent* list, int n)
{
int c_start = -1; c_end = MAX_INT32;
MinHeap heap;
for(int i = 0; i < n; i++)
{
if (list[i].start == list[i].end)
return true;
else if (list[i].start < list[i].end)
heap.add(list[i]);
else {
if (c_start < list[i].start)
c_start = list[i].start;
if (c_end > list[i].end)
c_end = list[i].end;
}
}
bool no_cross = false;
no_cross = (c_start == -1);
extent *min;
while (heap.len() > 0)
{
min = heap.extract();
if (no_cross) {
if (c_start == -1)
{
c_start = min->start;
c_end = min->end;
} else if (c_start < min->start)
return false;
else
c_end = min->end;
} else {
if (c_start < min.start)
return false;
else
c_start = min.end;
}
}
return (c_start == 0 && c_end == END_OF_WEEK) || (c_start >= c_end);
}
Can be solved using a balanced BST, such as Redblack tree (Using TreeSet in java). Running time is O(N) in number of events in the input.
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.TreeSet;
public class WeekSchedule {
private static final int SECONDS_IN_WEEK = 60*60*24*7;
private TreeSet<Event> treeSet = new TreeSet<Event>();
public void addEvent(String start, String end) {
addRange(convertToInt(start), convertToInt(end));
}
public boolean spansWeek() {
int secSum = 0;
if (treeSet == null) {return false;}
for (Event pair : treeSet) {
secSum = secSum + (pair.end - pair.start + 1);
}
return secSum == SECONDS_IN_WEEK;
}
private void addRange(int start, int end) {
if (end<start) {
//split into 2 events, does not matter because they are recurring anyway
addRange(start, SECONDS_IN_WEEK);
addRange(1, end % SECONDS_IN_WEEK);
return;
}
Event newPair = new Event(start, end);
if (treeSet.isEmpty()) {
treeSet.add(newPair);
return;
}
Event ceiling = treeSet.ceiling(new Event(end,end));
if (ceiling == null) {ceiling = treeSet.last();
}
Event floor = treeSet.floor(new Event(start, start));
if (floor == null) {floor = treeSet.first();}
Event rangeLeft = null;
Event rangeRight = null;
if (newPair.compareTo(floor) == -1
|| newPair.compareTo(ceiling) == 1) {
treeSet.add(newPair);
} else {
if (floor.inRange(newPair.start)) {
rangeLeft = floor;
newPair = new Event(floor.start, newPair.end);
} else {
rangeLeft = newPair;
}
if (ceiling.inRange(newPair.end)) {
rangeRight = ceiling;
newPair = new Event(newPair.start, ceiling.end);
} else {
rangeRight = newPair;
}
treeSet.removeAll(treeSet.subSet(rangeLeft, rangeRight));
treeSet.remove(rangeRight);
}
treeSet.add(newPair);
}
public static final class Event implements Comparable<Event> {
private int start = 0;
private int end = 0;
public Event(int left, int right) {
super();
this.start = left;
this.end = right;
}
public boolean inRange(int num) {
return num >= start && num <= end;
}
@Override
public int compareTo(Event o) {
if (this.end < o.start) {
return -1;
} else if (o.end < this.start) {
return 1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Pair [" + start + ", " + end + "]";
}
}
private int convertToInt(String eventTime) {
SimpleDateFormat dateFormat = new SimpleDateFormat("E HH:mm:ss");
Calendar calendar = Calendar.getInstance();
try {
calendar.setTime(dateFormat.parse(eventTime));
} catch (ParseException e) {
throw new RuntimeException("wrong date");
}
int seconds = (calendar.get(Calendar.DAY_OF_WEEK) - 1) * 60*60*24;
seconds = seconds + calendar.get(Calendar.HOUR_OF_DAY) * 3600
+ calendar.get(Calendar.MINUTE) * 60
+ calendar.get(Calendar.SECOND);
return seconds;
}
}
Can be solved using a balanced BST, such as Redblack tree (Using TreeSet in java). Running time is O(N) in number of events in the input.
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.TreeSet;
public class WeekSchedule {
private static final int SECONDS_IN_WEEK = 60*60*24*7;
private TreeSet<Event> treeSet = new TreeSet<Event>();
public void addEvent(String start, String end) {
addRange(convertToInt(start), convertToInt(end));
}
public boolean spansWeek() {
int secSum = 0;
if (treeSet == null) {return false;}
for (Event pair : treeSet) {
secSum = secSum + (pair.end - pair.start + 1);
}
return secSum == SECONDS_IN_WEEK;
}
private void addRange(int start, int end) {
if (end<start) {
//split into 2 events, does not matter because they are recurring anyway
addRange(start, SECONDS_IN_WEEK);
addRange(1, end % SECONDS_IN_WEEK);
return;
}
Event newPair = new Event(start, end);
if (treeSet.isEmpty()) {
treeSet.add(newPair);
return;
}
Event ceiling = treeSet.ceiling(new Event(end,end));
if (ceiling == null) {ceiling = treeSet.last();
}
Event floor = treeSet.floor(new Event(start, start));
if (floor == null) {floor = treeSet.first();}
Event rangeLeft = null;
Event rangeRight = null;
if (newPair.compareTo(floor) == -1
|| newPair.compareTo(ceiling) == 1) {
treeSet.add(newPair);
} else {
if (floor.inRange(newPair.start)) {
rangeLeft = floor;
newPair = new Event(floor.start, newPair.end);
} else {
rangeLeft = newPair;
}
if (ceiling.inRange(newPair.end)) {
rangeRight = ceiling;
newPair = new Event(newPair.start, ceiling.end);
} else {
rangeRight = newPair;
}
treeSet.removeAll(treeSet.subSet(rangeLeft, rangeRight));
treeSet.remove(rangeRight);
}
treeSet.add(newPair);
}
public static final class Event implements Comparable<Event> {
private int start = 0;
private int end = 0;
public Event(int left, int right) {
super();
this.start = left;
this.end = right;
}
public boolean inRange(int num) {
return num >= start && num <= end;
}
@Override
public int compareTo(Event o) {
if (this.end < o.start) {
return -1;
} else if (o.end < this.start) {
return 1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Pair [" + start + ", " + end + "]";
}
}
private int convertToInt(String eventTime) {
SimpleDateFormat dateFormat = new SimpleDateFormat("E HH:mm:ss");
Calendar calendar = Calendar.getInstance();
try {
calendar.setTime(dateFormat.parse(eventTime));
} catch (ParseException e) {
throw new RuntimeException("wrong date");
}
int seconds = (calendar.get(Calendar.DAY_OF_WEEK) - 1) * 60*60*24;
seconds = seconds + calendar.get(Calendar.HOUR_OF_DAY) * 3600
+ calendar.get(Calendar.MINUTE) * 60
+ calendar.get(Calendar.SECOND);
return seconds;
}
}
Using Balanced BST to merge ranges (TreeSet in java)
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.TreeSet;
public class WeekSchedule {
private static final int SECONDS_IN_WEEK = 60*60*24*7;
private TreeSet<Event> treeSet = new TreeSet<Event>();
public void addEvent(String start, String end) {
addRange(convertToInt(start), convertToInt(end));
}
public boolean spansWeek() {
int secSum = 0;
if (treeSet == null) {return false;}
for (Event pair : treeSet) {
secSum = secSum + (pair.end - pair.start + 1);
}
return secSum == SECONDS_IN_WEEK;
}
private void addRange(int start, int end) {
if (end<start) {
//split into 2 events, does not matter because they are recurring anyway
addRange(start, SECONDS_IN_WEEK);
addRange(1, end % SECONDS_IN_WEEK);
return;
}
Event newPair = new Event(start, end);
if (treeSet.isEmpty()) {
treeSet.add(newPair);
return;
}
Event ceiling = treeSet.ceiling(new Event(end,end));
if (ceiling == null) {ceiling = treeSet.last();
}
Event floor = treeSet.floor(new Event(start, start));
if (floor == null) {floor = treeSet.first();}
Event rangeLeft = null;
Event rangeRight = null;
if (newPair.compareTo(floor) == -1
|| newPair.compareTo(ceiling) == 1) {
treeSet.add(newPair);
} else {
if (floor.inRange(newPair.start)) {
rangeLeft = floor;
newPair = new Event(floor.start, newPair.end);
} else {
rangeLeft = newPair;
}
if (ceiling.inRange(newPair.end)) {
rangeRight = ceiling;
newPair = new Event(newPair.start, ceiling.end);
} else {
rangeRight = newPair;
}
treeSet.removeAll(treeSet.subSet(rangeLeft, rangeRight));
treeSet.remove(rangeRight);
}
treeSet.add(newPair);
}
public static final class Event implements Comparable<Event> {
private int start = 0;
private int end = 0;
public Event(int left, int right) {
super();
this.start = left;
this.end = right;
}
public boolean inRange(int num) {
return num >= start && num <= end;
}
@Override
public int compareTo(Event o) {
if (this.end < o.start) {
return -1;
} else if (o.end < this.start) {
return 1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Pair [" + start + ", " + end + "]";
}
}
private int convertToInt(String eventTime) {
SimpleDateFormat dateFormat = new SimpleDateFormat("E HH:mm:ss");
Calendar calendar = Calendar.getInstance();
try {
calendar.setTime(dateFormat.parse(eventTime));
} catch (ParseException e) {
throw new RuntimeException("wrong date");
}
int seconds = (calendar.get(Calendar.DAY_OF_WEEK) - 1) * 60*60*24;
seconds = seconds + calendar.get(Calendar.HOUR_OF_DAY) * 3600
+ calendar.get(Calendar.MINUTE) * 60
+ calendar.get(Calendar.SECOND);
return seconds;
}
}
@Test
public void test() {
weekSched.addEvent("Tue 09:00:00", "Tue 22:00:00");
weekSched.addEvent("Tue 09:00:00", "Thu 22:00:00");
weekSched.addEvent("Sun 00:00:00", "Tue 08:59:59");
weekSched.addEvent("Wed 15:00:00", "Fri 22:00:00");
weekSched.addEvent("Wed 15:00:00", "Fri 22:00:00");
weekSched.addEvent("Fri 22:00:00", "Sat 23:59:59");
boolean actual = weekSched.spansWeek();
logger.info("Spans week? {}", actual?"yes":"no");
assertTrue(actual);
}
Step 1: Sort the time interval based on starting time
- Anonymous April 17, 2015Step 2: Iterate through sorted interval and compare each interval with next interval and see whether it overlaps or not. if all interval overlaps entire time is covered