How should I practice Dynamic K-th Largest Queries?

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

Is Dynamic K-th Largest Queries associated with Google?

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

Dynamic K-th Largest Queries

Google● HardNEW GRADONSITE INTERVIEW

Learn

Problem statement

Process an ordered sequence of operations against an initially empty multiset of integers.

INSERT value inserts one occurrence of value.
FIND k returns the zero-indexed kth-largest value currently stored.

Duplicate values occupy separate ranks. Every FIND operation uses a valid k. Return the results of all FIND operations in query order.

Design the query operation to be substantially faster than sorting the entire multiset after every insertion.

Function

processKthLargest(operations: String[][]) → int[]

Examples

Example 1

operations = [["INSERT","3"],["INSERT","3"],["INSERT","2"],["FIND","0"],["FIND","1"],["FIND","2"]]return = [3,3,2]

The sorted multiset is [3,3,2], and duplicates occupy the first two ranks.

Example 2

operations = [["INSERT","-1"],["INSERT","5"],["FIND","1"],["INSERT","10"],["FIND","1"]]return = [-1,5]

Before inserting 10, the second-largest value is -1. Afterward it is 5.

Constraints

1 <= operations.length <= 100000.
Every operation has the required operand and is either INSERT or FIND.
Inserted values fit in a signed 32-bit integer.
Every FIND k satisfies 0 <= k < current multiset size.