Update Rankings - codepath/compsci_guides GitHub Wiki

TIP102 Unit 5 Session 1 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Linked Lists, Indexing

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 input?

  • The input is the head of a 1-indexed linked list and a target index.

• What is the output?

  • The output is the head of the linked list with the nodes at target and target - 1 swapped, if possible.

• What should happen if target is the first node?

  • The original list should be returned without changes.

• What if the list is empty?

  • If the list is empty, the function should return None.

HAPPY CASE
Input: mario -> peach -> luigi -> daisy, target = 3
Output: mario -> luigi -> peach -> daisy
Explanation: The nodes at index 3 and index 2 (luigi and peach) are swapped.

Input: mario -> luigi, target = 1
Output: mario -> luigi
Explanation: No swap occurs because target is 1.

EDGE CASE
Input: None, target = 1
Output: None
Explanation: The list is empty, so the output is 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.

This problem is a Linked List Node Swap problem, where we need to swap the values or nodes at two adjacent positions in the list.

For linked list problems, consider:

• Traversing the list to locate the target node and the target - 1 node.
• Swapping the nodes or just their values, depending on the data structure and constraints.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We need to traverse the list to the node at index target - 1 and swap its value with the node at index target.

1) If `target <= 1`, or the list is empty, return the head as no swap is needed.
2) Initialize a variable `current` to the head and a variable `prev` to None.
3) Traverse the list until the `current` node is the node at the `target` index.
4) Once the `target` node is found, swap the `player` values between the node at `target` and the node at `target - 1`.
5) Return the modified head of the list.

⚠️ Common Mistakes

• Forgetting to handle the edge case where target is 1 or the list has only one node.
• Not correctly adjusting the pointer to target - 1 before swapping.

4: I-mplement

Implement the code to solve the algorithm.

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

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

def increment_rank(head, target):
  if target <= 1 or head is None or head.next is None:
      return head

  index = 1
  prev = None
  current = head

  # Traverse the list to the target index
  while index < target:
      prev = current
      current = current.next
      index += 1

  # Swap the values between the node at target-1 and the node at target
  temp = prev.player
  prev.player = current.player
  current.player = temp

  return head 

5: R-eview

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

• Input: mario -> peach -> luigi -> daisy, target = 3

  • Watchlist: prev holds peach, current holds luigi.
  • Expected Output: mario -> luigi -> peach -> daisy

• Input: mario -> luigi, target = 1

  • Watchlist: No swap occurs as target is 1.
  • Expected Output: mario -> luigi

• Input: None, target = 1

  • Watchlist: head is None, so return None.
  • Expected Output: None

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 may need to traverse the entire list to find the node at index target.
• Space Complexity: O(1) because we are only using a constant amount of space to hold references to the nodes being swapped.