Microsoft Interview Question
Software ArchitectsTeam: Bangalore
Country: United States
Interview Type: Phone Interview
I took a bit of your idea and came up with this. It works in my test:
int max_marks(int nitems,int max,int marks[],int time[]) {
int i,j,val,k;
for(i=0;i<=nitems;i++)
{
for(j=0;j<=max;j++) {
matrix[i][j] = INT_MAX;
}
}
for(i=1;i<= nitems;i++) {
val=0;
for(k=1;k<= i; k++)
val+= marks[k-1];
for(j=0;j<=max;j++) {
if(j>val) break;
if(marks[i-1] > j)
matrix[i][j]=matrix[i-1][j];
else {
if(matrix[i-1][j-marks[i-1]] == INT_MAX)
matrix[i][j] = time[i-1];
else
matrix[i][j]= min(matrix[i-1][j],time[i-1]+matrix[i-1][j-marks[i-1]]);
}
}
}
return matrix[nitems][max];
}
I think something like this should do:
int bestIndex = -1;
int bestTime = Integer.MAX_VALUE;
for (int i = 0; i < marks.length; i++) {
if (marks[i] >= P && times[i] < bestTime) {
bestTime = times[i];
bestIndex = i;
}
}
return bestIndex;
or you meant to order them? In that case, again, you copy in a new array (in O(n)) the ones with mark bigger than P, and then sort by time.
I am not actually sure that I understand your solution :D But to me, it seems like a greedy algorithm.
My best bet would be that this task is a variation on the knapsack problem (google it for details). So the dynamic programming solution would go like this:
- create the DP table [0..P, 0..T_MAX] where T_MAX is the time needed to complete all tasks
- fill up the 0th row and column with -1s or NULL or some other illegal value
- each cell would contain the task which one should do FIRST given the available time t and the points P, and the time it would take to get at least P points while minimizing the time (I know my explanation is kinda awkward here, but if you solve the knapsack problem you'll know what I'm talking about :)), OR -1 if the solution does not exist
- minimize the solution on the time for each cell
Your solution, from what I was able to understand of it, is correct only in the case where you are allowed to partially attempt a problem and receive partial credit for problems based on the fraction of the problem that was completed. If you can only receive credit for a problem once it's fully completed, the greedy algorithm is not correct.
Consider the possibility of having three tasks specified as (points, time): (50, 50), (45, 30), (45, 30). Then suppose you have 50 minutes total. While the second and third tasks offer you 1.5 points / minute vs. the first task's 1 point / minute, it's better to take the first task, since you'll be able to use your entire time scoring points that way.
The solution in this case would need to use the normal methods for solving the knapsack problem.
We have to use DP to solve this problem, the greedy approch which you have given is not correct
Here is the example
input
Q -> 1, 2, 3
M -> 6, 7, 14
T -> 3, 3.5, 6.5
P = 15
According to your algorithm, the minimum t will be 9.5 and user attempt first and third question
but more optiomal solution is 6.5, when user attempt first and second questions.
So, so solve such cases, we use DP
Here is the logic
M <- as input Marks array
T <- as input time array
Let C(i,j) repersents the minumum time to get i marks using first j questions.
C(i,j) = Infinity if i > 0 and j = 0
C(i,j) = 0 if i = 0 // Consider negative value of i and j as 0
C(i,j) = min(C(i,j-1), C(i-M[j],j-1) + T[j])
we can use buttom up approch to solve the value C(P,N) if P is the needed marks and N is the size of the array
Complexity: Both space and Time complexity are O(PN)
Here is the code
using System;
namespace DynamicProgramming
{
public class Question
{
public int marks;
public int timeRequiredToComplete; // in minutes
}
public static class Program
{
public static void Main(string[] args)
{
int questionCount = 3;
Question[] questions = new Question[questionCount];
var random = new Random();
for(int i = 0; i < questionCount; i++)
{
questions[i] = new Question() { marks = random.Next(1, 15), timeRequiredToComplete = random.Next(1, 60) };
}
int passingMarks = random.Next(1,20);
FindQuestionswithMinimumTime(questions,passingMarks);
Console.ReadLine();
}
public static void FindQuestionswithMinimumTime(Question[] questions,int passingMarks)
{
if(questions == null)
{
throw new ArgumentNullException();
}
if(passingMarks < 1)
{
Print(null,null);
}
else
{
int questionCount = questions.Length;
int[][] marksTimeMatrix = new int[passingMarks+1][];
int[][][] questonRelation = new int[passingMarks][][];
int[][] questionsattempted = new int[passingMarks+1][];
int totalTime = 0;
for (int i = 0; i < questionCount; i++)
{
totalTime += questions[i].timeRequiredToComplete;
}
for (int i = 0; i < passingMarks; i++)
{
questonRelation[i] = new int[questionCount][];
}
for(int i = 0 ; i < passingMarks; i++)
{
for(int j = 0 ; j < questionCount; j++)
{
questonRelation[i][j] = new int[2];
}
}
for(int i = 0; i <= passingMarks; i++)
{
marksTimeMatrix[i] = new int[questionCount+1];
questionsattempted[i] = new int[questionCount+1];
}
for(int i = 1; i <= passingMarks; i++)
{
marksTimeMatrix[i][0] = totalTime;
questionsattempted[i][0] = questionCount;
}
for(int j = 0; j <= questionCount; j++)
{
marksTimeMatrix[0][j] = 0;
questionsattempted[0][j] = 0;
}
int iTemp,jTemp,optimizedI, optimizedJ;
for(int i = 1 ; i <= passingMarks; i++)
{
for(int j = 1; j <= questionCount; j++)
{
iTemp = i-questions[j-1].marks < 0?0:i-questions[j-1].marks;
jTemp = j-1 < 0?0:j-1;
if(marksTimeMatrix[i][j-1] < marksTimeMatrix[iTemp][jTemp] + questions[j-1].timeRequiredToComplete)
{
marksTimeMatrix[i][j] = marksTimeMatrix[i][j-1];
optimizedI = i-1;
optimizedJ = j-2;
questionsattempted[i][j] = questionsattempted[i][j-1];
}
else
{
marksTimeMatrix[i][j] = marksTimeMatrix[iTemp][jTemp] + questions[j-1].timeRequiredToComplete;
questionsattempted[i][j] = questionsattempted[iTemp][jTemp] + 1;
optimizedI = iTemp-1;
optimizedJ = jTemp-1;
}
questonRelation[i-1][j-1][0] = optimizedI;
questonRelation[i-1][j-1][1] = optimizedJ;
}
}
Question[] attemptedQuestions = new Question[questionsattempted[passingMarks][questionCount]];
int[] questionNumberArray = new int[questionsattempted[passingMarks][questionCount]];
optimizedI = passingMarks-1;
optimizedJ = questionCount-1;
int k=0;
while(optimizedJ >= 0 && optimizedI >= 0)
{
if(questonRelation[optimizedI][optimizedJ][0] == optimizedI)
{
optimizedJ = optimizedJ-1;
}
else
{
attemptedQuestions[k] = questions[optimizedJ];
questionNumberArray[k] = optimizedJ;
iTemp = questonRelation[optimizedI][optimizedJ][0];
jTemp = questonRelation[optimizedI][optimizedJ][1];
optimizedI = iTemp; optimizedJ = jTemp;
k++;
}
}
Print(attemptedQuestions,questionNumberArray);
}
}
public static void Print(Question[] questions, int[] questionNumberArray)
{
if(questions == null && questionNumberArray == null)
{
Console.WriteLine("No need to attempt any questions");
}
if((questionNumberArray == null && questions != null) || (questionNumberArray != null && questions == null) || (questions.Length != questionNumberArray.Length))
{
throw new Exception("inputs are not valid");
}
else
{
int totaltimerequired = 0;
Console.WriteLine("Minumum number of questions to attempt is {0}", questions.Length);
Console.WriteLine("Here is the questions list");
for(int i = 0 ; i < questions.Length;i++)
{
Console.WriteLine("Question : {0} (Marks : {1}, Time Required To Complete : {2})",questionNumberArray[i],questions[i].marks,questions[i].timeRequiredToComplete);
totaltimerequired += questions[i].timeRequiredToComplete;
}
Console.WriteLine("Minumum time required(in minutes) for these questions is {0}", totaltimerequired);
}
}
}
}
private static int PassingMarkInLessTime(int[] marks, int[] time, int p)
{
int n = marks.Length;
int[,] temp = new int[n + 1, p + 1];
int minVal = Int32.MaxValue;
int sumSoFar = 0;
for (int i = 0; i <= n; i++)
{
if (i != 0)
sumSoFar += marks[i - 1];
for (int j = 0; j <= p; j++)
{
if (i == 0 || j == 0)
{
temp[i, j] = 0;
continue;
}
if (j <= sumSoFar)
{
if (j < marks[i - 1])
{
temp[i, j] = temp[i - 1, j];
}
else
{
int v1 = temp[i - 1, j] == 0 ? Int32.MaxValue : temp[i - 1, j];
temp[i, j] = Math.Min(v1, time[i - 1] + temp[i - 1, j - marks[i - 1]]);
}
minVal = temp[i, j];
}
else
{
temp[i, j] = 0;
continue;
}
}
}
return minVal;
}
class Marks_Time implements Comparable<Marks_Time> {
int marks;
int time;
float weight;
public Marks_Time(int marks, int time) {
this.marks = marks;
this.time = time;
this.weight = ((float)marks)/time;
}
public int getMarks() {
return marks;
}
public void setMarks(int marks) {
this.marks = marks;
}
public int getTime() {
return time;
}
public void setTime(int time) {
this.time = time;
}
public float getWeight() {
return weight;
}
public void setWeight(float weight) {
this.weight = weight;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + getOuterType().hashCode();
result = prime * result + marks;
result = prime * result + time;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Marks_Time other = (Marks_Time) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (marks != other.marks)
return false;
if (time != other.time)
return false;
return true;
}
private PassingMarks getOuterType() {
return PassingMarks.this;
}
@Override
public int compareTo(Marks_Time o) {
if (weight == o.getWeight()) {
return o.getMarks() - this.marks;
} else {
return weight - o.getWeight() > 0 ? -1 : 1;
}
}
@Override
public String toString() {
return "Marks :"+marks + " , Time :" + time +" , Weight :" + weight;
}
}
Marks - Time collection -
4 7 6 8 9 5 4 10 3 11 15 13 15 7 10 9
1 2 2 3 4 1 3 3 3 4 5 2 4 1 2 2
Algo -
Collections.sort(marks_TimeList);
int passingMarks = 37;
int minimumTime = 0;
for (Marks_Time marksTime : marks_TimeList) {
if (marksTime.getMarks() < passingMarks) {
passingMarks = passingMarks - marksTime.getMarks();
minimumTime = minimumTime + marksTime.getTime();
} else {
minimumTime = minimumTime + marksTime.getTime();
break;
}
}
This is a twist on the 0-1 knapsack problem.
In the knapsack problem, we have items each having a weight and value and we want to maximize the value within a max weight.
In this problem, we have questions each having a score and time and we want to minimize the time to achieve a min score.
This problem has analogues in the knapsack problem:
question = item
score = weight
time = value
minimize time = maximize value
min score = max weight
- JW April 27, 2015