Code Review · Python

Python Code Review: Inefficient List Lookups

Review Python code that repeatedly checks membership in a list and accidentally creates an O(n²) performance problem.

Code Review Exercise

Review the following code and identify as many issues as you can. The code is trying to return users whose IDs appear in a selected list of IDs.

python
def get_selected_users(users, selected_ids):
    selected = []

    for user in users:
        if user.id in selected_ids:
            selected.append(user)

    return selected

What concerns do you see before scrolling further?

Review Findings

Issue #1: Membership check may be O(n)

If selected_ids is a list, then user.id in selected_ids scans the list each time. That lookup is O(n), not O(1).

Issue #2: The loop can accidentally become O(n²)

If there are many users and many selected IDs, the code can do a large number of repeated list scans. The code looks simple, but it may scale poorly.

Issue #3: The expected input type is unclear

The function name selected_ids does not reveal whether it is a list, set, tuple, or another collection. That matters here because membership performance depends on the data structure.

Issue #4: Missing type hints make the performance issue easier to miss

Without type hints, a reviewer has to infer the shape of both inputs. If the code says selected_ids: set[int], the intended lookup behavior is much clearer.

Why This Happens

In Python, x in some_list checks each element until it finds a match or reaches the end. That is fine for tiny lists, but it can become expensive inside a loop.

A set is built for fast membership checks. If the only question is “is this ID selected?”, a set usually communicates the intent better and performs better.

Fixed Version

python
def get_selected_users(users, selected_ids):
    selected_id_set = set(selected_ids)

    selected = []
    for user in users:
        if user.id in selected_id_set:
            selected.append(user)

    return selected

This version converts the selected IDs to a set once, then uses fast membership checks inside the loop.

Cleaner Version With Type Hints

python
from collections.abc import Iterable


def get_selected_users(
    users: Iterable[User],
    selected_ids: Iterable[int],
) -> list[User]:
    selected_id_set = set(selected_ids)
    return [user for user in users if user.id in selected_id_set]

The type hints make the input contract clearer, and the list comprehension makes the filtering intent explicit.

When This Matters

This issue is easy to dismiss when the sample data is small. In production, the same pattern may appear in data processing, API filtering, CSV imports, report generation, and batch jobs.

A good reviewer does not automatically optimize everything. But when a linear lookup appears inside another loop, it is worth asking whether the input can grow.

Interview Follow-Ups

Is using a set always better than using a list?

No. A list is fine when order matters, duplicates matter, or the collection is tiny. A set is better when the main operation is membership lookup.

What is the tradeoff of converting the list to a set?

Building the set costs time and memory up front, but it can greatly reduce repeated membership lookup cost when there are many checks.

Should the caller pass a set instead?

Sometimes. If the function expects fast membership checks, accepting a set or documenting that selected_ids is converted internally are both reasonable choices.

Is this a correctness bug or a performance bug?

Usually it is a performance bug. The code returns the right answer, but it can become much slower than expected as input sizes grow.

What Interviewers Expect

A junior reviewer may say the code is readable and correct.

A stronger reviewer often notices the hidden performance issue:

  • Correctness: the result is probably right.
  • Performance: list membership inside a loop can be expensive.
  • Readability: a set better communicates lookup intent.
  • Maintainability: type hints make the expected inputs clearer.