Katkat
Back

Find the N-th Highest Bid in an Auction Log Without a Heap

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Given an unordered list of auction bids, return the n-th highest one, treating two equal bid amounts as distinct entries, while a heap-based solution is off the table. Tests selection algorithms faster than full sorting, correct handling of duplicate values, and justifying the achieved time complexity.

An auction system logs every bid as it comes in, in no particular order. Given the list of bids and an integer n, return the n-th highest bid, where equal bid amounts are counted as separate entries rather than merged.

def nth_highest_bid(bids: list[int], n: int) -> int:

bids holds every submitted bid amount in the order received. n selects which highest bid to return, counting from 1.

Rules

  • Equal amounts are not deduplicated: in [70, 70, 20], both the 1st and 2nd highest bids are 70, and the 3rd highest is 20.
  • No heap or priority queue of any kind, including heapq — assume the interviewer has explicitly ruled it out, since it's the obvious first answer.
  • The interviewer will ask you to justify the time complexity you land on, including against already-sorted input and input with many repeated bid amounts.

Constraints

  • 1 <= n <= len(bids) <= 10^5
  • -10^9 <= bids[i] <= 10^9

Examples

Input:  bids = [70, 20, 90, 40, 90, 10], n = 2
Output: 90

Sorted descending: [90, 90, 70, 40, 20, 10]. The 2nd entry is 90, since the two 90s each count.

Input:  bids = [70, 20, 90, 40, 90, 10], n = 4
Output: 40

Input:  bids = [-50, 0, -50, 30], n = 3
Output: -50

Sorted descending: [30, 0, -50, -50]. The 3rd entry is -50.

Hints

Hint 1

Sorting the whole list works but does more work than necessary — you only need one position, not a full order.

Hint 2

Quickselect (the selection-flavored sibling of quicksort) finds a single rank in expected linear time by recursing into only the side of a partition that contains the target position.

Hint 3

A standard 3-way partition (less than / equal to / greater than the pivot) handles heavy duplication cleanly, since every value equal to the pivot resolves in one step instead of being repeatedly re-partitioned.

Hint 4

Picking the pivot uniformly at random, rather than always the first or last element, is what keeps already-sorted input from triggering quickselect's quadratic worst case.

Follow-up questions

  • How would you answer many different values of n against the same fixed bid list efficiently, without re-running quickselect from scratch each time?
  • How would you adapt this to a stream of bids where you must always be able to answer 'what's the n-th highest so far' without storing the entire history?
  • What's the worst realistic input you'd stress-test this against, beyond sorted and duplicate-heavy arrays?
  • If heaps genuinely were allowed, how would a fixed-size min-heap approach compare in time and space for a large list and a small n?