Please navigate to the bottom of the page for Table of Contents

Friday, April 19, 2013

LINQ design interview question

LINQ is one of my favorite interview topics for many reasons. It allows me to check a candidate's ability to define logic, use SQL skills, showcase lambda expressions, distill the problem into easy steps and of course, see some code in action. Also, since LINQ code is generally quite compact, it is perfect for white boarding.

I was recently helping a friend solve a problem and felt that it could be modified to an excellent interview question. It has a bit of algorithm design, heavy use of simple to medium complex LINQ and is not more that 10-15 lines of actual code. Perfect.

Question: Given a class of students  (ID, Name, Grades) with results for at least 2 semesters, find the students whose Grades have significantly improved in the second semester as compared to the first. Bonus: List out top 25% of the students.

As the first step, let us define the rough algorithm for solving this problem:

  1. Load Student data for first semester
  2. Load student data for second semester
  3. Merge Grades for each student from second semester into the first semester result set
  4. For each student, calculate the grade difference for students whose grades have improved (you do not want to waste computational cycles for students whose grades have fallen)
  5. For each student from 4 above, calculate the grade improvement percent
  6. Sort the result by descending order of grade improvement percent
  7. Select rows that constitute top 25% of students

Now, let’s define our POCO class that will represent the student data structure. The data structure has two parts: basic student properties (Id, Name, Grade) and some computational properties that we will use to solve our algorithm.

    public class StudentRecord
{
// basic properties
public int Id { get; set; }
public string Name { get; set; }
public double Grade { get; set; }

// computational properties
public double GradeSecondSemester { get; set; }
public double GradeDifference { get; set; }
public double GradeDifferencePercent { get; set; }
}

In addition to a Student record, we also need to a collection to hold these records. Let’s call it ClassReport:

    public class ClassReport
{
// some basic properties of a class
public int Id { get; set; }
public string Name { get; set; }
public int SemesterId { get; set; }

// list of student records for that semester
public List<StudentRecord> Students;

public ClassReport()
{
Students =
new List<StudentRecord>();
}
}

For steps 1 and 2 of the algorithm, I am not going to focus on this blog. We will assume that we have a way to load this data (stubbed in our code sample below).


Step 1 and 2: Load Student data:


We will mock up our student data in this example. In real life, this data probably will come from a database or a web service call, etc. As you can see below, we generate some dummy student data for two different semesters. Note that the student Id’s need to match across (not really a hard requirement, but good to have for our demo purposes).

        static void Main(string[] args)
{
// Step 1 and 2: Load Student data
ClassReport cr1 = MockSem1();
ClassReport cr2 = MockSem2();

}

private static ClassReport MockSem1()
{
ClassReport cr = new ClassReport()
{
Id = 1,
Name =
"First Grade",
SemesterId = 1
};

// add dummy data - in real life, this comes from database
cr.Students.Add(
new StudentRecord()
{
Id = 1,
Name =
"Ray",
Grade = 90
});
cr.Students.Add(
new StudentRecord()
{
Id = 2,
Name =
"Jack",
Grade = 80
});
cr.Students.Add(
new StudentRecord()
{
Id = 3,
Name =
"John",
Grade = 60
});
cr.Students.Add(
new StudentRecord()
{
Id = 4,
Name =
"Lisa",
Grade = 67
});
cr.Students.Add(
new StudentRecord()
{
Id = 5,
Name =
"Jill",
Grade = 94
});
return cr;
}

private static ClassReport MockSem2()
{
ClassReport cr = new ClassReport()
{
Id = 1,
Name =
"First Grade",
SemesterId = 2
};

// add dummy data - in real life, this comes from database
cr.Students.Add(
new StudentRecord()
{
Id = 1,
Name =
"Ray",
Grade = 85
});
cr.Students.Add(
new StudentRecord()
{
Id = 2,
Name =
"Jack",
Grade = 95
});
cr.Students.Add(
new StudentRecord()
{
Id = 3,
Name =
"John",
Grade = 82
});
cr.Students.Add(
new StudentRecord()
{
Id = 4,
Name =
"Lisa",
Grade = 95
});
cr.Students.Add(
new StudentRecord()
{
Id = 5,
Name =
"Jill",
Grade = 96
});
return cr;
}

Step 3: Merge Grades for each student from second semester into the first semester result set


Here is where our LINQ fun starts. In one of my previous post, I had explained how LINQ join works. Now would be a good time to review bunch of LINQ related interview questions and answers from the past.

            // step 3: Merge Grades for each student from second 
// semester into the first semester result set

// in-line merge; no need for a separate assignment
// for each student in first semester report
(from firstSem in cr1.Students
// join to second sem class report
join secondSem in cr2.Students
// on student id as the key
on firstSem.Id equals secondSem.Id
// assign second sem grade to first (via a select; clever)
select firstSem.GradeSecondSemester = secondSem.Grade)
// execute
.ToList();
As you can see from the LINQ statement, we join first semester class report with second semester and then do an in-line update of the first semester data structure’s GradeSecondSemester property.

Step 4: Calculate grade difference for students whose grades have improved


Now we need to process those students whose grades improved in the 2nd semester and update our data structure to reflect the difference:

// step 4: For each student, calculate the grade difference 
// for students whose grades have improved (you do not want
// to waste computational cycles for students whose grades have fallen)
cr1.Students
// find all students who did better in 2nd semester
.FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
// and update their grade difference property
.ForEach(x => x.GradeDifference = (x.GradeSecondSemester - x.Grade));

We use FindAll to find those students who have better grades and then loop for those records using ForEach to update the GradeDifference property.


Step 5: For each student from 4 above, calculate the grade improvement percent

// Step 5: For each student from 4 above, 
// calculate the grade improvement percent

