Amazon Interview Question for Dev Leads Dev Leads


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][1] <= intervals[i][0]) throw new Exception("Invalid input");
        timeLine[i * 2] = new Event(intervals[i][0], true);
        timeLine[i * 2 + 1] = new Event(intervals[i][1], 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.

- vladimir.grebennikov December 11, 2014 | Flag Reply
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:
        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]])

- Sunny December 12, 2014 | Flag Reply
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;
			}
			
		});
		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);

- naren December 12, 2014 | Flag Reply
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??

- Vijay December 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Sunny December 16, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

merge part of the merge sort.

- aa January 26, 2015 | Flag Reply
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);

- Omri.Bashari May 18, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More