Looped - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Local Minima/Maxima Detection

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 number of critical points (local minima or maxima) in a linked list representing volume levels in a song.
  • What constitutes a critical point?
    • A critical point is a node that is either a local minima or maxima:
      • Local minima: The current node’s value is less than both the previous and the next node’s values.
      • Local maxima: The current node’s value is greater than both the previous and the next node’s values.
HAPPY CASE
Input: song_audio = Node(5, Node(3, Node(1, Node(2, Node(5, Node(1, Node(2)))))))
Output: 3
Explanation: There are three critical points:
- The third node is a local minima because 1 is less than 3 and 2.
- The fifth node is a local maxima because 5 is greater than 2 and 1.
- The sixth node is a local minima because 1 is less than 5 and 2.

EDGE CASE
Input: song_audio = Node(5)
Output: 0
Explanation: A single node can't be a critical point.

EDGE CASE
Input: song_audio = Node(5, Node(5, Node(5)))
Output: 0
Explanation: All nodes have the same value, so no critical points exist.

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 Local Minima/Maxima Detection, we want to consider the following approaches:

  • Traversal: Traverse the list while comparing the current node’s value with its previous and next nodes to identify critical points.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list with three pointers (previous, current, and next). For each node, check if it is a local minima or maxima by comparing its value with its neighbors.

1) Initialize three pointers: prev, current, and next_node.
2) Start the traversal from the second node (as the first node cannot be a critical point).
3) For each node, check:
    a) If it is a local minima: current value < prev value and current value < next_node value.
    b) If it is a local maxima: current value > prev value and current value > next_node value.
4) If the node is a critical point, increment the count.
5) Move all pointers one step forward and continue until next_node becomes None.
6) Return the total count of critical points.

⚠️ Common Mistakes

  • Failing to check boundary conditions, such as when the list has fewer than three nodes.
  • Misidentifying critical points by incorrectly comparing values.

4: I-mplement

Implement the code to solve the algorithm.

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

# Function to count critical points
def count_critical_points(song_audio):
    if not song_audio or not song_audio.next or not song_audio.next.next:
        return 0  # There can't be any critical points if there are less than 3 nodes

    count = 0
    prev = song_audio
    current = song_audio.next
    next_node = current.next

    while next_node:
        if (current.value > prev.value and current.value > next_node.value) or \
           (current.value < prev.value and current.value < next_node.value):
            count += 1
        
        # Move the pointers forward
        prev = current
        current = next_node
        next_node = next_node.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.

  • Example: Use the provided song_audio linked list to verify that the function correctly identifies all critical points.
  • Watch: Verify that the traversal properly considers the values of the current, previous, and next nodes.

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