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: koopa_troopa = Node("Koopa Troopa") -> Node("Toadette") -> Node("Waluigi")
Output: koopa_troopa = Node("Koopa Troopa") <-> Node("Toadette") <-> Node("Waluigi")
Explanation: The singly linked list is converted into a doubly linked list by updating the `prev` pointers.
EDGE CASE
Input: koopa_troopa = None
Output: None
Explanation: When the linked list is empty, no changes are made.
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 conversion problems, we want to consider the following approaches:
prev
and next
attributesPlan the solution with appropriate visualizations and pseudocode.
General Idea: Traverse the singly linked list and update each node's prev
pointer to point to the previous node.
1) Start at the head of the singly linked list.
2) Initialize a pointer `current` to the head and a pointer `prev_node` to `None`.
3) Traverse the list:
a) Set the `prev` pointer of the current node to `prev_node`.
b) Update `prev_node` to the current node.
c) Move `current` to the next node.
4) Continue until the end of the list is reached.
⚠️ Common Mistakes
prev
pointers for all nodes, leading to an incomplete doubly linked list.Implement the code to solve the algorithm.
class Node:
def __init__(self, value, next=None, prev=None):
self.value = value
self.next = next
self.prev = prev
koopa_troopa = Node("Koopa Troopa")
toadette = Node("Toadette")
waluigi = Node("Waluigi")
koopa_troopa.next = toadette
toadette.next = waluigi
# Convert to doubly linked list
current = koopa_troopa
prev_node = None
while current:
current.prev = prev_node
prev_node = current
current = current.next
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example:
print_linked_list(koopa_troopa) # Expected Output: "Koopa Troopa -> Toadette -> Waluigi"
print_linked_list_backwards(waluigi) # Expected Output: "Waluigi -> Toadette -> Koopa Troopa"
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
- Time Complexity: O(N) where N is the number of nodes in the linked list, as we need to traverse all nodes to update the prev pointers.
- Space Complexity: O(1) because we are only using a constant amount of extra space for the pointers.