TIP102 Unit 5 Session 1 Advanced (Click for link to problem statements)
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?
What is the output?
target
and target - 1
swapped, if possible.What should happen if target
is the first node?
What if the list is empty?
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.
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:
target
node and the target - 1
node.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
target
is 1 or the list has only one node.target - 1
before swapping.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
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
prev
holds peach, current
holds luigi.Input: mario -> luigi, target = 1
target
is 1.Input: None, target = 1
head
is None, so return None.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.
O(N)
because we may need to traverse the entire list to find the node at index target
.O(1)
because we are only using a constant amount of space to hold references to the nodes being swapped.