Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Here is a DP approach.
Arrange the tasks in some order (any order)
Let M(i) denote the maximum work done using the first i tasks.
We need to find the value of M(n).
To do this let's say we need to calculate M(i+1) from M(i)
If inserting (i + 1)th task in the previous max sequence increases the Max work spent, then change the sequence and include this (i+1)th task in the already existing sequence.
If inserting (i + 1)th task in the previous max sequence is equal to the M(i) then keep both sequences.
Therefore M(i) will not be a single sequence but there might be a list of tasks all with same max work value
This is exact replica of 'Avid TV watcher' problem. A very detailed code with explanation is present here:
bit.ly/1dztZFM
This, in its most general form, seems like a CSP, or SAT problem. I would go for the standard branch and prune/bound.
Each work Wi has a payoff of Ti. If two works overlap then they cannot be chosen together
One way to formulate:
Maximize T1 W1 + T2 W2 + .... + T5 W5
Subject to: not(W1 & W2) = true
not(W2 & W3) = true
not(W2 & W4) = true
not(W2 & W5) = true
not(W3 & W5) = true
This is a rough sloppy implementation without bounding.
function payoff = solve(k, w)
if (k > N)
p = get_pay_off(w)
if (p > pmax)
pmax = p;
wmax = w;
end
return p;
end
w[k] = 1;
p1 = solve(k + 1, w);
w[k] = 0;
p2 = solve(k + 1, w);
return (max(p1, p2))
end
You can add a bounding method to make the algorithm faster. This is usually obtained by relaxing the binary variables and solving the LP to obtain the upperbound. If the upper bound on payoff is less than best solution so far, our assumption for wk is wrong or there is no solution.
Naive solutions:
--------------------
a) Sort on the basis of starting time. If two Work have same start time, list the one with smaller end time first.
b) In the sorted result, list all non conflicting schedules.
c) For all non-conflicting schedules, find the total minutes/hours obtained. Choose the maximum of them.
For example 2:
Sort (Start time) := W1 W4 W2 W6 W5 W3
List of non conflicting schedules:
W1
W1 W2 W3
W1 W6 W3
W1 W3 (valid, but this can be avoided since other schedule having a work between W1 and W3 would yield higher output).
W1 W5
W4 W2 W3
W4 W6 W3
W4 W5 and so on.
THe maximum of these is W1 W6 W3 with 6.5 hours.
Can someone suggest an optimization over this?
1. Sort the work items by their start times.
2. Proceed the solution through backtracking.
3. At each stage, possible candidates are next item just after the last item, and all other work items overlapping with first item.
4. When all items are processed, compare them with max solution. If it is greater than Max, store this value in Max.
typedef struct _Work
{
string name;
string start;
string end;
_Work( string name1, string start1, string end1 )
{
name = name1;
start = start1;
end = end1;
}
_Work()
{
name = "";
start = "00:00";
end = "00:00";
}
}Work;
vector<Work> sortWorks( vector<Work> input )
{
vector<Work> output;
while( input.size() > 0 )
{
int min_index = 0;
for( unsigned int i = 1; i < input.size(); i++ )
{
if( input[i].start.compare( input[min_index].start ) < 0 )
min_index = i;
}
output.push_back( input[min_index] );
input.erase( input.begin() + min_index );
}
return output;
}
vector<Work> maxDay;
int maxMinutes;
vector<Work> getNextPossibleCandidates( Work w, vector<Work> remaining )
{
vector<Work> output;
string starttime = w.start;
string endtime = "";
for( int i = 0; i < remaining.size(); i++ )
{
if( endtime.empty() )
endtime = remaining[i].end;
if( remaining[i].start.compare( endtime ) > 0 )
break;
output.push_back( remaining[i] );
}
return output;
}
int getMinutes( Work w )
{
int start = atoi( w.start.substr( 0, 2 ).c_str() ) * 60 + atoi( w.start.substr( 3, 2 ).c_str() );
int end = atoi( w.end.substr( 0, 2 ).c_str() ) * 60 + atoi( w.end.substr( 3, 2 ).c_str() );
return end-start;
}
void maximizeSchedule( vector<Work> tillNow, vector<Work> remaining )
{
Work lastWork;
if( tillNow.size() > 0 )
lastWork = tillNow[tillNow.size() - 1];
vector<Work> candidates = getNextPossibleCandidates( lastWork, remaining );
if( candidates.size() == 0 )
{
int thisValue = 0;
for( int i = 0; i < tillNow.size(); i++ )
thisValue += getMinutes( tillNow[i] );
if( ( maxDay.size() == 0 ) || ( thisValue > maxMinutes ) )
{
maxDay = tillNow;
maxMinutes = thisValue;
}
}
for( int i = 0; i < candidates.size(); i++ )
{
vector<Work> tempTillNow = tillNow;
vector<Work> tempRemaining = remaining;
int j = 0;
for( j = 0; j < remaining.size(); j++ )
{
if( remaining[j].start.compare( candidates[i].end ) > 0 )
break;
}
tempTillNow.push_back( candidates[i] );
tempRemaining.erase( tempRemaining.begin(), tempRemaining.begin() + j );
maximizeSchedule( tempTillNow, tempRemaining );
}
}
void getMaxSchedule( vector<Work> v )
{
vector<Work> tillNow;
vector<Work> sorted = sortWorks( v );
maximizeSchedule( tillNow, sorted );
}
You could treat this problem like a directed graph, giving each edge weight a value equal to the minutes of work it takes to complete. While constructing the graph, if an end time is greater than a start time then that edge cannot exist.
Next identify the vertices that have no incoming paths. These will be the possible start nodes of any possible greatest path.
Then you can do a breadth first search through the graph starting at each possible START node and maintaining a longest path (biggest time) that is compared at the end of each BFS iteration. At the end, you simply reproduce the longest path and it's value.
I am curious about the question statement "maximum work minutes"...
If it's finding maximum work minutes we can just simply do a Greedy Algorithm sorting by end time...
Algorithm:
1. Sort by end time of each work.
2. Start by getting the latest time, check this work's starting time
3. proceed to add the next work whose end time < then this work's starting time.
4. repeat
Since it's maximum number of MINUTES worked NOT maximum works done, we would have a possible solution that picks only one long work...But it seems to be right. Any suggestions?
Looks very simple..
1. Sort the values. Lets we have sorted array Times[]
2. Take one more array to save SelectedTime[]
3. SelectedTime[0] = Times[0]
4. Loop on Times Start with 1
a. IF SelectedTime[SelectedTime.Count-1] overlap Times[i] AND Times[i];s total minutes > SelectedTime[SelectedTime.Count-1]
b. THEN SelectedTime[SelectedTime.Count-1]= Times[i];
c. IF Not Overlap THEN SelectedTime[SelectedTime.Count]= Times[i]; here we are adding one more time.
Hi,
For me it sounds like a greedy approach:
Firstly sort all the works according to it's start time in an increasing order, then according to the finish time in an decreasing one. So what you do now: take the first event that appears, let's name the start time S(i) and finish time E(i). Now take the first event that S(i+1) > E(i). If there are several events starting at the same time take the one that E(i+1) has the largest value (because we are trying to find the longest time). Proceed till the end.
Incorrect solution. Consider this:
W1: 01:00 - 03:00
W2: 04:00 - 08:00
W3: 02:00 - 10:00
@Hector, you are right. This can be done in O(n) using greedy approach. Although, DP solution is also available, it is O(n^2). However, we should sort the entries based on their finishing times and look for the compatible tasks that satisfy Start[m]>=Finish[i] and the m task to our list of accepted tasks.
Weighted interval Scheduling Problem with each weght = length of the interval.
- pranayhasan August 23, 2013