Feature #1: Select Closest Drivers
Explore how to identify the closest drivers to a user in a city modeled as a Cartesian plane. Understand using Euclidean distance and max-Heap data structures to efficiently select the nearest drivers for Uber ride allocation while considering time and space complexities.
We'll cover the following...
Description
The first functionality we’ll be building is to locate the nearest available drivers within the vicinity of a user. There are numerous Uber drivers roaming around in a city. For simplicity, we’ll consider the city as a Cartesian plane and assign the coordinates (0, 0) to the user’s location. When a user wants to book a ride, we’ll simply find k drivers with the shortest distance on the Cartesian plane. Here, k is the minimum threshold for choosing the closest drivers.
We’ll be provided an array containing a set of points on the Cartesian plane and a number k. Each set of points will represent the location of a driver. We need to find the k closest drivers from the user’s location.
Solution
The Euclidean distance between a point P(x,y) and the origin can be calculated using the following formula:
...