Amazon Interview Question
Dev Leads Dev LeadsCountry: India
Not sure if I udnerstand the question correctly, but basically I throw all the start & end points into a set. Then I iterate through the sorted set. If I am at the first element then I set variable "prev" to it. Otherwise I add a new interval (prev, curr) and set prev to be curr + 1 (or the day after curr).
def divide(intervals):
s = set()
for interval in intervals:
s.add(interval[0])
s.add(interval[1])
results = []
prev = None
for d in sorted(s):
if prev == None:
prev = d
else:
results.append([prev, d])
prev = d + 1
return results
print divide([[34, 51], [37, 64]])
//Assumption: Intervals seems like month and day to me.
//Algorithm store all the half intervals into the priority Queue and assemble them by retrieving one by one appending start one to the previous one as end date afterwards incrementing the start interval
public class SplitIntervals {
final static int [] MONTH_DAYS = new int [] { 31,27,31,30,31,30,31,31,30,31,30,31};
private static class Interval {
int startDay;
int startMonth;
int endDay;
int endMonth;
Interval(int startMonth,int startDay,int endDay,int endMonth) {
this.startDay = startDay;
this.startMonth = startMonth;
this.endDay = endDay;
this.endMonth = endMonth;
}
@Override
public String toString() {
return String.format("%d/%d - %d/%d",startMonth,startDay,endMonth,endDay);
}
}
public static void main(String[] args) {
PriorityQueue<Interval> intervalQueue = new PriorityQueue<>(10,new Comparator<Interval>() {
@Override
public int compare(Interval o1, Interval o2) {
// sort by start interval
int diff = o1.startMonth - o2.startMonth;
if(diff!=0) return diff;
diff = o1.startDay - o2.startDay;
if(diff!=0) return diff;
return 0;
}
});
intervalQueue.add(new Interval(2,3,-1,-1));
intervalQueue.add(new Interval(2,20,-1,-1));
intervalQueue.add(new Interval(2,6,-1,-1));
intervalQueue.add(new Interval(3,5,-1,-1));
Interval currentInterval = intervalQueue.poll();
List<Interval> splitIntervals = new ArrayList<>();
while(!intervalQueue.isEmpty()) {
Interval nextInterval = intervalQueue.poll();
//set this interval start day and end Month to be end day and end Month
currentInterval.endDay = nextInterval.startDay;
currentInterval.endMonth = nextInterval.startMonth;
splitIntervals.add(currentInterval);
currentInterval = nextInterval;
currentInterval.startDay++;
if(currentInterval.startDay > MONTH_DAYS[currentInterval.startMonth-1]) {
currentInterval.startMonth++;
currentInterval.startDay = 1;
}
if(currentInterval.startMonth > 12) {
currentInterval.startMonth = 1;
}
}
System.out.println(splitIntervals);
typedef int date_t; // or use any comparable date class
class Interval
{
public:
Interval(date_t _start, date_t _end): start(_start), end(_end) {};
date_t start;
date_t end;
};
void split(const std::vector<Interval>& in, std::vector<Interval>& out)
{
std::vector<date_t> dates;
for (auto i : in)
{
dates.push_back(i.start);
dates.push_back(i.end);
}
std::sort(std::begin(dates), std::end(dates));
auto start = *std::begin(dates);
for (auto i : dates)
{
if (i == start) continue;
out.push_back(Interval(start, i));
start = i + 1;
}
}
// usage
std::vector<Interval> in, out;
in.push_back(Interval(6, 25));
in.push_back(Interval(3, 20));
split(in, out);
O(N*logN). We loose time only on sorting time intervals.
You might want to mess a bit with the resulting intervals edges if you want the previous closing time to be less than the next opening time. But I see no difficulties doing so.
- vladimir.grebennikov December 11, 2014