// 5.a. calculate total difference sum
double gradeDiffSum = cr1.Students.Sum(x => x.GradeDifference);

// 5.b. calculate percent for each row
cr1.Students
// find all students who did better in 2nd semester
.FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
// update grade percent
.ForEach(x => x.GradeDifferencePercent =
((x.GradeDifference * 100) / gradeDiffSum));

Step 6: Sort the result by descending order of grade improvement percent


By this point, I am hoping you get the gist of how to approach such LINQ queries. Sorting a list is a relatively simple operation as shown below:

    // Step 6: Sort the result by descending order of grade improvement percent
var sortedList =
(
from entry in cr1.Students
orderby entry.GradeDifferencePercent descending
select
entry)
.ToList();
Step 7: Select rows that constitute top 25% of students

We use TakeWhile here to keep selecting students till we reach our number.

    //Step 7: Select rows that constitute top 25% of students
// 7.a. - sum of grade diff percent
double gradeDiffPercentSum = 0;

// 7.b - take as many rows as needed till we reach the 25% sum
var bestStudents =
sortedList
.TakeWhile(x =>
((gradeDiffPercentSum += x.GradeDifferencePercent) <= 25.0))
.ToList();

// 7.c account for the case where the first element is more than 25
if (bestStudents.Count() == 0)
bestStudents = sortedList.Take(1).ToList();
That’s it. You now have a list of top 25% students whose grades have improved in the second semester.

I am pasting the complete program here in case you like to see the whole thing in one shot.


The complete solution:

using System.Linq;

namespace
StudentReport
{
class
Program
{
static void Main(string
[] args)
{
// Step 1 and 2: Load Student data
ClassReport
cr1 = MockSem1();
ClassReport
cr2 = MockSem2();

// step 3: Merge Grades for each student from second
// semester into the first semester result set

// in-line merge; no need for a separate assignment
// for each student in first sem report
(from firstSem in
cr1.Students
// join to second sem class report
join secondSem in
cr2.Students
// on student id as the key
on firstSem.Id equals
secondSem.Id
// assign second sem grade to first (via a select; clever)
select
firstSem.GradeSecondSemester = secondSem.Grade)
// execute
.ToList();

// step 4: For each student, calculate the grade difference
// for students whose grades have improved (you do not want
// to waste computational cycles for students whose grades have fallen)
cr1.Students
// find all students who did better in 2nd semester
.FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
// and update their grade difference property
.ForEach(x => x.GradeDifference = (x.GradeSecondSemester - x.Grade));

// Step 5: For each student from 4 above,
// calculate the grade improvement percent

// 5.a. calculate total difference sum
double
gradeDiffSum = cr1.Students.Sum(x => x.GradeDifference);

// 5.b. calculate percent for each row
cr1.Students
// find all students who did better in 2nd semester
.FindAll(s => ((s.GradeSecondSemester - s.Grade) > 0))
// update grade percent
.ForEach(x => x.GradeDifferencePercent =
((x.GradeDifference * 100) / gradeDiffSum));


// Step 6: Sort the result by descending order of grade improvement percent
var
sortedList =
(
from entry in
cr1.Students
orderby entry.GradeDifferencePercent
descending
select
entry)
.ToList();


//Step 7: Select rows that constitute top 25% of students
// 7.a. - sum of grade diff percent
double
gradeDiffPercentSum = 0;

// 7.b - take as many rows as needed till we reach the 25% sum
var
bestStudents =
sortedList
.TakeWhile(x =>
((gradeDiffPercentSum += x.GradeDifferencePercent) <= 25.0))
.ToList();

// 7.c account for the case where the first element is more than 25
if
(bestStudents.Count() == 0)
bestStudents = sortedList.Take(1).ToList();

// do something with this result set
}

private static ClassReport
MockSem1()
{
ClassReport cr = new ClassReport
()
{
Id = 1,
Name =
"First Grade"
,
SemesterId = 1
};

// add dummy data - in real life, this comes from database
cr.Students.Add(
new StudentRecord
()
{
Id = 1,
Name =
"Ray"
,
Grade = 90
});
cr.Students.Add(
new StudentRecord
()
{
Id = 2,
Name =
"Jack"
,
Grade = 80
});
cr.Students.Add(
new StudentRecord
()
{
Id = 3,
Name =
"John"
,
Grade = 60
});
cr.Students.Add(
new StudentRecord
()
{
Id = 4,
Name =
"Lisa"
,
Grade = 67
});
cr.Students.Add(
new StudentRecord
()
{
Id = 5,
Name =
"Jill"
,
Grade = 94
});
return
cr;
}

private static ClassReport
MockSem2()
{
ClassReport cr = new ClassReport
()
{
Id = 1,
Name =
"First Grade"
,
SemesterId = 2
};

// add dummy data - in real life, this comes from database
cr.Students.Add(
new StudentRecord
()
{
Id = 1,
Name =
"Ray"
,
Grade = 85
});
cr.Students.Add(
new StudentRecord
()
{
Id = 2,
Name =
"Jack"
,
Grade = 85
});
cr.Students.Add(
new StudentRecord
()
{
Id = 3,
Name =
"John"
,
Grade = 70
});
cr.Students.Add(
new StudentRecord
()
{
Id = 4,
Name =
"Lisa"
,
Grade = 82
});
cr.Students.Add(
new StudentRecord
()
{
Id = 5,
Name =
"Jill"
,
Grade = 96
});
return
cr;
}
}
}

2 comments:

  1. The Business Phone Service are available in every place of the world. The service providers come up with various plans from time to time. It has the latest features incorporated that help people to make the best use of the technology.

    ReplyDelete
  2. Very good example. Inspirational.

    ReplyDelete