Katkat
Back

Find Clients Outside Provider Coverage

OscarSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests spatial data processing and efficient set operations to identify gaps in service coverage between clients and providers based on distance and specialty requirements.

Problem Statement

You are given a list of clients, a list of providers, and a maximum distance threshold. Each client requires a specific set of specialties, and each provider offers a set of specialties at a specific (x, y) location. A provider covers a client if their distance is less than or equal to distance. The Euclidean distance between (x1, y1) and (x2, y2) is sqrt((x1-x2)^2 + (y1-y2)^2).

Your task is to return a list of IDs of clients who have at least one required specialty that is NOT covered by any provider within the allowed distance. Maintain the original order of the clients list.

Function Signature

def find_uncovered_clients(clients, providers, distance):
    # clients: List of dicts {'id': int, 'coords': (x, y), 'specialties': set}
    # providers: List of dicts {'id': int, 'coords': (x, y), 'specialties': set}
    # distance: float
    # returns: List of int (client IDs)

Examples

Example 1:

  • Clients: [{'id': 1, 'coords': (0, 0), 'specialties': {'Cardio', 'Dentist'}}]
  • Providers: [{'id': 10, 'coords': (1, 1), 'specialties': {'Cardio'}}]
  • Distance: 2.0
  • Output: [1] (Provider 10 is within distance, but missing 'Dentist').

Example 2:

  • Clients: [{'id': 2, 'coords': (0, 0), 'specialties': {'Eye'}}]
  • Providers: [{'id': 11, 'coords': (0, 1), 'specialties': {'Eye'}}]
  • Distance: 2.0
  • Output: [] (Client is fully covered).

Constraints

  • Number of clients and providers: up to 10,000 each.
  • Coordinates: integers between -10,000 and 10,000.
  • Specialties: represented as strings.
  • Time limit: Should perform efficiently given the large query volume.

Hints

Hint 1

For every client, track a set of 'satisfied specialties' initialized as empty.

Hint 2

Instead of checking all providers for every client, filter providers by distance first or iterate through providers to update coverage maps for nearby clients.

Hint 3

Consider using a spatial partitioning approach or a simple grid-based bucket system if the number of providers becomes very large.

Follow-up questions

  • How would you optimize the search if the number of clients and providers increased to 1,000,000?
  • What data structures would you use if providers frequently changed their specialty offerings?
  • How does the time complexity change if we need to return the specific missing specialty for each uncovered client?