Book Similarity - 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, Sets, Consecutive Subsets

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 count the number of similar book components in the subset array. Two books are considered similar if they appear consecutively in the all_books linked list.
• Q: What should be returned?
  • A: The function should return the number of similar book components.

HAPPY CASE
Input: 
    - all_books1 = Node(0, Node(1, Node(2, Node(3))))
    - subset1 = [0, 1, 3]
Output: 
    - 2
Explanation: 
    - 0 and 1 are similar, so [0, 1] and [3] are the two similar components.

EDGE CASE
Input: 
    - all_books2 = Node(0, Node(1, Node(2, Node(3, Node(4)))))
    - subset2 = [0, 3, 1, 4]
Output: 
    - 2
Explanation: 
    - 0 and 1 are similar, 3 and 4 are similar, so [0, 1] and and [3, 4] are the similar components.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked Lists, Sets, Consecutive Subsets, etc.

For Linked List problems involving Consecutive Subsets, we want to consider the following approaches:

• Traversal: Traverse the linked list while checking whether consecutive nodes belong to the subset.
• Sets: Use a set to quickly check membership of a value in the subset.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: We will traverse the linked list and use a set to check if each node's value is part of the subset. If consecutive nodes belong to the subset, they are part of the same component. If not, a new component begins.

1) Convert the `subset` array into a set for quick lookup.
2) Initialize a variable `similar_count` to 0 and a boolean `in_component` to False.
3) Traverse the linked list:
    - If the current node's value is in the set and we are not already in a component, increment `similar_count` and set `in_component` to True.
    - If the current node's value is not in the set, set `in_component` to False.
4) Continue until the entire list is traversed.
5) Return the value of `similar_count`.

⚠️ Common Mistakes

• Forgetting to reset the in_component flag when a non-subset node is encountered, which could lead to incorrect counting.
• Incorrectly handling edge cases where the subset is empty or the list is empty.

4: I-mplement

Implement the code to solve the algorithm.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def similar_book_count(all_books, subset):
    subset_set = set(subset)
    current = all_books
    similar_count = 0
    in_component = False
    
    while current:
        if current.value in subset_set:
            if not in_component:
                similar_count += 1
                in_component = True
        else:
            in_component = False
        
        current = current.next
    
    return similar_count

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 all_books and subset to verify that the function correctly counts the similar components.

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(S) where S is the size of the subset set.