Your question is Refactoring for Complexity. Take a moment with it on the right.
Talk me through your thinking if you like. When you're confident, submit your answer and I'll grade it like a real screen (7/10 or better passes).
You're a software engineer at Ovyo working on catalog and viewership analytics for streaming partners. The three functions below run nightly over the full content catalog and viewing logs: finding duplicate titles that were accidentally ingested twice, finding viewers who watched two specific shows, and finding the most-watched genre. Against a small test catalog they're fine, but against Ovyo's real catalog (tens of thousands of titles) and a day's worth of viewing events, the nightly job now takes hours.
def find_duplicate_titles(catalog):
duplicates = []
for i in range(len(catalog)):
for j in range(len(catalog)):
if i != j and catalog[i]["title"] == catalog[j]["title"]:
if catalog[i] not in duplicates:
duplicates.append(catalog[i])
return duplicates
def common_viewers(show_a_viewers, show_b_viewers):
common = []
for viewer in show_a_viewers:
if viewer in show_b_viewers:
common.append(viewer)
return common
def most_watched_genre(watch_events):
genre_counts = []
for event in watch_events:
genre = event["genre"]
found = False
for entry in genre_counts:
if entry["genre"] == genre:
entry["count"] += 1
found = True
break
if not found:
genre_counts.append({"genre": genre, "count": 1})
genre_counts.sort(key=lambda e: e["count"], reverse=True)
return genre_counts[0]["genre"]
How would you refactor this piece of code to improve its time and space complexity? For each function, state its current complexity, why, and what you'd change it to.