Saltar al contenido

Percentiles de latencia por nearest rank

Fácil#percentiles#sorting~10 min

La misión

Problema

Un panel informa la latencia de las solicitudes como percentiles en lugar de un promedio. Dada una lista de muestras de latencia en milisegundos y una lista de percentiles como [50, 90, 99], devuelve un dict de cada percentil a su valor usando el método del rango más cercano (nearest rank): ordena las muestras, y el percentil p es la muestra en el rango ceil(p × n / 100), contado desde 1, donde n es la cantidad de muestras. Usa aritmética entera para el rango. Hay hasta un millón de muestras.

Ejemplos

Input:  latencies = [12, 15, 11, 13, 240, 14, 12, 16, 13, 12], ps = [50, 90, 99]
Output: {50: 13, 90: 16, 99: 240}
Por qué: una solicitud lenta de cada diez es invisible en p90 y lo es todo en p99
Input:  latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Por qué: con 100 muestras, el percentil p es simplemente el p-ésimo valor más pequeño
Input:  latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Por qué: caso límite: una sola muestra es todos los percentiles

Pistas

0 / 3

Tiempo objetivo
O(n log n + q)
Espacio objetivo
O(n)

Restricciones

  • at most 10⁶ samples

¿Lo que te frena es la idea y no el código? Fundamentos de observabilidad lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio