Fragen aus Vorstellungsgesprächen für Software engineer, von Bewerbern geteilt
Find the top minimal m elements of n elements in O(n) time
A basic heap would take O(n lg n) time, which wouldn't work here. One step better would be to limit the heap to m elements, which would make it O(n lg m), which is O(n) for sufficiently small m. This may be simply undoable for m == n in O(n) time.
I take that back; it's not undoable. You can find the m'th smallest element in O(n) time; C++ has this implemented as std::nth_element, even. Once you have the m'th smallest element, sweep the input another time and bucket everything smaller than it, which is a second O(n) pass. But yeah; a heap will always be O(n lg m) here, which becomes O(n lg n) if m==n.