Interview Question


Country: United States




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

Idea:
START and END should come in pairs, Like START1 - END1, ... START5 START6 ... END6 ... END5....
So, we need to find all intervals between pair-closed END (END5, not END6) and next START .
From this intervals, choose the longest one.

- Lem December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

kjjh

- Anonymous December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is to get all gaps between the endtime and start time first and then prune the list...

have a set to strore endtimes less than starttimes. a potential list of idle times, we need to do another loop from this set, compaing across other set of times to get the final idle time..

Given a log with sorted start time..
Have the sorted start times in an array S[] and the corresponding EndTimes in E[]

int[,] tempAllGaps=new int[s.length][2];
int x=0;
for(int i=0;i<S.Length;i++){
if(E[I]<S[I+1]) {
tempAllGaps[x][0]=E[i];
tempAllGaps[x++][1]=S[i+1];

}	
}
//Now tempAllGaps has all gaps, loop thro and find if there is a set where starttime is less than or equal to tempAllGaps[][0] and it there is an endtime greater thatn or equal to tempAllGaps[][1], this will get the list idle machine time

- Anonymous December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in O(n) time, written in C++.

Input:

10:20 - 10:30
11:10 - 11:30
11:20 - 12:40
11:30 - 13:00

Output:

Longest slot is between 11:10 and 13:00

Code:

#include <iostream>
#include <vector>
#include <stdexcept>
#include <limits>

struct log_entry {
	log_entry(int start, int end) : start_(start), end_(end) { }
	
	int start_;
	int end_;
};

std::pair<int, int> longest_slot(const std::vector<log_entry>& entries) {
	if (entries.empty())
		throw std::invalid_argument("log entries must not be empty");
    
	int min_start = 0;
	int max_end = 0;
	int max_diff = 0;
	
	int cur_start = -1;
	int cur_end = -1;
	
	for (size_t i = 0; i < entries.size(); i++) {
		const log_entry& entry = entries[i];

        // Current entry not yet set?
        if (cur_start == -1 && cur_end == -1) {
            cur_start = entry.start_;
            cur_end = entry.end_;
        }

        // Is this entry starting between the last slot?
        if (entry.start_ >= cur_start && entry.start_ <= cur_end) {
            cur_start = std::min(cur_start, entry.start_);
            cur_end = std::max(cur_end, entry.end_);
        } else {
            cur_start = entry.start_;
            cur_end = entry.end_;
        }

        // Update maximum diff
        if (cur_end - cur_start > max_diff) {
            min_start = cur_start;
            max_end = cur_end;
            max_diff = max_end - min_start;
        }
	}
	
	return std::make_pair(min_start, max_end);
}

/**
 * Using a log generated by a multiprocessor machine, which contains start and
 * end time of each process, find the longest slot of time in which the machine
 * wasn't idle. The log is sorted by the process's start time.
 */
int main() {
	std::vector<log_entry> entries{{1000, 1100},
        {1020, 1030},
        {1110, 1130},
        {1120, 1240},
        {1130, 1300}};
	std::pair<int, int> r = longest_slot(entries);
	std::cout << "Longest slot is between " << r.first << " and " << r.second << std::endl;
	return 0;
}

- Diego Giagio December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution O(N) psuedo code:

Since all start times are sorted, we can iterate through to find subsequent working slots and compare with max found so far. return max

psuedo:

log {
timeStamp start;
timeStamp end;
}

getMaxWorkingSlot(log[] logs) {

	int maxNotIdle=0 //seconds
	log previous;
	for (log l : logs) { 
		if (previous==null)
			previous = l;
			maxNotIdle = l.end-l.start;
			continue;
		if (l.start>previous.end)
			previous = l;
			if (maxNotIdle<l.end-l.start)
				maxNotIdle=l.end-l.start;
		else
			if (l.end>previous.end)
				previus.end=l.end;
				int notIdle = previous.end – previous.start
				if (notIdle>maxNotIdle)
					maxNotIdle=notIdle;
	}

return maxNotIdle;
}

- gumanji December 07, 2013 | 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