Feature #5: Eligible Candidates

Description

We have n machines that are part of a cluster. We need to elect a leader. Leader election amongst all n machines would generate a lot of traffic and take a lot of time.

To optimize traffic and time, we have come up with a scheme that will reduce search space. Each machine is assigned a unique identifier, which is placed in a sorted array. A random number is picked, and k machines with IDs closest to the randomly drawn number are eligible candidates for leadership. Once the k machines are identified, the leader election from amongst these will take place.

Given a sorted integer array servers, a randomly picked number num, and an integer k, your task is to find k machines with IDs closest to the random number. The IDs of the machines should also be sorted in ascending order.

An ID a is closer to num than an ID b, if |a - num| < |b - num|. In case |a - num| == |b - num|, then a is closer to num if a < b.

Note: The servers array is sorted in ascending order and 1 <= k <= servers.length.

The following examples may clarify these requirements:

Solution

If the array’s length is large and k is very small, we do not have to look at most of the numbers in this array. We will start by finding the number closest to num in servers. Since our input is sorted, we can safely assume that the second closest number to num will either be to the left or right of the first closest number. Similarly, the third closest number to num will either be towards the first number’s left or the second number’s right.

We can use the concept of a sliding window to approach this problem. Using two ...