The Sorting Hat's Decision

JCSU Unit 10 Problem Set 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-30 mins
• 🛠️ Topics: Linked Lists, Partitioning, Two Pointers

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 problem?
  • Rearrange a linked list so that all nodes with values greater than threshold appear before nodes with values less than or equal to threshold.
• Are there constraints on input?
  • Input is a valid linked list, and threshold is an integer.

HAPPY CASE Input: student_scores = 4 -> 10 -> 2 -> 8 -> 5 threshold = 5 Output: 10 -> 8 -> 4 -> 2 -> 5 Explanation: Nodes with values greater than 5 are placed first, followed by nodes with values less than or equal to 5.

EDGE CASE Input: student_scores = None (Empty list) threshold = 5 Output: None Explanation: An empty list remains empty after rearrangement.

EDGE CASE Input: student_scores = 3 -> 3 -> 3 threshold = 3 Output: 3 -> 3 -> 3 Explanation: All nodes are equal to the threshold and remain in their original order.

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

• Two Pointers/Dummy Nodes: Use two separate lists for nodes greater than and less than/equal to the threshold, and reconnect them at the end.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Separate the linked list into two lists:

• Nodes with values greater than the threshold.
• Nodes with values less than or equal to the threshold.

Connect the two lists and return the new head of the rearranged list.

Steps:

1. Create two dummy nodes: higher_head for nodes greater than the threshold and lower_head for nodes less than or equal to the threshold.
2. Initialize two pointers (higher and lower) to build the respective lists.
3. Traverse the input list:
   • If the node's value is greater than threshold, add it to the higher list.
   • Otherwise, add it to the lower list.
4. Connect the higher list to the lower list.
5. Terminate the lower list to avoid cycles.
6. Return the head of the rearranged list, skipping the dummy higher_head node.

4: I-mplement

Implement the code to solve the algorithm.

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

# For testing
def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

def sort_into_houses(student_scores, threshold):
    # Create two dummy nodes to build two separate lists
    higher_head = Node(0)  # Dummy head for scores > threshold
    lower_head = Node(0)   # Dummy head for scores <= threshold

    # Pointers to build the two lists
    higher = higher_head
    lower = lower_head

    current = student_scores  # Start with the head of the input list

    # Traverse the linked list and separate nodes into two lists
    while current:
        if current.value > threshold:
            higher.next = current  # Add the current node to the 'higher' list
            higher = higher.next
        else:
            lower.next = current  # Add the current node to the 'lower' list
            lower = lower.next
        current = current.next  # Move to the next node in the input list

    # Connect the two lists: the 'higher' list followed by the 'lower' list
    higher.next = lower_head.next  # Skip the dummy node of the 'lower' list
    lower.next = None  # Terminate the 'lower' list

    # Return the new head, skipping the dummy node of the 'higher' list
    return higher_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 1:

• Input: student_scores = 4 -> 10 -> 2 -> 8 -> 5, threshold = 5
• Expected Output: 10 -> 8 -> 4 -> 2 -> 5
• Observed Output: 10 -> 8 -> 4 -> 2 -> 5

Example 2:

• Input: student_scores = None, threshold = 5
• Expected Output: None
• Observed Output: None

Example 3:

• Input: student_scores = 3 -> 3 -> 3, threshold = 3
• Expected Output: 3 -> 3 -> 3
• Observed Output: 3 -> 3 -> 3

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume n is the number of nodes in the linked list.

• Time Complexity: O(n) because we traverse the list once to partition it.
• Space Complexity: O(1) additional space because the rearrangement is done in-place using existing nodes.