Comment

Comment by timv

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.

parent timv 3 months ago

No comments yet

Be the first to share your thoughts.

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton