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.
HAPPY CASE
Input:
- playlist1 = Node(1, Node(2, Node(3, Node(4))))
- playlist2 = Node(('Respect', 'Aretha Franklin'),
Node(('Superstition', 'Stevie Wonder'),
Node(('Wonderwall', 'Oasis'),
Node(('Like a Prayer', 'Madonna'),
Node(('Bohemian Rhapsody', 'Queen'))))))
Output:
- 1 -> 4 -> 2 -> 3
- ('Respect', 'Aretha Franklin') -> ('Bohemian Rhapsody', 'Queen') -> ('Superstition', 'Stevie Wonder') -> ('Like a Prayer', 'Madonna') -> ('Wonderwall', 'Oasis')
Explanation:
- The list is reordered to alternate between elements from the start and end of the original list.
EDGE CASE
Input:
- playlist = Node(1, Node(2))
Output:
- 1 -> 2
Explanation:
- The list has only two elements, so no reordering is necessary.
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 Reordering and Merging, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will split the linked list into two halves, reverse the second half, and then merge the two halves by alternating nodes from each half.
1) Initialize two pointers `slow` and `fast` to find the middle of the list.
2) Reverse the second half of the list.
3) Merge the two halves by alternating nodes from each half.
4) Return the head of the newly reordered list.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def shuffle_playlist(playlist):
if not playlist or not playlist.next:
return playlist
# Step 1: Find the middle of the list
slow, fast = playlist, playlist
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Step 2: Reverse the second half
prev, curr = None, slow.next
slow.next = None # Split the list into two halves
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
# Step 3: Merge the two halves
first, second = playlist, prev
while second:
next_first, next_second = first.next, second.next
first.next = second
second.next = next_first
first = next_first
second = next_second
return playlist
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
playlist1
and playlist2
linked lists to verify that the function correctly shuffles the playlists.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the playlist.
O(N)
because we traverse the entire list multiple times (finding the middle, reversing, and merging).O(1)
because the algorithm uses a constant amount of extra space for pointers.