Top Artists - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Linked Lists, Hash Maps

1: U-nderstand

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

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does the problem ask for?
  • The problem asks to return a dictionary that maps each artist in the linked list to the number of times they appear.
• What is the structure of the linked list?
  • Each node in the linked list contains a song, the artist of the song, and a reference to the next node.
• What should the output look like?
  • The output should be a dictionary where the keys are artist names and the values are their respective frequencies.

HAPPY CASE
Input: playlist = SongNode("Saturn", "SZA", SongNode("Who", "Jimin", SongNode("Espresso", "Sabrina Carpenter", SongNode("Snooze", "SZA"))))
Output: {"SZA": 2, "Jimin": 1, "Sabrina Carpenter": 1}
Explanation: The artist "SZA" appears twice, while "Jimin" and "Sabrina Carpenter" appear once.

EDGE CASE
Input: playlist = None
Output: {}
Explanation: An empty linked list should return an empty dictionary.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List and Hash Map problems, we want to consider the following approaches:

• Traversing a linked list: We can traverse the linked list to gather all artists.
• Using a dictionary: We can use a dictionary to keep track of the frequency of each artist.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list and for each artist encountered, we will update the frequency count in a dictionary.

1) Initialize an empty dictionary called artist_frequency to store artist frequencies.
2) Traverse the linked list starting from the head node.
3) For each node, check if the artist is already in the dictionary:
    a) If the artist is present, increment the frequency count.
    b) If the artist is not present, add it to the dictionary with a frequency count of 1.
4) Continue until the end of the linked list is reached.
5) Return the artist_frequency dictionary.

⚠️ Common Mistakes

• Not handling the case where the linked list is empty.
• Forgetting to update the artist's frequency in the dictionary.

4: I-mplement

Implement the code to solve the algorithm.

class SongNode:
    def __init__(self, song, artist, next=None):
        self.song = song
        self.artist = artist
        self.next = next

# For testing
def print_linked_list(node):
    current = node
    while current:
        print((current.song, current.artist), end=" -> " if current.next else ")
        current = current.next
    print()

def get_artist_frequency(playlist):
    artist_frequency = {}
    current = playlist
    
    while current:
        if current.artist in artist_frequency:
            artist_frequency[current.artist] += 1
        else:
            artist_frequency[current.artist] = 1
        current = current.next
    
    return artist_frequency

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Example: Use the provided playlist and ensure that the frequencies of "SZA", "Jimin", and "Sabrina Carpenter" are correctly counted.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of nodes in the linked list.

• Time Complexity: O(N) because we need to traverse all nodes in the linked list to compute the frequencies.
• Space Complexity: O(N) because in the worst case, we may store a frequency count for each node in the linked list.