Interview Question
Country: United States
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
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;
}
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;
}
Idea:
- Lem December 06, 2013START 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.