InternDoor

The k-th biggest number

Mediumheap · sorting · quickselect

Reported in interviews at (where)

You are given a list of whole numbers nums and a number k. Line the numbers up from biggest to smallest, keeping repeats, and return the one in place k (counting from 1).

Sorting works. A heap that never holds more than k numbers, or quickselect, does less work.

Example 1
Input
nums = [3,9,4,9,1]
k = 2
Output
9

From the top: 9, 9, 4, 3, 1. The second is 9: repeats count.

Example 2
Input
nums = [3,9,4,9,1]
k = 3
Output
4

The third from the top is 4.

Limits

  • 1 <= k <= nums.length <= 100000
  • -10000 <= nums[i] <= 10000

Hints

Hint 1

Keep a min-heap of the k biggest seen so far; its top is the answer at the end.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.