How should I practice Running Medians and Percentiles?

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

Is Running Medians and Percentiles associated with StackAdapt?

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

Problem · Array

Running Medians and Percentiles

Learn this problem

● Hard

StackAdaptFULLTIMEPHONE SCREEN

Problem statement

Process a finite sequence of statistic operations while retaining every value that has been added. Each row of operations has one of these forms:

["add", value] adds the signed integer written as a decimal string. Duplicate values are retained.
["median"] appends the median of all values added so far. For an even number of values, use the arithmetic mean of the two middle values.
["percentile", p] appends the nearest-rank percentile for the integer p from 1 through 100. If n values have been added, sort them conceptually and return the value at one-based rank ceil(p * n / 100).

Every query occurs after at least one add. Return only query results, in operation order, as floating-point values.

Function

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

Examples

Example 1

operations = [["add","1"],["add","2"],["median"],["add","3"],["median"],["percentile","50"],["percentile","100"]]return = [1.5,2.0,2.0,3.0]

The first median averages 1 and 2. After adding 3, the median is 2; the nearest-rank 50th and 100th percentiles are 2 and 3.

Example 2

operations = [["add","5"],["add","5"],["add","-1"],["percentile","25"],["median"],["add","9"],["percentile","75"]]return = [-1.0,5.0,5.0]

With values [-1, 5, 5], the nearest-rank 25th percentile is the first value and the median is 5. After adding 9, rank ceil(75 * 4 / 100) = 3 still contains 5.

Constraints

1 <= operations.length <= 100000.
Each operation is ["add", value], ["median"], or ["percentile", p].
Each added value is a canonical decimal string for an integer in [-10^9, 10^9].
For a percentile operation, 1 <= p <= 100.
Each median or percentile operation follows at least one add operation.
Duplicate values are distinct observations.