How do you deduplicate a list in Python while preserving first-seen order?
answer
- Two obvious ways to drop duplicates
- One of them throws the order away
- Reach for a mapping, not a set
- Keys only, values all None
- Insertion order guaranteed since 3.7
basics
~10 slist(dict.fromkeys(items)) keeps the first occurrence of each element in its original position, because dict iteration order is guaranteed insertion order since Python 3.7. set(items) also removes duplicates but iterates in an arbitrary order.
solid answer
~40 sUse `list(dict.fromkeys(items))`. `dict.fromkeys` builds a dict whose keys are the elements, so equal elements collapse into one key, and since Python 3.7 a dict's iteration order is a language guarantee: insertion order. What survives is therefore the **first** occurrence of each element, in the slot where it first appeared. `set(items)` collapses duplicates just as well but iterates in hash-table order, which is arbitrary and, for strings, differs between processes because of hash randomization. Both need hashable elements and both are O(n); the naive `if x not in result` list scan is O(n squared) and only defensible for a handful of items. If you want the result sorted, sort it explicitly afterwards instead of hoping a set comes out ordered.
code
pycon · 5 lines>>> items = ["b", "a", "b", "c", "a"]
>>> list(dict.fromkeys(items))
['b', 'a', 'c']
>>> sorted(set(items))
['a', 'b', 'c']go deeper
Be ready to write the one-liner from memory and say what it returns for a short list. Know that a set removes duplicates but gives no order promise, and that both approaches need hashable elements.
Explain the mechanics: fromkeys builds a dict of keys with None values, a key's position is fixed at first insertion, and dict order has been a language guarantee since 3.7. Contrast O(n) with the O(n squared) list-scan version.
Show where the idiom stops: unhashable elements, deduplication by a derived field, and equal-but-not-identical elements where keeping the first one silently discards a different payload. Flag set-iteration order as a source of non-reproducible output.
Own the reproducibility argument: any pipeline whose output ordering comes from set iteration is unstable across processes because of hash randomization, and that instability shows up as flaky tests and non-deterministic artefacts. Make ordered dedupe the house default.
## The two candidate tools Deduplicating a sequence means collapsing elements that are **equal**, and Python decides equality for hashed containers with the pair `__hash__` and `__eq__`. Both tools below therefore require hashable elements. What separates them is the order of what comes out. `set(items)` builds a hash set. Iterating a set walks its internal table, so the output order is a function of each element's hash value and of the table's resize history, not of the order you inserted. For small integers this is deceptive: `hash(n) == n` for small ints, so `set([3, 1, 2])` frequently iterates ascending and people conclude that sets sort. They do not. For strings, hash randomization is on by default (seeded per process, pinnable with the `PYTHONHASHSEED` environment variable), so the same program can print a different order on the next run. Any code whose output depends on set iteration order is a flaky test waiting to happen. `dict.fromkeys(items)` is a classmethod that builds a dict whose keys are the elements and whose values are all `None` (an optional second argument supplies a different fill value). Duplicate elements collapse into one key. Since Python 3.7 a dict's iteration order is a documented **language guarantee** of insertion order; CPython 3.6 already behaved that way, but only as an implementation detail nobody was allowed to rely on. So `list(dict.fromkeys(items))` is the canonical order-preserving dedupe, and it is one expression. ```python >>> list(dict.fromkeys(["b", "a", "b", "c"])) ['b', 'a', 'c'] ``` The `list(...)` wrapper matters: iterating a dict yields its keys, but a dict is not a list, so callers expecting a sequence want the conversion. ## Why the *first* occurrence wins A key's position in a dict is fixed the first time it is inserted. Re-assigning a key that already exists updates its value but does **not** move it to the end. `dict.fromkeys` re-assigns `None` over `None`, so every later duplicate is a no-op for both the value and the position. You keep the first element you saw, where you first saw it. That distinction only becomes visible when "equal" does not mean "identical". `1`, `True` and `1.0` are all equal and share a hash, so they collapse into a single key, and it is whichever one appeared first that is kept: ```python >>> dict.fromkeys([1.0, True]) {1.0: None} ``` The same applies to any class with a custom `__eq__` and `__hash__`: two objects that compare equal but carry different payloads will leave you holding the first one. If you need the last one instead, feed the reversed sequence and reverse the result, or key the survivors explicitly. ## Cost Both `set` and `dict.fromkeys` are a single pass with O(1) average hashing per element, so both are O(n) time and O(k) extra space for k unique elements. The idiom people reach for before they know either one is ```python out = [] for x in items: if x not in out: out.append(x) ``` which is O(n squared), because `in` on a list is a linear scan. It is fine for ten items and a genuine production hazard for a hundred thousand. `dict.fromkeys` does allocate a full dict rather than a set, so each unique element costs a table entry plus a value slot; that overhead is real but almost never the deciding factor next to correct ordering. ## Iterables and iterators Both accept any iterable, including a generator, and both consume it exactly once. `list(dict.fromkeys(line.strip() for line in stream))` is a complete deduplicating read of a stream. Because the whole result is materialized, memory scales with the number of **unique** elements, not with the input length, which is why this idiom survives inputs far larger than the output. ## Where the one-liner stops working Two cases break it. If elements are unhashable, such as `dict` or `list` instances, both tools raise `TypeError` and you need a hashable stand-in key. And if you want to deduplicate by a *derived* value, keeping the first record per user id rather than per whole record, `dict.fromkeys` cannot express it at all, because it keys on the entire element; that case needs an explicit `seen` set inside a loop. ## Interview framing Interviewers ask this to see whether you reach past the obvious `set()`. Saying "`set(items)`" is a correct answer to a question that was not asked. The strong answer states the ordering guarantee, names the version it became a guarantee, and mentions that the elements must be hashable either way.
- Does list(dict.fromkeys(items)) keep the first or the last occurrence of a duplicate, and why?The first. A dict key's position is fixed on its first insertion; assigning to an existing key updates the value but never moves the key. `dict.fromkeys` writes `None` over `None` for every later duplicate, so both the value and the position are unchanged. To keep the last occurrence instead, deduplicate the reversed sequence and reverse the result.
- Why does iterating a set of small integers often look sorted while a set of strings does not?Small integers hash to themselves, so they usually land in table slots in ascending order and iterate that way by accident. String hashing is randomized per process by default, so a set of strings iterates in an order that changes between runs. Neither is a guarantee, and code that relies on either is fragile.
- What does list(dict.fromkeys([1, True, 1.0])) return?`[1]`. The three values compare equal and share a hash, so they collapse into one key, and the first one inserted is the one kept. This is the same reason a list containing both `0` and `False` deduplicates down to whichever came first, and it is a real source of surprise when a sequence mixes bools with numbers.
A set is a bag you tip out on the table: everything you put in is there, in no particular arrangement. A dict is a numbered ledger: each new entry gets the next line and never changes line again.
saying these in an interview costs you the question
- Claims set() preserves the order of the input
- Uses an if-not-in-list scan on large inputs
- Thinks sorted(set(x)) restores the original order
- Calls dict ordering a CPython-only implementation detail today
- Forgets that elements must be hashable either way
- Assumes duplicates keep the last occurrence