200 Points for Gryffindor - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10-15 mins
  • 🛠️ Topics: Linked Lists, Counting Elements

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 the frequency of a given score in a linked list representing house points.
  • What should be the structure of the linked list?
    • Each node in the linked list contains a house name and its score.
HAPPY CASE
Input: house_points = Node("Gryffindor", 600, Node("Ravenclaw", 300, Node("Slytherin", 500, Node("Hufflepuff", 600)))), score = 600
Output: 2
Explanation: The score 600 appears twice in the linked list.

EDGE CASE
Input: house_points = None, score = 500
Output: 0
Explanation: An empty list does not contain any elements, so the output is 0.

EDGE CASE
Input: house_points = Node("Gryffindor", 600), score = 400
Output: 0
Explanation: The score 400 does not appear in the list.

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 problems involving Element Counting, we want to consider the following approaches:

  • Traversal: Traverse the list while counting occurrences of the target score.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list, and for each node, check if its score matches the given score. We will keep a count of the number of matches.

1) Initialize a count variable to 0.
2) Traverse the linked list starting from the head.
3) For each node, check if the node's value equals the given score.
4) If it does, increment the count.
5) Move to the next node and continue until the end of the list.
6) Return the count as the frequency of the score in the list.

⚠️ Common Mistakes

  • Forgetting to increment the count correctly when a match is found.
  • Not handling the case where the list is empty.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, house, score, next=None):
        self.house = house
        self.value = score
        self.next = next

# Function to count the frequency of the score in the linked list
def count_element(house_points, score):
    count = 0
    current = house_points

    while current:
        if current.value == score:
            count += 1
        current = current.next

    return count

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 house_points linked list and verify that the function correctly counts the frequency of the score 600.

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 each node is visited exactly once.
  • Space Complexity: O(1) because only a constant amount of extra space is used for the count variable.