I have an interview question that I can’t seem to figure out. Given an array of size N, find the subset of size k such that the elements in the subset are the furthest apart from each other.
Example:
Array = [1,2,6,10]
k = 3
answer = [1,6,10]
UPDATE : meaning of furthest apart : the difference b/w any two elements in the subset is mimimum .
What do you mean “furthest apart”? Maximizing the minimum of differences between any 2 values in the set?
In that case, you could bin-search the answer. If you think that the answer is at least D, you can start with the first element and always greedily pick the smallest element that’s >= D + the last picked element. If there are >= K such elements, it can be done (if there are more, you just pick the last K); otherwise, it obviously isn’t possible for this D. If you sort this array beforehand, you can do this in just one pass for a fixed D. And since it’s obviously always possible for any D <= answer and impossible for D > answer, binsearch works. Time: O(N log A_max).
what do u mean by furthest apart from each other? is it the indexes or the difference b/w any two elements?
the_c0der: Is the trolling (not specifying to which possibility yes) intentional? 
There are 4 possibilities, actually: of indexes or values, and maximum difference or minimum difference. But the ones with maximum difference are trivial, and what’s the point in values if we’re only interested in indexes?
I believe you meant “the minimum difference between any two elements is maximum”
In that case, see my answer below.