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