"""
Exercise 1: remove the accidental O(n^2) (easy)

find_new_customers(today, known) returns the customers in `today` (a list, with possible duplicates)
that are NOT in `known` (a list), without duplicates, preserving first-appearance order.

The stub checks membership in a list inside a loop (O(n*m)). Make it O(n + m) by using sets for
membership tests (keep a separate `seen` set for de-duplication). With 20,000 customers the fast version
must finish in well under 0.1 s.
"""

import time


def find_new_customers(today, known):
    result = []
    for c in today:
        if c not in known and c not in result:
            result.append(c)
    return result


# --- self-check: do not modify below this line ---
checks = []
checks.append(("correct and ordered", find_new_customers(["b", "a", "c", "b", "d"], ["c"]), ["b", "a", "d"]))
today = [f"c{i}" for i in range(20000)] + [f"c{i}" for i in range(0, 20000, 2)]
known = [f"c{i}" for i in range(0, 20000, 3)]
start = time.perf_counter()
out = find_new_customers(today, known)
elapsed = time.perf_counter() - start
checks.append(("count", len(out), 20000 - len(range(0, 20000, 3))))
checks.append(("fast (< 0.1 s)", elapsed < 0.1, True))

passed = 0
for label, actual, expected in checks:
    ok = actual == expected
    passed += ok
    print(f"{'PASS' if ok else 'FAIL'}: {label} (got {actual!r}, expected {expected!r})")

print("PASS" if passed == len(checks) else "FAIL")