How should I practice Dynamic Order-Statistic Binary Search Tree?

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

Is Dynamic Order-Statistic Binary Search Tree associated with Salesforce?

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

Dynamic Order-Statistic Binary Search Tree

Salesforce● HardFULLTIMEONSITE INTERVIEW

Learn

Problem statement

Maintain an initially empty binary search tree of unique integer keys. Process each operation in order:

[1, value] inserts value. Inserting an existing key is a no-op.
[2, value] deletes value. Deleting a missing key is a no-op.
[3, k] asks for the one-indexed kth-smallest current key.

Every query rank is valid for the current tree. Return one integer for each query, in query order.

Store each node's subtree size so a query descends by comparing k with the left-subtree size.

Function

dynamicKthSmallest(operations: int[][]) → int[]

Examples

Example 1

operations = [[1,5],[1,3],[1,7],[3,2],[2,5],[3,2]]return = [5,7]

The first query sees [3,5,7]. After deleting 5, the second-smallest key is 7.

Example 2

operations = [[1,4],[1,4],[2,9],[3,1],[2,4],[1,2],[3,1]]return = [4,2]

The duplicate insertion and missing deletion are no-ops. The two valid queries return 4 and 2.

Constraints

1 <= operations.length <= 100000.
Every operation has one of the three documented forms.
All keys are signed 32-bit integers.
Every query rank is between 1 and the current number of keys.