Editor

Gatecrashers

#623 · Dictionaries and sets · Intermediate · Fast enough · 60 XP · about 10 min

A festival scans the badge of everyone who comes through its gate. The organizers have two lists of badge numbers: guest_list, every badge that was invited, and arrivals, every scan at the gate in the order it happened. People go in and out, so the same badge can be scanned many times.

Write gatecrashers(guest_list, arrivals) that returns a list of the badges that were scanned but are not on the guest list, each badge once, in the order of its first scan.

Examples

gatecrashers([4, 8, 15], [8, 23, 4, 42, 23])  # returns [23, 42]
gatecrashers([1, 2, 3], [3, 2, 1])            # returns []
gatecrashers([], [7, 7, 5])                   # returns [7, 5]

In the first example badges 8 and 4 were invited. Badge 23 was scanned twice but appears once in the answer.

Constraints

  • 0 <= len(guest_list) <= 200,000
  • 0 <= len(arrivals) <= 200,000
  • Badge numbers are whole numbers from 0 to 1,000,000,000.

Time limit

Each test must finish within 10 seconds, and the hidden tests use lists of 200,000 badges.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.