# The Ones That Come Back > In a column that promised uniqueness, some values kept their seat. Name them. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## Problem A data-quality check on an event export turned up a column of integer `ids` that should be unique but isn't. Return the id values that appear more than once, from smallest to largest. ## Worked solution and explanation ### What this really is Strip the event-export framing and this is a frequency tally with two twists. The skill being probed: count how many times each value occurs, then keep only the values whose count crosses two. Anyone can spot that a value repeats. What separates candidates is the value that repeats THREE times (it still appears once) and the promised ascending order (a bare set hands you neither). Return `list(some_set)` and you pass the sample by luck and fail the moment the duplicates don't happen to fall out sorted. --- ### The tempting wrong turn The classic "find duplicates" pattern is two sets: one for values you've seen, one for values you've seen twice. It's clean and it's O(n). But it answers a different question than the one asked here, and it quietly drops the ordering promise. **Two sets, returned raw** seen = set(); dups = set() for x in ids: if x in seen: dups.add(x) else: seen.add(x) return list(dups) Correctly finds duplicates, but list(dups) is in set iteration order, not ascending. On [5,3,5,3,3,1,1] it can return [3,5,1]. Contract violated. **Count, filter, sort** counts = Counter(ids) repeated = [] for v, c in counts.items(): if c > 1: repeated.append(v) return sorted(repeated) Tallies every value, keeps those seen more than once, and the sorted() makes the ascending contract explicit. Each value appears once because dict keys are unique. > **Trick to solving** > > The output order is part of the spec, not an afterthought. A set answers "is it a duplicate?" but has no order to give you. The instant a problem says "smallest to largest", a raw set-to-list conversion is a bug, even when your one sample case happens to come out sorted. --- ### The solution #### Step 1: Tally occurrences in one pass collections.Counter(ids) walks the list once and gives you value -> count. This is the move that separates duplicates from singletons; without a count you cannot tell them apart. #### Step 2: Keep only the repeats Loop over the counter's items and, with a simple count > 1 check, append the values that qualify. Because you're reading dict keys, each qualifying value is considered exactly once, so a thrice-seen value can't sneak in twice. #### Step 3: Sort ascending on the way out Wrap the collected values in sorted(). This is the line the naive two-set version forgets, and it's the one the grader checks. **Count, filter, sort** ```python from collections import Counter def find_duplicates_only(ids: list[int]) -> list[int]: counts = Counter(ids) repeated = [] for value, count in counts.items(): if count > 1: repeated.append(value) return sorted(repeated) ``` > **Performance insight** > > **Time:** O(n) to build the counter, plus O(d log d) to sort the d duplicate values (d <= n). **Space:** O(n) for the counter. The sort is the only non-linear term, and d is usually tiny compared to n. > **Interviewers watch for** > > Whether the ascending contract is honored by construction or by accident. A candidate who returns list(set) and shrugs "it's sorted in the example" has missed that ordering is a requirement. sorted() at the boundary shows they read the whole spec, not just the first sentence. > **Common pitfall** > > Appending on every repeat instead of collecting unique keys. On [2, 2, 2] that yields [2, 2] because the value triggers the "seen before" branch twice. Counting sidesteps it: the value is one key with a count of three, appended once. --- ## Common follow-up questions - What if the output had to be in first-seen order instead of ascending? _(Tests whether they'd swap sorted() for a first-occurrence dict, since Counter already preserves insertion order in modern Python.)_ - How would you return values that appear exactly k times? _(Tests generalizing the count > 1 filter to count == k with a full frequency map.)_ - If the input were already sorted, could you avoid the counter entirely? _(Tests recognizing that adjacent equality makes duplicates detectable in O(1) extra space.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_ones_that_come_back) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.