Surprise Me - codepath/compsci_guides GitHub Wiki

TIP102 Unit 6 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Linked Lists, Random Selection, Reservoir Sampling

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What does the problem ask for?
    • A: The problem asks to return a random node's value from a singly linked list.
    • A: Each node must have the same probability of being chosen.
  • Q: What should be returned?
    • A: The function should return the value of a randomly chosen node.
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.

2: M-atch

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:

  • Reservoir Sampling: This algorithm allows us to randomly select an element from a stream (or linked list in this case) with uniform probability.
  • Traversal: Traverse the linked list and decide whether to update the chosen value based on a random selection.

3: P-lan

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

  • Forgetting to handle cases where the list is empty.
  • Incorrectly managing random number generation, leading to biased selection.

4: I-mplement

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

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Example: Use the provided catalogue linked list with multiple books to verify that the function correctly returns a random book with equal probability.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the length of the linked list.

  • Time Complexity: O(N) because we traverse the entire linked list once.
  • Space Complexity: O(1) because the algorithm uses a constant amount of extra space for the result and index variables.