• 0

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N*logN). We loose time only on sorting time intervals.

``````public class Event:IComparable<Event>
{
public double Time;
public bool IsStart;

public Event(double time, bool isStart)
{
Time = time;
IsStart = isStart;
}

public int CompareTo(Event other)
{
return Time.CompareTo(other.Time);
}
}

public IEnumerable<double[]> TimeIntervalsSplit(double[][] intervals)
{
var timeLine = new Event[intervals.Length * 2];
for (int i = 0; i < intervals.Length; i++)
{
if (intervals[i].Length != 2 || intervals[i] <= intervals[i]) throw new Exception("Invalid input");
timeLine[i * 2] = new Event(intervals[i], true);
timeLine[i * 2 + 1] = new Event(intervals[i], false);
}
Array.Sort(timeLine);
int depth = 1;
for (int i = 1; i < timeLine.Length; i++)
{
if (timeLine[i].IsStart)
{
if (depth++ > 0) yield return new[] { timeLine[i - 1].Time, timeLine[i].Time };
}
else
{
depth--;
yield return new[] { timeLine[i - 1].Time, timeLine[i].Time };
}
}
}``````

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
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]])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

//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;
}

});
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;
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);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can u explain the interval {2/3-2/20, 2,6-3/5} .. here 2/3 means??

Comment hidden because of low score. Click to expand.
0

These are dates. So 2/3 means February 3rd while 3/5 would mean March 5th.

Comment hidden because of low score. Click to expand.
0
of 0 vote

merge part of the merge sort.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.