Last Place

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 return the player name of the last node in the linked list.
• What should the function return if the list is empty?
  • It should return None.

HAPPY CASE
Input: Linked List: mario -> peach -> luigi -> daisy
Output: ""Daisy""
Explanation: The last node in the linked list is ""Daisy"".

EDGE CASE
Input: Linked List: None
Output: None
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 to find the last node.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Traverse the linked list from the head to the end, and return the player name of the last node.

1) If the head is None, return None.
2) Initialize a pointer starting at the head node.
3) Traverse the linked list until the next node is None.
4) Return the player name of the current node.

⚠️ Common Mistakes

• Forgetting to handle the case where the linked list is empty and returning 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.

• 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."