Microsoft Interview Question for Software Architects


Team: Bangalore
Country: United States
Interview Type: Phone Interview




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

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

// We will define DP table t:
t[q][s] = min time to do quiz ending at question q and with at least score s
t[0][...] = t[...][0] = infinity

// If question q’s score >= min score, we want to take either just question q or not take question q at all (in this case, take previous questions that yield score s).
// If question q's score < min score, we can take question q along with some previous questions together yielding score s, or just take previous questions that yield score s.
t[q][s] = (question[q].score >= minScore) ? min(t[q-1][s], question[q].t) : min(t[q-1][s-question[q].score] + question[q].time, t[q-1][s])

- JW April 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What happens when t[q-1][s-question[q].score] is infinity? It wouldnt work I guess.

- sowmya.kp May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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];
}

- sowmya.kp May 10, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- CptSudoku April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

defintly this is fraction knapsack prblm

- shubham April 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- eugene.yarovoi May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sonesh June 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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);
            }
        }
    }
}

- sonesh June 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
        }

- codealtecdown September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
            }
        }

- Dinesh Kumar December 26, 2016 | 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