Last Place

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.