Match Bookings to Payments

You are given two unsorted lists:

• bookings: each record contains at least a unique booking_id
• payments: each record contains at least a booking_id indicating which booking the payment belongs to

For each booking, determine whether a payment has been made for that booking.

Clarify your expected output, for example:

• return a boolean for a single booking, or
• return a mapping/list showing whether each booking has at least one matching payment

Follow-up:

• How would your approach change if one booking can have multiple payment records?

Part 1: Determine Whether Each Booking Has a Matching Payment

You are given two unsorted lists of booking IDs. bookings contains unique booking IDs, and payments contains the booking ID referenced by each payment record. For every booking in bookings, determine whether there is at least one payment with the same booking ID. Return the results as a list of booleans in the same order as bookings.

Constraints

• 0 <= len(bookings), len(payments) <= 200000
• bookings contains unique integers
• 0 <= booking_id <= 10^9
• payments may contain duplicate booking IDs
• payments may contain booking IDs that do not exist in bookings

Examples

Example 1

Input: ([101, 55, 78], [78, 101])
Output: [True, False, True]

Explanation: Bookings 101 and 78 appear in payments, but 55 does not.

Example 2

Input: ([1, 2, 3], [3, 3, 4, 1])
Output: [True, False, True]

Explanation: Duplicate payments for booking 3 still only mean True. Payment 4 is ignored because it has no matching booking.

Hints

1. Checking every payment for every booking is too slow for large inputs. Can you preprocess payments for fast lookup?
2. The output order must match the original bookings list.

Part 2: Count Payment Records for Each Booking

You are given two unsorted lists of booking IDs. bookings contains unique booking IDs, and payments contains the booking ID referenced by each payment record. A single booking can now have multiple payment records. For every booking in bookings, return how many payment records belong to it. The result must be in the same order as bookings.

Constraints

• 0 <= len(bookings), len(payments) <= 200000
• bookings contains unique integers
• 0 <= booking_id <= 10^9
• payments may contain duplicate booking IDs
• payments may contain booking IDs that do not exist in bookings

Examples

Example 1

Input: ([101, 55, 78], [78, 101, 78, 78])
Output: [1, 0, 3]

Explanation: Booking 101 has 1 payment, 55 has none, and 78 has 3.

Example 2

Input: ([1, 2, 3], [3, 3, 4, 1, 2, 2, 2])
Output: [1, 3, 2]

Explanation: Booking 1 appears once, 2 appears three times, and 3 appears twice. Payment 4 is ignored.

Hints

1. Instead of only tracking whether a payment exists, track how many times each payment booking ID appears.
2. A hash map/dictionary can store the frequency of each booking ID in payments.