How should I practice Find Median from Data Stream?

Start by reading the full statement, solve the visible examples, then compare the pattern against related XPeng Motors phone screen problems in FastPrep.

Is Find Median from Data Stream associated with XPeng Motors?

FastPrep tags this as a XPeng Motors phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Design

Find Median from Data Stream

Learn this problem

● Hard

XPeng MotorsFULLTIMEPHONE SCREEN

Problem statement

Process a finite sequence of operations while maintaining every integer added so far. Each row in operations has one of these forms:

["add", value] inserts the integer represented by value.
["median"] queries the current median.

For an odd number of stored values, the median is the middle value after sorting. For an even number, it is the arithmetic mean of the two middle values. Return a double[] containing the median-query results in encounter order. Add operations produce no output.

Function

processMedianOperations(operations: String[][]) → double[]

Examples

Example 1

operations = [["add","5"],["median"],["add","1"],["median"],["add","9"],["median"]]return = [5.0,3.0,5.0]

The stored multisets at the three queries are [5], [1,5], and [1,5,9], whose medians are 5, 3, and 5.

Example 2

operations = [["add","-4"],["add","8"],["median"],["add","8"],["median"],["add","20"],["median"]]return = [2.0,8.0,8.0]

The queries observe [-4,8], [-4,8,8], and [-4,8,8,20].

Example 3

operations = [["add","1000000000"],["add","999999999"],["median"]]return = [999999999.5]

The arithmetic mean of the two middle values is 999999999.5.

Constraints

1 <= operations.length <= 100000
Every row is either ["add", value] or ["median"].
Each added value fits in a signed 32-bit integer.
Every median query occurs after at least one add operation.
At least one median query appears.