Sort the Performers - codepath/compsci_guides GitHub Wiki

Unit 2 Session 1 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the problem asking for?

  • A: The problem asks to return the list of performer names sorted in descending order based on their performance durations.

• Q: What are the inputs?

  • A: Two arrays, performer_names (strings) and performance_times (distinct positive integers), both of length n.

• Q: What are the outputs?

  • A: A list of performer names sorted in descending order of their performance durations.

• Q: Are there any constraints on the values in the arrays?

  • A: The arrays are of equal length and performance_times contains distinct positive integers.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to map performance times to performer names, sort the performance times in descending order, and then extract the performer names based on the sorted times.

1. Create a dictionary `performance_dict` mapping performance times to lists of performer names.
2. For each pair of name and time in `performer_names` and `performance_times`, populate the dictionary.
3. Sort the keys of the dictionary (performance times) in descending order.
4. Create an empty list `sorted_performer_names` to store the sorted performer names.
5. For each time in the sorted times, append the corresponding performer names to `sorted_performer_names`.
6. Return the list `sorted_performer_names`.

I-mplement

from collections import defaultdict

def sort_performers(performer_names, performance_times):
    "
    :type performer_names: List[str]
    :type performance_times: List[int]
    :rtype: List[str]
    "
    # Step 1: Create a dictionary mapping performance times to lists of performer names
    performance_dict = defaultdict(list)
    for name, time in zip(performer_names, performance_times):
        performance_dict[time].append(name)
    
    # Step 2: Sort the performance times in descending order
    sorted_times = sorted(performance_dict.keys(), reverse=True)
    
    # Step 3: Extract the performer names based on the sorted performance times
    sorted_performer_names = []
    for time in sorted_times:
        for name in performance_dict[time]:
            sorted_performer_names.append(name)
    
    return sorted_performer_names