Count Racers - codepath/compsci_guides GitHub Wiki

TIP102 Unit 5 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

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

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 is the input?

    • The input is the head of a linked list where each node represents a player in the race.

  • What is the output?

    • The output is an integer representing the total number of nodes (players) in the linked list.

  • Can the list be empty?

    • Yes, the linked list can be empty, in which case the output should be 0.
HAPPY CASE
Input: mario -> peach -> luigi -> daisy
Output: 4
Explanation: There are 4 nodes, representing 4 players.

Input: mario
Output: 1
Explanation: There is only 1 node, so the output is 1.

EDGE CASE
Input: None
Output: 0
Explanation: An empty linked list results in an output of 0.

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.

This problem is a Linked List Traversal problem, where we need to iterate through each node of the linked list and count the total number of nodes.

For linked list problems, consider:

  • Traversing the list one node at a time.
  • Checking for the end of the list (i.e., when current is None).

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to traverse the linked list from the head node to the last node, counting each node we encounter.

1) Initialize a variable `count` to 0 to store the number of players.
2) Set `current` to the `head` of the linked list.
3) While `current` is not None:
    a) Increment the `count` by 1.
    b) Move `current` to the next node.
4) Once we reach the end of the list (`current` is None), return the `count`.

⚠️ Common Mistakes

  • Forgetting to handle the edge case where the linked list is empty.
  • Missing a condition to stop traversal (when current becomes None).

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, player, next=None):
        self.player_name = player
        self.next = next

def count_racers(head):
    count = 0
    current = head
    while current:
        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.

  • Input: mario -> peach -> luigi -> daisy

    • Watchlist: count is incremented at each step: 1, 2, 3, 4.
    • Expected Output: 4

  • Input: mario

    • Watchlist: count starts at 0 and increments once.
    • Expected Output: 1

  • Input: None

    • Watchlist: count remains 0 as there are no nodes.
    • Expected Output: 0

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 traverse each node exactly once.
  • Space Complexity: O(1) because we only use a constant amount of space regardless of the size of the linked list.