Feature #7: Highest Rank
Explore how to identify the kth highest driver rank from an unsorted list by using a min-heap. This lesson shows you how to efficiently manage driver prioritization without starving lower-ranked drivers. Learn to implement heap operations and analyze the time and space complexity involved in this approach.
We'll cover the following...
Description
At Uber, each driver is assigned a rank based on the reviews they receive from their passengers. Currently, the system prioritizes drivers with the highest rank and assigns them instant rides. We want to change this driver selection criterion such that drivers with lower ranks don’t get starved while the drivers with high ranks keep getting rides. The drivers’ ranks are maintained in an unsorted array. We’ll call a hidden API that will provide us with a number k. The value of this k can range from 1 to the size of our rank array. Once we have a value k, we need to find the kth highest driver rank.
We’ll be provided with an unsorted array of integers representing the divers’ ranks. The drivers are represented by the index of this array. The value of k will be made available from the hidden API. Our task will be to determine the kth highest rank, so the driver associated with that rank can be selected.
Solution
Just like in Feature #1, we can use a heap to obtain the kth highest rank from our unsorted array. We now have to select the largest number, so we’ll use a min-heap. We’ll insert ranks of the first k drivers ...