TIP102 Unit 5 Session 1 Standard (Click for link to problem statements)
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?
How do we determine if a message can be passed from the start_villager
to the target_villager
?
start_villager
and checking if we reach the target_villager
.What attributes and methods are relevant for this problem?
neighbor
attribute of the Villager
class.HAPPY CASE
Input:
isabelle = Villager("Isabelle", "Dog", "Normal", "what's up?")
tom_nook = Villager("Tom Nook", "Raccoon", "Cranky", "yes, yes")
kk_slider = Villager("K.K. Slider", "Dog", "Lazy", "dig it")
isabelle.neighbor = tom_nook
tom_nook.neighbor = kk_slider
result = message_received(isabelle, kk_slider)
Output:
True
Explanation:
The message can be passed from Isabelle to Tom Nook, and then from Tom Nook to KK Slider.
EDGE CASE
Input:
isabelle = Villager("Isabelle", "Dog", "Normal", "what's up?")
kk_slider = Villager("K.K. Slider", "Dog", "Lazy", "dig it")
result = message_received(kk_slider, isabelle)
Output:
False
Explanation:
KK Slider has no neighbor, so the message cannot be passed to Isabelle.
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 neighbors of start_villager
and check if we can reach target_villager
.
1) Define the `message_received` function.
2) Initialize a variable `current` to `start_villager`.
3) While `current` is not None:
a) If `current` is `target_villager`, return True.
b) Move to the next neighbor by setting `current` to `current.neighbor`.
4) If the loop exits without finding `target_villager`, return False.
⚠️ Common Mistakes
None
to avoid infinite loops.current
variable to move to the next neighbor.Implement the code to solve the algorithm.
class Villager:
def __init__(self, name, species, personality, catchphrase, neighbor=None):
self.name = name
self.species = species
self.personality = personality
self.catchphrase = catchphrase
self.furniture = []
self.neighbor = neighbor
def message_received(start_villager, target_villager):
current = start_villager
while current is not None:
if current == target_villager:
return True
current = current.neighbor
return False
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Villager
and link them as neighbors.start_villager
and target_villager
pairs.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of neighbors in the chain.
O(N)
because we need to traverse the chain of neighbors.O(1)
because we are using a fixed amount of space for the traversal.