FastPrep
Problem · Tree

Dynamic Order-Statistic Binary Search Tree

Learn this problem
● HardSalesforce logoSalesforceFULLTIMEONSITE INTERVIEW
See Salesforce hiring insights

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.

More Salesforce problems

drafts saved locally
public int[] dynamicKthSmallest(int[][] operations) {
    // TODO: maintain subtree sizes through every update and rank query.
}
operations[[1,5],[1,3],[1,7],[3,2],[2,5],[3,2]]
expected[5,7]
checking account