JuniorCodeOccasionalNot answered yet
Filter out seen ids while keeping the original order
Given recom_ids and seen_ids, return a new list with the same order as recom_ids but excluding any id that appears in seen_ids.
Requirements:
- Preserve the order of
recom_ids. - Aim for O(n) overall, not the O(n*m) nested scan.
def filter_seen(recom_ids, seen_ids):
# your code hereWrite the implementation.
Convert seen_ids to a set once, then iterate recom_ids keeping items whose id is not in that set. The set gives O(1) membership, so the whole pass is O(n); a list-based in check would make each test O(m) and the total O(n*m). Iterating recom_ids directly preserves order.
- ✗Leaving
seen_idsas a list, so eachincheck is O(m) and the total O(n*m) - ✗Using set difference, which loses the required
recom_idsorder - ✗Mutating
recom_idsin place while iterating instead of building a new list
- →Why does converting
seen_idsto a set change the overall complexity? - →How would you preserve order if you instead used a set difference?
Contents
Task
Implement filter_seen: return the elements of recom_ids in original order, excluding any present in seen_ids, in O(n).
Solution
def filter_seen(recom_ids, seen_ids):
seen = set(seen_ids) # O(1) membership
return [x for x in recom_ids if x not in seen]Key points
set(seen_ids)is built once in O(m); eachnot incheck is then O(1).- Iterating
recom_idsdirectly preserves order — set difference does not guarantee it. - Without the set, a list
incheck would make the algorithm O(n*m).
Contents
