Target Practice - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 1 Standard (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15-25 mins
  • 🛠️ Topics: Linked Lists, Two Pointers, Slow and Fast Pointer Technique

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 does the problem ask for?
    • The problem asks to return the middle potion from a linked list using the slow and fast pointer technique.
  • What should be returned if the list has an even number of nodes?
    • If the list has an even number of nodes, return the potion of the second middle node.
HAPPY CASE
Input: potions1 = Node("Poison Antidote", Node("Shrinking Solution", Node("Trollblood Tincture")))
Output: "Shrinking Solution"
Explanation: "Shrinking Solution" is the middle potion in the list.

HAPPY CASE
Input: potions2 = Node("Elixir of Life", Node("Sleeping Draught", Node("Babbling Beverage", Node("Aging Potion"))))
Output: "Sleeping Draught"
Explanation: "Sleeping Draught" is the second middle potion in the list with an even number of nodes.

EDGE CASE
Input: potions = None
Output: None
Explanation: If the list is empty, return 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.

For Linked List problems involving Finding the Middle Element, we want to consider the following approaches:

  • Two Pointers (Slow and Fast Pointer Technique): Use two pointers that traverse the list at different speeds to find the middle node efficiently.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use the slow and fast pointer technique. The slow pointer will move one step at a time, while the fast pointer will move two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle node.

1) Initialize two pointers: slow and fast, both pointing to the head of the list.
2) Traverse the list:
    a) Move the slow pointer by one step.
    b) Move the fast pointer by two steps.
    c) Continue until the fast pointer reaches the end or there are no more nodes for the fast pointer to move.
3) The slow pointer will now be pointing to the middle node.
4) Return the potion at the middle node.

⚠️ Common Mistakes

  • Forgetting to handle the case where the list is empty.
  • Incorrectly updating the pointers or missing the condition where the fast pointer reaches the end.

4: I-mplement

Implement the code to solve the algorithm.

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

# Function to find the middle potion
def find_middle_potion(potions):
    if not potions:
        return None
    
    slow = potions
    fast = potions

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow.potion

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided potions1 and potions2 linked lists to verify that the function correctly identifies the middle potion.

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 each node is visited at most once.
  • Space Complexity: O(1) because only a constant amount of extra space is used for pointers.