Last Place - 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 the player_name of the last node in the linked list.

  • Can the list be empty?

    • Yes, the linked list can be empty, in which case the output should be None.
HAPPY CASE
Input: mario -> peach -> luigi -> daisy
Output: "Daisy"
Explanation: Daisy is the last node in the linked list.

Input: mario
Output: "Mario"
Explanation: The list contains only one node, which is Mario.

EDGE CASE
Input: None
Output: None
Explanation: The linked list is empty, so the output is None.

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 until we reach the last node.

For linked list problems, consider:

  • Traversing the list until you reach the node where current.next is None.
  • Handling the edge case where the list is empty.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to traverse the linked list until we reach the last node. The last node will have next as None. We will then return the player_name of that node.

1) If the linked list is empty (`head` is None), return None.
2) Initialize a variable `current` and set it to `head`.
3) Traverse the list by moving `current` to `current.next` until `current.next` is None (i.e., the last node).
4) Return the `player_name` of the last node.

⚠️ Common Mistakes

  • Forgetting to handle the edge case where the linked list is empty.
  • Missing the check to stop traversal at the last node (current.next is 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

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.player_name, end=" -> " if current.next else "\n")
        current = current.next

def last_place(head):
    if head is None:
        return None
    
    current = head
    while current.next:
        current = current.next
    
    return current.player_name

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: current moves through the list: mario -> peach -> luigi -> daisy.
    • Expected Output: "Daisy"

  • Input: mario

    • Watchlist: current stays on the single node: mario.
    • Expected Output: "Mario"

  • Input: None

    • Watchlist: head is None, so the function returns None.
    • Expected Output: None

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