How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Booking.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Booking during technical interviews.

Match Bookings to Payments | Booking Coding Question

Match Bookings to Payments

Company: Booking

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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?

Quick Answer: This question evaluates skill in matching records across unsorted collections, focusing on data structures, aggregation and handling one-to-one and one-to-many relationships between bookings and payments.

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

Input: ([101, 55, 78], [78, 101])

Expected Output: [True, False, True]

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

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

Expected Output: [True, False, True]

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

Input: ([10, 20], [])

Expected Output: [False, False]

Explanation: There are no payments, so no booking has been paid.

Input: ([], [1, 2])

Expected Output: []

Explanation: With no bookings, the result is an empty list.

Hints

Checking every payment for every booking is too slow for large inputs. Can you preprocess `payments` for fast lookup?
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

Input: ([101, 55, 78], [78, 101, 78, 78])

Expected Output: [1, 0, 3]

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

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

Expected Output: [1, 3, 2]

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

Input: ([10, 20], [])

Expected Output: [0, 0]

Explanation: No payments means every booking has count 0.

Input: ([], [1, 2, 2])

Expected Output: []

Explanation: With no bookings, the result is an empty list.

Input: ([7], [7, 7, 7])

Expected Output: [3]

Explanation: The single booking has three matching payment records.

Hints

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

Quick Overview

This question evaluates skill in matching records across unsorted collections, focusing on data structures, aggregation and handling one-to-one and one-to-many relationships between bookings and payments.