Count Racers

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

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Linked List, Iteration

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 goal of the function?
  • To count the number of nodes in the linked list.
• What should the function return if the list is empty?
  • It should return 0.

HAPPY CASE
Input: Linked List: mario -> peach -> luigi -> daisy
Output: 4
Explanation: There are 4 nodes in the linked list.

EDGE CASE
Input: Linked List: None
Output: 0
Explanation: The linked list is empty.

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

• Traverse the list while counting the nodes.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the linked list from the head to the end, counting the nodes.

1) Initialize a counter to 0.
2) Traverse the linked list starting from the head node.
3) For each node encountered, increment the counter.
4) Continue until the end of the linked list is reached.
5) Return the counter value.

⚠️ Common Mistakes

• Forgetting to handle the case where the linked list is empty and returning the count as 0.

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.

• Trace through your code with an input to check for the expected output
• Catch possible edge cases and off-by-one errors

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 the nodes in the linked list.
• Space Complexity: O(1) because we only need a fixed amount of extra space for pointers.