Timmy and tommy - codepath/compsci_guides GitHub Wiki

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

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 5-10 mins
  • 🛠️ Topics: Classes, Linked Lists, Pointers

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • How do we insert a new node between two existing nodes in a linked list?

    • By adjusting the next pointers of the nodes to include the new node.

  • What attributes and methods are relevant for this problem?

    • The next attribute of the Node class.
HAPPY CASE
Input: 
tom_nook = Node("Tom Nook")
tommy = Node("Tommy")
timmy = Node("Timmy", tommy)
tom_nook.next = timmy
print(tom_nook.value) # Output: Tom Nook
print(tom_nook.next.value) # Output: Timmy
print(timmy.value) # Output: Timmy
print(timmy.next.value) # Output: Tommy
print(tommy.value) # Output: Tommy
print(tommy.next) # Output: None

Explanation: 
The linked list is correctly updated to include `timmy` between `tom_nook` and `tommy`.

EDGE CASE
Input: 
node1 = Node("Node 1")
node2 = Node("Node 2")
node1.next = node2
new_node = Node("New Node", node2)
node1.next = new_node
print(node1.value) # Output: Node 1
print(node1.next.value) # Output: New Node
print(new_node.value) # Output: New Node
print(new_node.next.value) # Output: Node 2

Explanation: 
The new node is correctly inserted between the two existing nodes.

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

  • Create and link nodes using the next attribute.
  • Adjust the next pointers to insert nodes in the desired position.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Insert the new node timmy between tom_nook and tommy by updating the next pointers.

1) Define the `Node` class with `__init__` method to initialize `value` and `next` attributes.
2) Create an instance of `Node` for `tom_nook` with value "Tom Nook".
3) Create an instance of `Node` for `tommy` with value "Tommy".
4) Link `tom_nook` to `tommy` using the `next` attribute.
5) Create an instance of `Node` for `timmy` with value "Timmy" and `next` pointing to `tommy`.
6) Update the `next` attribute of `tom_nook` to point to `timmy`.

⚠️ Common Mistakes

  • Forgetting to set the next attribute of timmy to tommy.
  • Incorrectly referencing the next attribute.

4: I-mplement

Implement the code to solve the algorithm.

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

# From previous problem
tom_nook = Node("Tom Nook")
tommy = Node("Tommy")
tom_nook.next = tommy

# Create and insert the new node
timmy = Node("Timmy", tommy)
tom_nook.next = timmy

5: R-eview

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

  • Instantiate the nodes tom_nook, tommy, and timmy.
  • Validate the linked list by checking the value and next attributes.
  • Ensure the nodes are linked correctly with timmy between tom_nook and tommy.

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(1) because creating and linking nodes are constant-time operations.
  • Space Complexity: O(1) for each node instance created.