Finding numbers near the median in linear time Problem:
Describe (English is enough) a linear algorithm that, given a set $S$ of $n$ distinct numbers and a positive integer $k \leq n$, returns the $k$ numbers in $S$ that are closest to the median of $S$.
Answer:
I interpret the term linear algorithm to mean one that runs in $O(n)$ time. It is not clear to me if that means worst case or average case. I would tend to think worst case.
\newline
I claim that problem may not have a unique solution. For example, if we are given
$S = \{ 1, 2, 3, 4, 5 \}$ and $k = 2$ then we have the following two valid solutions:
\newline
$S = \{ 2, 3 \}$ and $S = \{ 3, 4 \}$.
Here is my algorithm, which I do not believe meets the performance requirements
of the question:
Let ans be the set of numbers we want to return.
Compute the median of S and call that value m.

Initialize the set ans to the first k elements of S.
// One data structure to hold ans would be an array. A better choice might be
// a binary tree / heap.
for i = k+1 to n (inclusive)
       if S[i] is closer to the median then the element of ans that is farthest
            away from the median then
                update ans by replacing that element with S[i]
       end if
end for
return ans

I am assuming that we can find the median in $O(n)$ time. Depending on the data structure chosen for ans, the running time for the code will be $O( n \log k )$ which is linear in $n$.
This does not seem right to me. Is it? If it is wrong, where did I go wrong?
Does this problem even have a valid solution?
There is an algorithm that finds the $\ell$-th smallest element in an array of length $n$ in time $O(n)$. You can find the $(n-k)/2$-th smallest and the $(n+k)/2$-th smallest elements in $O(n)$ using this algorithm, and then, using an additional pass, find all elements in between.