Prioritizing Suspects - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Partitioning, Temporary Head 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 partition a linked list such that all nodes with values greater than a given threshold come before nodes with values less than or equal to threshold.
  • What should be returned?
    • The function should return the head of the partitioned list.
HAPPY CASE
Input: suspect_ratings = Node(1, Node(4, Node(3, Node(2, Node(5, Node(2)))))) 
       threshold = 3
Output: 4 -> 5 -> 1 -> 3 -> 2 -> 2
Explanation: The nodes with values greater than 3 come first, followed by nodes with values less than or equal to 3.

EDGE CASE
Input: suspect_ratings = Node(3, Node(3, Node(3)))
       threshold = 3
Output: 3 -> 3 -> 3
Explanation: All nodes have values equal to the threshold, so their order remains unchanged.

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 Partitioning, we want to consider the following approaches:

  • Temporary Head Technique: Use temporary head nodes to separate the nodes into two groups (greater and less than or equal) before combining them.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will use two temporary head nodes to create two separate lists: one for nodes with values greater than the threshold, and one for nodes with values less than or equal to the threshold. After traversing the entire list, we will combine the two lists and return the head of the partitioned list.

1) Initialize two temporary head nodes: `greater_head` and `less_or_equal_head`.
2) Initialize two pointers `greater` and `less_or_equal` to point to the temporary heads.
3) Traverse the original linked list:
    a) For each node, if the node's value is greater than the threshold, append it to the `greater` list.
    b) Otherwise, append it to the `less_or_equal` list.
4) Combine the two lists by linking the end of the `greater` list to the start of the `less_or_equal` list.
5) Ensure the last node of the `less_or_equal` list points to None.
6) Return the head of the combined list.

⚠️ Common Mistakes

  • Forgetting to handle cases where one of the lists (greater or less than/equal) is empty.
  • Incorrectly managing the end of the less_or_equal list, leading to a cycle in the linked list.

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 partition the linked list
def partition(suspect_ratings, threshold):
    if not suspect_ratings:
        return None
    
    greater_head = Node(0)  # Temporary head for greater-than-threshold list
    less_or_equal_head = Node(0)  # Temporary head for less-or-equal list
    
    greater = greater_head
    less_or_equal = less_or_equal_head
    
    current = suspect_ratings
    while current:
        if current.value > threshold:
            greater.next = current
            greater = greater.next
        else:
            less_or_equal.next = current
            less_or_equal = less_or_equal.next
        current = current.next
    
    # Combine the two lists
    greater.next = less_or_equal_head.next
    less_or_equal.next = None  # Ensure the last node points to None
    
    # Check if the greater list is empty
    if greater_head.next:
        return greater_head.next
    else:
        return less_or_equal_head.next

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 suspect_ratings linked list with the threshold to verify that the function correctly partitions the list.

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 the algorithm uses a constant amount of extra space for pointers.