Write a function to remove duplicates from a list while keeping the original order.
Walk through the list, keep a set of items already seen, and add an item to the result only if it is not in the set. This is O(n) time. Using set(lst) alone is fast but loses the order.
Explain it simply
set(lst) removes duplicates but does not promise any order. Since the order matters here, we remember what we have seen, and a set makes that lookup fast.
Line by line
def dedupe(items):
seen = set()
result = []
for x in items:
if x not in seen:
seen.add(x)
result.append(x)
return result
def dedupe_dict(items):
return list(dict.fromkeys(items))
print(dedupe([3, 1, 3, 2, 1, 4])) # Output: [3, 1, 2, 4]
print(dedupe_dict(["a", "b", "a", "c"])) # Output: ['a', 'b', 'c']
print(dedupe([])) # Output: []dict.fromkeys is the short trick: dictionaries keep insertion order (guaranteed since Python 3.7) and keys are unique. Both versions need the items to be hashable.
Complexity
Time O(n) on average, since set and dict lookups are O(1). Space O(n) for the seen set and the result.
What to say in the interview
"I loop once with a seen set, so each membership check is O(1) and order is preserved. list(dict.fromkeys(items)) does the same in one line. If items are unhashable, like lists, I'd fall back to a slower list-based check."