Geek asks and answers

Find a subset with elements that are farthest from each other

I have an interview question that I cannot understand. Given an array of size N, find a subset of size k so that the elements in the subset are farthest from each other. In other words, maximize the minimum pairwise distance between elements.

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

For the brutforce method, you need to find all subsets of size k that are exponential at runtime.

One of my ideas was to take values ​​evenly distributed across the array. I mean this

  • Take the first and last items
  • find the difference between them (in this case 10-1) and divide it by k ((10-1) / 3 = 3)
  • move 2 pointers inward at both ends, choosing items that are +/- 3 from your previous selection. So, in this case, you start at 1 and 10 and find the closest elements to 4 and 7. It will be 6.

This is based on the intuition that elements should be distributed as evenly as possible. I do not know how to prove that this works / does not work. If someone knows how or better is the algorithm, split up. Thank!

+12
source share
4 answers

This can be resolved in polynomial time using DP.

The first step, as you said, sorts the list A. Let X [i, j] be the solution to select j elements from the first i elements of A.

Now X [i + 1, j + 1] = max (min (X [k, j], A [i + 1] -A [k])) over k <= i.

, .

(1,2,6,10) :

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1
+6

, . , , .

, .

, , : - , , ( , ) , . k, - O(N^k).

- , , . , 10, 11. - , -- , . , , - .

, , k , . M, O(N*M) , , O(N*log(M)), N - .

, , . , O(N*log(M/k)).

+2

, . , .

Let suppose you have an array X = (X1, X2, ..., Xn)

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n

j <- 1
while j < n - k do
    X.Exclude(min(Energy(Xi)), 1 < i < n)
    j <- j + 1
    n <- n - 1
end while
0
$length = length($array);
sort($array); //sorts the list in ascending order
$differences = ($array << 1) - $array; //gets the difference between each value and the next largest value
sort($differences);  //sorts the list in ascending order
$max = ($array[$length-1]-$array[0])/$M; //this is the theoretical max of how large the result can be
$result = array();
for ($i = 0; i < $length-1; $i++){
    $count += $differences[i];
    if ($length-$i == $M - 1 || $count >= $max){ //if there are either no more coins that can be taken or we have gone above or equal to the theoretical max, add a point
        $result.push_back($count);
        $count = 0;
        $M--;
    }
}
return min($result)

: , , ( ), , , arent ; , . .

. ( radix ).

, 1, 4, 7, 100 200 M = 3 :

$differences = 3, 3, 93, 100
$max = (200-1)/3 ~ 67
then we loop:
$count = 3, 3+3=6, 6+93=99 > 67 so we push 99
$count = 100 > 67 so we push 100
min(99,100) = 99

This is a simple exercise to convert it into a solution that I have set, which I leave to the reader (PS, after I read this in the book all the time, I always wanted to say this: P)

0
source

More articles:


All Articles