How should I practice Dynamic Median with Additions and Deletions?

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

Is Dynamic Median with Additions and Deletions associated with ByteDance?

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

Problem · Heap

Dynamic Median with Additions and Deletions

Learn this problem

● Hard

ByteDanceFULLTIMEONSITE INTERVIEW

Problem statement

Process operations on an integer multiset and return one result for every median query.

[1, x] adds one occurrence of x.
[2, x] removes one occurrence of x, or does nothing when x is absent.
[3] queries the current median.
For a nonempty multiset, return the median as a reduced numerator/denominator string with a positive denominator. For an empty multiset, return the literal string null.

Function

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

Examples

Example 1

operations = [[1,5],[1,1],[3],[1,9],[3],[2,5],[3],[2,1],[2,9],[3]]return = ["3/1","5/1","5/1","null"]

The queried multisets are {1,5}, {1,5,9}, {1,9}, and the empty multiset.

Example 2

operations = [[1,2],[1,2],[1,8],[3],[2,2],[3],[2,2],[3],[2,2],[3]]return = ["2/1","5/1","8/1","8/1"]

Each deletion removes only one duplicate occurrence. The final deletion of absent value 2 is a no-op.

Constraints

1 <= operations.length <= 200000.
Every operation is exactly [1, x], [2, x], or [3].
-1000000000 <= x <= 1000000000.