Implement k-th largest in a number stream
Problem Description
You are tasked with designing a small library to monitor statistics over a continuous stream of integers.
Implement a data structure that, given an integer k and an initial list of integers, supports the following operation:
add(val): Insert the integervalinto the stream and return the k-th largest element among all elements seen so far (including the newly added one).
More formally, after each call to add, if you consider all numbers that have been provided (both from the initial list and all numbers added subsequently), and sort them in non-decreasing order, you should return the element that is k positions from the end. You may assume that k is always valid, meaning there will always be at least k elements available after each add call.
API to Implement
Define a class or type with:
- A constructor that takes:
k(an integer)nums(a list/array of integers, possibly empty)
- A method:
add(val: int) -> intthat insertsvaland returns the current k-th largest element.
Constraints
- You may assume:
1 <= k <= 10^4- At most
10^4calls toaddwill be made. - Each integer value fits within a standard 32-bit signed integer range.
- Your design should be efficient enough to handle the worst-case number of
addcalls within typical interview time complexity expectations. - You are only required to describe the code-level behavior and interface; a working implementation is not necessary.
AI interview prep
Core dilemma
Efficiently maintaining a dynamic ordered subset of a potentially unbounded stream to query a specific rank (k-th largest) without storing or sorting the entire stream, optimizing for `add` operation performance.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Implement k-th largest in a number stream
Problem Description
You are tasked with designing a small library to monitor statistics over a continuous stream of integers.
Implement a data structure that, given an integer k and an initial list of integers, supports the following operation:
add(val): Insert the integervalinto the stream and return the k-th largest element among all elements seen so far (including the newly added one).
More formally, after each call to add, if you consider all numbers that have been provided (both from the initial list and all numbers added subsequently), and sort them in non-decreasing order, you should return the element that is k positions from the end. You may assume that k is always valid, meaning there will always be at least k elements available after each add call.
API to Implement
Define a class or type with:
- A constructor that takes:
k(an integer)nums(a list/array of integers, possibly empty)
- A method:
add(val: int) -> intthat insertsvaland returns the current k-th largest element.
Constraints
- You may assume:
1 <= k <= 10^4- At most
10^4calls toaddwill be made. - Each integer value fits within a standard 32-bit signed integer range.
- Your design should be efficient enough to handle the worst-case number of
addcalls within typical interview time complexity expectations. - You are only required to describe the code-level behavior and interface; a working implementation is not necessary.