Microsoft Interview Question
Country: United States
One line python solution. This is highly optimized and thoroughly tested:
return sum(maxPoints)
This gives even better result than in the example above.
Time complexity: O(N), space complexity: O(N)
Explanation: start all tasks at 0 minutes (specification of the problem doesn't forbid this)
Anyone can do better :) ?
Brute Force, Recursive, C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Task {
int maxPoint;
int pointsPerMinute;
int requiredTime;
int visit;
Task() {
maxPoint = 0;
pointsPerMinute = 0;
requiredTime = 0;
visit = 0;
}
};
void processInput(int& totalTime, vector<Task>& tasks) {
string buffer;
int taskIndex, i, t;
cin >> totalTime;
cin >> buffer;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
Task task;
task.maxPoint = t;
tasks.push_back(task);
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
cin >> buffer;
taskIndex = 0;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
tasks[taskIndex].pointsPerMinute = t;
taskIndex++;
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
cin >> buffer;
taskIndex = 0;
i = 0;
t = 0;
while (i <= (int)buffer.size()) {
if (i == buffer.size() || buffer[i] == ',') {
tasks[taskIndex].requiredTime = t;
taskIndex++;
t = 0;
} else {
t = t * 10 + (buffer[i] - '0');
}
i++;
}
}
int solve(int totalTime, vector<Task>& tasks, int time) {
int ret, i, point;
if (time >= totalTime) return 0;
ret = 0;
for (i = 0; i < (int)tasks.size(); i++) {
if (tasks[i].visit == 1) continue;
tasks[i].visit = 1;
point = tasks[i].maxPoint - (time + tasks[i].requiredTime) * tasks[i].pointsPerMinute;
ret = max(ret, point + solve(totalTime, tasks, time + tasks[i].requiredTime));
tasks[i].visit = 0;
}
return ret;
}
int main(int argc, char* argv[]) {
vector<Task> tasks;
int totalTime;
processInput(totalTime, tasks);
cout << solve(totalTime, tasks, 0) << "\n";
return 0;
}
Just do it using the dynamic programming approach. O(n * T) complexity and O(T) memory where n is the number of tasks and T is the amount of time
public static int getMaxScore(int[] taskValue, int[] taskTime, int totalTime){
int[] timeScore = new int[totalTime];
int[] nextTimeScore = new int[totalTime];
int[] temp;
for(int i = 0; i < taskValue.length; i++){
int taskTimeHere = taskTime[i];
int taskValueHere = taskValue[i];
for(int j = 0; j < totalTime; j++){
if(taskTimeHere > j){
int thisTask = taskValueHere + nextTimeScore[j + 1 - taskTimeHere];
nextTimeScore[j] = Math.max(thisTask, timeScore[j]);
}
else{
nextTimeScore[j] = timeScore[j];
}
}
temp = nextTimeScore;
nextTimeScore = timeScore;
timeScore = temp;
}
return timeScore[totalTime -1];
}
I considered all the combinations of requiredTime[i] * pointsPerMinute[i] and found the minimum sum of that combination. I think this can be further optimized by cutting out branches in the recursion once a decent minimum sum of products is reached to be compared.
public class GetMaxPoints {
public static void main(String args[]) {
int[] maxPoints = {250, 500, 1000};
int[] pointsPerMinute = {2,4,8};
int[] requiredTime = {25,25,25};
System.out.println(getMaxPoints(maxPoints, requiredTime, pointsPerMinute));
}
public static int getMaxPoints(int[] maxPoints, int[] requiredTime, int[] pointsPerMinute) {
int sumMaxPoints = 0;
for (int i = 0; i < maxPoints.length; i++) {
sumMaxPoints = sumMaxPoints + maxPoints[i];
if (i != 0)
requiredTime[i] += requiredTime[i-1];
}
return (sumMaxPoints - findMin(requiredTime,pointsPerMinute, 0, 0, sumMaxPoints));
}
public static int findMin(int[] requiredTime, int[] pointsPerMinute, int timeIndex, int sum, int minSum) {
if(timeIndex == requiredTime.length - 1) {
sum+= requiredTime[timeIndex] * pointsPerMinute[0];
if (sum< minSum) return sum;
else return minSum;
}
for (int j = 0; j < pointsPerMinute.length; j++) {
int sumResult = findMin(requiredTime,
removeFromArray(j, pointsPerMinute),
timeIndex + 1,
sum + requiredTime[timeIndex] * pointsPerMinute[j],
minSum);
if ( sumResult < minSum)
minSum = sumResult;
}
return minSum;
}
public static int[] removeFromArray(int itemIndexToRemove, int[] array) {
List<Integer> result = new LinkedList<Integer>();
for( int item : array) {
if (array[itemIndexToRemove] != item) result.add(item);
}
int[] newArray = new int[array.length - 1];
for (int i = 0; i < newArray.length; i++) { newArray[i] = result.get(i); }
return newArray;
}
}
Same as permutation problem
//
// main.cpp
// maximum_points
//
// Created by Sai krishna Ravipati on 10/2/15.
// Copyright (c) 2015 Sai krishna Ravipati. All rights reserved.
//
#include <iostream>
//#include <algorithm>
using namespace std;
namespace Mine {
template <typename T>
void swap(T &a, T &b) {
T temp = a;
a = b;
b = temp;
}
}
int calculate_max_pts(int *points, int *points_per_min, int *time,
int current, int N, int total_time, int starting_time) {
int max = 0;
int cur_max = 0;
int returned_max = 0;
for (int i = current; i < N; i++) {
Mine::swap(points[i], points[current]);
Mine::swap(points_per_min[i], points_per_min[current]);
Mine::swap(time[i], time[current]);
if (time[current] <= total_time) {
returned_max = calculate_max_pts(points, points_per_min, time, current + 1, 3, total_time- time[current], starting_time + time[current]);
cur_max = points[current] - ((starting_time + time[current]) * points_per_min[current]) + returned_max;
if (max < cur_max) {
max = cur_max;
}
}
Mine::swap(points[i], points[current]);
Mine::swap(points_per_min[i], points_per_min[current]);
Mine::swap(time[i], time[current]);
}
return max;
}
int main(int argc, const char * argv[]) {
// insert code here...
int points[3] = {1000,500,250};
int points_per_min[3] = {8,4,2};
int time[3] = {25, 25,25};
int max_points = calculate_max_pts(points, points_per_min, time, 0, 3, 75, 0);
std::cout << max_points << endl;
getchar();
return 0;
}
STEP1:
Do a binary search on MaxPoints[] and select T such that this value is maximized
MaxPoint(T) - RequiredTime(T) * PointsPerMinute
STEP2:
Select this T and remove it from MaxPoints[].
Update totalpoints based on this T
Update timeleft
STEP3:
while timeleft > 0 and MaxPoints has T, repeat step1
Runtime should be nlogn
STEP1:
Assingn each Task weights based on following formulas. Formula takes everything into account and comes at optimal task weight:
tasks[i].TaskWeight1 = ((Double) (MaxPoints[i] - RequiredTime[i]*PointsPerMin[i]))/T;
tasks[i].TaskWeight2 = (Double) (MaxPoints[i] - RequiredTime[i]*PointsPerMin[i]);
STEP2:
Then sort the tasks by TaskWeight1 descending order.
If two tasks has same weight, then sort those based on Second weight calculated above with higher task weight comes first.
STEP3:
Process the tasks in sort order.
Assign the weight to each task based on Points earned per min using the formula:
- Pkar December 11, 2015tasks[i].TaskWeight = ((Double) (MaxPoints[i] - RequiredTime[i]*PointsPerMin[i]))/T;
Then chose the task that has highest weight to be done first followed by tasks with lower weight. This way the points earned per task completion can be maximized..