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:
- catalogue = Node(('Homegoing', 'Yaa Gyasi'), Node(('Pachinko', 'Min Jin Lee'), Node(('The Night Watchman', 'Louise Erdrich'))))
Output:
- One of the book titles and authors from the list should be returned with equal probability.
EDGE CASE
Input:
- catalogue = Node(('Only Book', 'Author'))
Output:
- ('Only Book', 'Author')
Explanation:
- There is only one node in the list, so it should always be returned.
Match what this problem looks like to known categories of problems, e.g. Random Selection, Linked Lists, etc.
For Linked List problems involving Random Selection, we want to consider the following approaches:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: We will traverse the linked list, and for each node, randomly decide whether to update the chosen value using reservoir sampling.
1) Initialize `result` to `None`.
2) Initialize a counter `index` to 0.
3) Traverse the linked list:
- For each node, generate a random integer between 0 and `index`.
- If the random integer is 0, update `result` to the current node's value.
- Increment `index` by 1.
4) After traversing the list, return `result`.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
import random
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
def get_random(catalogue):
result = None
current = catalogue
index = 0
while current:
# Randomly decide if we should update the result with current node's value
if random.randint(0, index) == 0:
result = current.value
current = current.next
index += 1
return result
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
catalogue
linked list with multiple books to verify that the function correctly returns a random book with equal probability.Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the length of the linked list.
O(N)
because we traverse the entire linked list once.O(1)
because the algorithm uses a constant amount of extra space for the result and index variables.