Unit 5 Session 2 (Click for link to problem statements)
TIP102 Unit 5 Session 2 Standard (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?
HAPPY CASE
Input: head = Node("banana") -> Node("blue shell") -> Node("bullet bill"), val = "red shell"
Output: Node("banana") -> Node("red shell") -> Node("blue shell") -> Node("bullet bill")
Explanation: The node with value "red shell" is correctly inserted as the second node.
EDGE CASE
Input: head = Node("banana"), val = "red shell"
Output: Node("banana") -> Node("red shell")
Explanation: The new node is inserted as the second element after the single existing node.
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:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Insert a new node after the head of the linked list by updating the next
pointers of the relevant nodes.
1) Create a new node with the given value `val`.
2) Set the `next` pointer of the new node to point to the node that was originally the second node (i.e., the node after the head).
3) Update the `next` pointer of the head to point to the new node.
4) Return the head of the linked list.
⚠️ Common Mistakes
next
pointers, causing incorrect list sequences.Implement the code to solve the algorithm.
def add_second(head, val):
# Create the new node that needs to be added
new_node = Node(val)
# Insert the new node as the second node
new_node.next = head.next
head.next = new_node
# Return the unchanged head of the list
return head
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example:
head = Node("banana")
head.next = Node("blue shell")
head.next.next = Node("bullet bill")
new_head = add_second(head, "red shell")
print_linked_list(new_head)
# Expected Output: "banana -> red shell -> blue shell -> bullet bill"
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
- Time Complexity: O(1) for the insertion operation since we are directly updating the pointers.
- Space Complexity: O(1) because we are only adding one new node.