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 Technical Screen rounds at Google.

What role is this question designed for?

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

Maximize 1D deliveries within distance and minimize total distance

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given positions on a 1D line: - `people`: an array of `N` integers (positions of people) - `shops`: an array of `M` integers (positions of milk-tea shops) You may match a shop to a person if the delivery distance is within a fixed limit `D`: \[ |shops[k] - people[i]| \le D \] Constraints: - Each shop can deliver to **at most one** person. - Each person can receive from **at most one** shop. ### Objective (lexicographic) 1. **Maximize** the number of deliveries (matched pairs). 2. Among all matchings that achieve the maximum number of deliveries, **minimize** the **total** delivery distance: \[ \sum |shops[k] - people[i]| \] ### Task Given `people`, `shops`, and `D` (e.g., `D = 5`), return: - `maxDeliveries`: the maximum number of deliveries possible - `minTotalDistance`: the minimum total distance among matchings that achieve `maxDeliveries` ### Notes - Positions may be unsorted; you may sort them. - Specify and handle edge cases such as duplicates, empty arrays, and when no pairs are feasible.

Quick Answer: This question evaluates combinatorial optimization and constrained matching skills, focusing on reasoning about distance-based pairings, lexicographic objective prioritization, and edge-case handling such as duplicates and empty inputs.

You are given two arrays of integer positions on a 1D number line: `people` and `shops`, along with a non-negative integer `D`. A shop can deliver to a person only if their distance is at most `D`, meaning `abs(shops[k] - people[i]) <= D`. Each shop can serve at most one person, and each person can receive from at most one shop. Your task is to return a tuple `(maxDeliveries, minTotalDistance)` where `maxDeliveries` is the largest number of valid shop-person matches possible, and `minTotalDistance` is the smallest possible sum of delivery distances among all matchings that achieve `maxDeliveries`. If no deliveries are possible, return `(0, 0)`. The input arrays may be unsorted and may contain duplicates.

Constraints

0 <= len(people), len(shops) <= 2000
-10^9 <= people[i], shops[j] <= 10^9
0 <= D <= 10^9
Positions may be unsorted and may contain duplicates

Examples

Input: ([1, 7, 10], [2, 6, 12], 2)

Expected Output: (3, 4)

Explanation: All three people can be matched: 1->2, 7->6, and 10->12 with distances 1, 1, and 2. That gives 3 deliveries with total distance 4.

Input: ([0, 4], [2, 5], 3)

Expected Output: (2, 3)

Explanation: The best matching is 0->2 and 4->5. This achieves the maximum 2 deliveries with total distance 2 + 1 = 3.

Input: ([5, 5, 10], [4, 6, 11], 1)

Expected Output: (3, 3)

Explanation: A valid optimal matching is 5->4, 5->6, and 10->11. All 3 deliveries are made, and the total distance is 1 + 1 + 1 = 3.

Input: ([-3, 0, 4], [-4, 1], 1)

Expected Output: (2, 2)

Explanation: Match -3->-4 and 0->1. The person at 4 cannot be served within distance 1. So the result is 2 deliveries with total distance 2.

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

Expected Output: (0, 0)

Explanation: There are no people to serve, so no deliveries can be made.

Input: ([0, 100], [10, 90], 5)

Expected Output: (0, 0)

Explanation: No shop is within distance 5 of any person, so no valid pair exists.

Hints

Sort both arrays first. On a 1D line, there is always an optimal solution with no crossing matches.
Use dynamic programming on prefixes: for the first `i` people and first `j` shops, store the best pair `(deliveries, totalDistance)` in lexicographic order.

Quick Overview

This question evaluates combinatorial optimization and constrained matching skills, focusing on reasoning about distance-based pairings, lexicographic objective prioritization, and edge-case handling such as duplicates and empty inputs.