Unit 5 Session 1 (Click for link to problem statements)
TIP102 Unit 5 Session 1 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: dog -> cat -> mouse -> cheese
Output: "Spike chases Tom chases Jerry chases Gouda"
Explanation: The values of the nodes are concatenated with "chases" as the separator.
EDGE CASE
Input: (empty list)
Output: "
Explanation: The list is empty, so the function returns an empty string.
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: Traverse the linked list to collect the values of the nodes in a list, then join the values with "chases" as the separator.
1) Initialize an empty list to store the node values.
2) Traverse the linked list from the head to the end.
3) Append each node's value to the list.
4) Join the values in the list with "chases" as the separator.
5) Return the resulting string.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def chase_list(head):
current = head
values = []
while current:
values.append(current.value)
current = current.next
return " chases ".join(values)
# Example usage
dog = Node("Spike")
cat = Node("Tom")
mouse = Node("Jerry")
cheese = Node("Gouda")
dog.next = cat
cat.next = mouse
mouse.next = cheese
print(chase_list(dog)) # Output: "Spike chases Tom chases Jerry chases Gouda"
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Example:
dog = Node("Spike")
cat = Node("Tom")
mouse = Node("Jerry")
cheese = Node("Gouda")
dog.next = cat
cat.next = mouse
mouse.next = cheese
print(chase_list(dog)) # Expected Output: "Spike chases Tom chases Jerry chases Gouda"
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Time Complexity:
Space Complexity: