8
\$\begingroup\$

I solved the Nested List Python challenge on HackerRank.com passing all test cases. Although this problem can likely be solved with a short script with clever one-liners, my approach was instead to solve it in a clean, understandable way in functional style.

Here is a summary of the challenge, see link above for full description:

Print the name(s) of any student(s) having the second lowest grade; if there are multiple students, order their names alphabetically and print each one on a new line.

The first line contains an integer, \$N\$, the number of students. The \$2N\$ subsequent lines describe each student over \$2\$ lines; the first line contains a student's name, and the second line contains their grade.

I haven't used nested lists much until now and I found myself having to search the internet a good bit for parts of the functions (in particular the get_lowest_grade function) and I would like to improve this code as much as possible.

def get_students(num_students: int) -> list:
    """Returns a list of names and grades of N students read from stdin
    where each name and respective grade is separated by a new line."""
    students = []
    for s in range(0, num_students):
        name = input()
        grade = float(input())
        students.append([name, grade])
    return students

def get_lowest_grade(students: list) -> float:
    """Returns the lowest grade from a list of students[name, grade]."""
    lowest_grade_student = min(students, key = lambda x: x[1])
    return lowest_grade_student[1]

def get_lowest_grade_students(students: list) -> list:
    """Returns the students with the lowest grade 
    from a list of students[name, grade]."""
    return [s for s in students if s[1] == get_lowest_grade(students)]

def exclude_lowest_grade_students(students: list) -> list:
    """Returns a list of students with the lowest graded students excluded
    from a list of students[name, grade]."""
    return [s for s in students if s[1] != get_lowest_grade(students)]

def get_student_names_sorted_alpha(students: list) -> list:
    """Returns a list of names sorted alphabetically from a list of students[name, grade]"""
    names = [s[0] for s in students]
    return sorted(names)

def main():
    num_students = int(input())
    students = get_students(num_students)
    lowest_excluded = exclude_lowest_grade_students(students)
    second_lowest = get_lowest_grade_students(lowest_excluded)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)

if __name__ == '__main__':
    main()
\$\endgroup\$
5
\$\begingroup\$

Your code looks nice and is well documented.

Many details can be improved though.

  • num_students = int(input()) could be moved in get_students so that your code deals with input in a single place.

  • even though the problem talks about lists, it may be more idiomatic to use a list of tuples instead of a list of list. I'd highly recommend Ned Batchelder's excellent article "Lists vs. Tuples" to know more about this.

  • 0 as a first argument of range is not needed as it is the default value. So you could rewrite: for s in range(0, num_students): as for s in range(num_students):.

  • Underscore (_) is pretty conventionnal for variable with an used value so you could write: for _ in range(num_students):.

  • Adding a simple print statement in get_lowest_grade shows that the function is called more often that it needs. This is a real issue when you have many students because your algorithm with go through all student for all students. Your algorithm is said to be quadratic or O(n^2). You could retrieve the lowest grade once and for all .

Your code would look like this:

def get_students() -> list:
    """Returns a list of names and grades of N students read from stdin
    where each name and respective grade is separated by a new line."""
    return [('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39),
            ('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39),
            ('Harry', 37.21), ('Berry', 37.21), ('Tina', 37.2), ('Akriti', 41), ('Harsh', 39)]
    num_students = int(input())
    students = []
    for s in range(num_students):
        name = input()
        grade = float(input())
        students.append((name, grade))
    return students

def get_lowest_grade(students: list) -> float:
    """Returns the lowest grade from a list of students[name, grade]."""
    lowest_grade_student = min(students, key = lambda x: x[1])
    return lowest_grade_student[1]

def get_students_with_grade(students: list, grade: float) -> list:
    """Returns the students with the lowest grade 
    from a list of students(name, grade)."""
    return [s for s in students if s[1] == grade]

def get_students_without_grade(students: list, grade: float) -> list:
    """Returns a list of students with the lowest graded students excluded
    from a list of students(name, grade)."""
    return [s for s in students if s[1] != grade]

def get_student_names_sorted_alpha(students: list) -> list:
    """Returns a list of names sorted alphabetically from a list of students[name, grade]"""
    names = [s[0] for s in students]
    return sorted(names)

def main():
    students = get_students()
    lowest_grade = get_lowest_grade(students)
    students2 = get_students_without_grade(students, lowest_grade)
    lowest_grade2 = get_lowest_grade(students2)
    second_lowest = get_students_with_grade(students2, lowest_grade2)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)

if __name__ == '__main__':
    main()

A different algorithm could be written using a different data structure like a dictionnary or a counter.

\$\endgroup\$
5
\$\begingroup\$

Performance

In this function, get_lowest_grade(...) will get called once for every student:

def get_lowest_grade_students(students: list) -> list:
    """Returns the students with the lowest grade
    from a list of students[name, grade]."""
    return [s for s in students if s[1] == get_lowest_grade(students)]

exclude_lowest_grade_students has the same flaw.

Another performance issue is the repeated list creations. Especially the one that creates the list without the lowest scoring students: as this list will typically have similar size as the original, it's a waste of memory.

Algorithm

Excluding the lowest scoring students in order to find the second lowest scoring students in the remaining group is a bit awkward. This awkwardness may have contributed to the performance traps in the implementation.

It would be simpler to actually find the 2nd lowest score, and then filter by that score.

As a follow up exercise, generalizing to find the k-th lowest score, without actually sorting the entire list, is an interesting problem to crack (see selection sort).

Named tuples

Although the main purpose of the exercise is nested lists, you might appreciate to learn about named tuples. Using named tuples, you could replace meaningless indexes like this:

names = [s[0] for s in students]

with code like this:

names = [s.name for s in students]

To make this possible, you can create a Student named tuple with:

from collections import namedtuple

Student = namedtuple('Student', ['name', 'score'])

And append students to the students list with:

students.append(Student(name, grade))

Coding style

The coding style is almost spotless, there are only two minor violations of PEP8:

  • There should be no spaces around keyword parameters, so instead of min(students, key = lambda x: x.score), it should be min(students, key=lambda x: x.score)
  • There should be two blank lines before function definitions
\$\endgroup\$
2
\$\begingroup\$

Similar to Janos I would propose to use a collections.namedtuple for a Student object:

from collections import namedtuple

Student = namedtuple("Student", ("name", "grade"))

It will also help, like he noted, to define a k-lowest grade function, like this:

def get_k_lowest_grade(students, k):
    """Returns the k-lowest grade from a list of Students(name, grade)."""
    grades = set(s.grade for s in students)
    return sorted(grades)[k - 1]

I would also make get_students_with_grade return a generator to avoid duplicating memory and the same for get_student_names_sorted_alpha (you just have to be aware that you can iterate over the results of the function exactly once):

def get_students_with_grade(students, grade):
    """Returns all students with `grade`
    from a list of Students(name, grade)."""
    return (s for s in students if s.grade == grade)


def get_student_names_sorted_alpha(students):
    """Returns a generator of names sorted alphabetically from a list of Students(name, grade)"""
    yield from sorted(s.name for s in students)

This makes your main a bit shorter:

def main():
    students = get_students()
    lowest_grade_2 = get_k_lowest_grade(students, k=2)
    second_lowest = get_students_with_grade(students, lowest_grade_2)
    for name in get_student_names_sorted_alpha(second_lowest):
        print(name)
\$\endgroup\$
  • \$\begingroup\$ I really like your generators idea, I'll try to start using those, thank you! \$\endgroup\$ – Phrancis Sep 27 '16 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.