How should I practice Fixed-K Kth Largest Stream?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google onsite interview problems in FastPrep.

Is Fixed-K Kth Largest Stream associated with Google?

FastPrep tags this as a Google onsite interview coding practice problem when the problem catalog has that company and stage context.

Fixed-K Kth Largest Stream

Google● MediumINTERNONSITE INTERVIEW

Learn

Problem statement

You are given a fixed rank k, an initial array of integers initialValues, and an array additions whose values arrive in order.

After each value in additions is inserted, report the k-th largest value among every value seen so far. Duplicate occurrences occupy separate positions in the ranking.

Return one result for each arriving value, in the same order as additions.

Implement kthLargestAfterEachAdd(k, initialValues, additions).

Function

kthLargestAfterEachAdd(k: int, initialValues: int[], additions: int[]) → int[]

Examples

Example 1

k = 3initialValues = [4,5,8,2]additions = [3,5,10,9,4]return = [4,5,5,8,8]

After adding 3, the three largest values are 8, 5, 4. Later additions raise the third-largest value first to 5 and then to 8.

Example 2

k = 2initialValues = [5,5]additions = [5,4,6]return = [5,5,5]

Repeated values occupy separate ranks. Even after 6 arrives, the second-largest value remains 5.

Example 3

k = 1initialValues = []additions = [-10,-5,-7]return = [-10,-5,-5]

With k = 1, each result is the maximum value seen so far.

Constraints

0 <= initialValues.length <= 200000.
1 <= additions.length <= 200000.
initialValues.length + additions.length <= 200000.
1 <= k <= initialValues.length + 1.
Every value fits in a signed 32-bit integer.