ML Prep

Reason about list-operation complexity

Problem

For the function below on nn input values, give tight worst-case time and auxiliary-space bounds. Then state the expected-time bound after replacing unique with a set and replacing the final loop by return len(values).

def duplicate_free_score(values):
    unique = []
    for value in values:
        if value not in unique:
            unique.append(value)
    total = 0
    for value in unique:
        total += values.count(value)
    return total
Reveal answer or reference solution

Worst-case time is O(n2)O(n^2): list membership can scan O(n)O(n) elements on each iteration, and up to nn calls to values.count each scan nn elements. Auxiliary space is O(n)O(n) for unique. A set-based pass has O(n)O(n) expected time under ordinary hash-table assumptions, and len(values) removes the second scan entirely. The returned score is always nn.

def complexity_answers() -> tuple[str, str, str]:
    return "O(n^2)", "O(n)", "O(n) expected"

Public tests

  • complexity_answers() → ('O(n^2)', 'O(n)', 'O(n) expected')
Outcome

Previous attempts

Loading attempts saved in this browser…

    Review Screening Results