alt Hacker NewsAnd what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?
And what of the likelihood that the original collection is modified when using the quickselect algorithm, thus introducing observable side effects in what could reasonably be considered a "read-only" computation?
And there lies the tradeoffs you need to consider as part of an interview question.
But if the best alternative is to sort the whole collection, then Quickselect doesn't introduce a new problem. You either accept that modifying the collection in place is an acceptable behaviour (and describe that in your API docs) or you make a copy of the collection and operate on that.
Given a choice between quickselect and quicksort, quickselect will get the answer with less overhead and no additional constraints (because it's essentially the same algorithm with unnecessary steps removed).
There are alternative approaches that don't require a full copy/sort, but they either require a partial copy + partial sort, or multiple passes through the collection.