TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
None
.HAPPY CASE
Input:
- playlist_a = Node('Song A', Node('Song B'))
- playlist_b = Node('Song X', Node('Song Y', Node('Song Z')))
- shared_segment = Node('Song M', Node('Song N', Node('Song O')))
- playlist_a.next.next = shared_segment
- playlist_b.next.next.next = shared_segment
Output:
- Song M
Explanation:
- Both playlists intersect at the node with value 'Song M'.
EDGE CASE
Input:
- playlist_a = Node('Song A')
- playlist_b = Node('Song X')
Output:
- None
Explanation:
- There is no intersection between the two playlists.
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 involving Intersection, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will calculate the lengths of both linked lists, align the start of the longer list with the shorter list, and then traverse both lists in tandem to find the intersection point.
1) Initialize a helper function `get_length` to calculate the length of a linked list.
2) Calculate the lengths of both `playlist_a` and `playlist_b`.
3) Align the start of the longer list with the shorter list by moving the pointer of the longer list ahead by the difference in lengths.
4) Traverse both lists simultaneously until the intersection is found.
5) If an intersection is found, return the intersecting node. If no intersection is found, return `None`.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def playlist_overlap(playlist_a, playlist_b):
# Step 1: Calculate the lengths of both linked lists
def get_length(head):
length = 0
while head:
length += 1
head = head.next
return length
len_a = get_length(playlist_a)
len_b = get_length(playlist_b)
# Step 2: Align the start of the longer list
while len_a > len_b:
playlist_a = playlist_a.next
len_a -= 1
while len_b > len_a:
playlist_b = playlist_b.next
len_b -= 1
# Step 3: Traverse both lists in tandem
while playlist_a and playlist_b:
if playlist_a == playlist_b:
return playlist_a
playlist_a = playlist_a.next
playlist_b = playlist_b.next
return None
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
playlist_a
and playlist_b
linked lists with a shared segment to verify that the function correctly identifies the intersection node.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
and M
represent the lengths of playlist_a
and playlist_b
respectively.
O(N + M)
because we traverse both linked lists to calculate their lengths and then traverse them again to find the intersection.O(1)
because the algorithm uses a constant amount of extra space for pointers.