How would you efficiently remove duplicates from a list while preserving order?
Order-preserving deduplication with dict.fromkeys
The idiomatic Python 3.7+ solution is list(dict.fromkeys(items)). A dict preserves insertion order and keys are unique, so the first occurrence of each hashable item is kept in order. If items are not hashable, you cannot use a dict or set directly; you need a different equality strategy, such as serializing to a hashable key or using an O(n^2) comparison fallback.
- 1
dict.fromkeys is concise and preserves first-occurrence order.
- 2
A seen set plus list append is also O(n) and can be faster if you need custom filtering logic.
- 3
Trade-off: dict.fromkeys builds a dict, while seen-set builds a set. Both are O(n) average time and O(n) space.
- 4
Common mistake: using list(set(items)), which removes duplicates but destroys order.
- 5
Version note: dict.fromkeys order preservation relies on Python 3.7+ dict insertion order guarantee.
Scenario Questions
0-2 years experience
- 1You have [1,2,1,3] and need unique values in original order. What do you do?
- 2Why does list(set(items)) not preserve order?
2-5 years experience
- 1You need to deduplicate a list of dicts by id while keeping first occurrence. How?
- 2You have unhashable elements. How do you preserve order without O(n^2) if possible?
5-8 years experience
- 1You stream a large log and need first occurrence per user ID with bounded memory. What data structure?
- 2You need stable deduplication across batches. How do you scale?
8+ years experience
- 1Design an order-preserving deduplication pipeline for billions of records with exactly-once semantics.
- 2You need dedupe with custom equality for near-duplicates. How do you avoid hashing pitfalls?
Follow-up Questions
- What if the list contains dictionaries? How do you deduplicate by a specific key?
- How would you deduplicate a stream that does not fit in memory?