Questions d'entretien

Entretien pour Algorithm Developer

-New York, NY

Hudson River Trading

Asked how to find the kth largest element of a sequence of n elements.

Répondre

Réponses aux questions d'entretien

3 réponse(s)

6

First algorithm: sort the sequence in O(n log n) time and select the kth element. Second algorithm: construct a max-heap out of the n elements, which can be done in O(n) time and then repeatedly remove the largest element until you reach the kth element. This step takes O(k log n) time and so overall the algorithm runs in O(n + k log n) time. Third algorithm: Use quick select: partition the sequence using a random element as the pivot and recurse on the partition that contains the kth element, which you can determine based on the sizes of the two partitions. This runs in expected time O(n) and runs with high probability in O(n) time. It is also possible to extend this algorithm to run deterministically in O(n) time (see Deterministic Selection algorithm).

Utilisateur anonyme le

1

The third algo is O(n)

Utilisateur anonyme le

0

we can maintain a min-heap of size k, each time if new element is larger than min element in the heap, remove the root and heapify, otherwise don't update

Utilisateur anonyme le

Ajouter des réponses ou des commentaires

Pour commenter ceci, connectez-vous ou inscrivez-vous.