Match Shops and Buyers
Updated
Problem statement
You are given the positions of shops and buyers on a straight street. The arrays shops and buyers contain their positions.
You can pair a shop with a buyer if the distance between them is at most d. The distance is |shops[i] - buyers[j]|. Each shop and each buyer can be used in at most one pair.
Choose pairs with these goals, in this order:
- Make as many pairs as possible.
- Among those choices, make the total distance as small as possible.
Return [numberOfPairs, totalDistance]. If no pair can be made, return [0, 0].
Shops or buyers at the same position are still separate people or shops. The input arrays may be in any order.
Function
matchShopsAndBuyers(shops: int[], buyers: int[], d: int) → long[]Examples
Example 1
shops = [12,1,6]buyers = [4,10,0]d = 2return = [3,5]After sorting, the shops are [1,6,12] and the buyers are [0,4,10]. Pair shop 1 with buyer 0, shop 6 with buyer 4, and shop 12 with buyer 10. This makes three pairs with total distance 1 + 2 + 2 = 5.
Example 2
shops = [2,30]buyers = [0,1,20]d = 5return = [1,1]Only shop 2 can reach a buyer. Pairing it with buyer 1 gives one pair with distance 1, which is better than pairing it with buyer 0.
Example 3
shops = [0,2]buyers = [1,3]d = 1return = [2,2]Pair shop 0 with buyer 1 and shop 2 with buyer 3. Both distances equal d, so both pairs are allowed.
Example 4
shops = [0,5]buyers = []d = 3return = [0,0]There are no buyers, so no pair can be made.
Constraints
0 <= shops.length, buyers.length <= 700-10^9 <= shops[i], buyers[i] <= 10^90 <= d <= 2 * 10^9- The total distance may exceed the range of a 32-bit integer. Use a 64-bit integer for it.
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Longest Chain of Nested BoxesBloomberg LP · PHONE SCREENBloomberg LP interview questions
- Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
- Cheapest Order to Cut a RodAdobe · PHONE SCREENAdobe interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Maximum Length Pair ChainInMobi · ONSITE INTERVIEWInMobi interview questions
- Alternating Jumps to the Last IndexExpedia · OAExpedia interview questions
- Merge Overlapping IntervalsAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Merge Weekday and Time IntervalsNextdoor · PHONE SCREENNextdoor interview questions
- Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions