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.
subset
array. Two books are considered similar if they appear consecutively in the all_books
linked list.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.
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:
subset
.subset
.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
in_component
flag when a non-subset node is encountered, which could lead to incorrect counting.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
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
all_books
and subset
to verify that the function correctly counts the similar components.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(S)
where S
is the size of the subset
set.