Pular para o conteúdo

Percentis de latência por nearest rank

Fácil#percentiles#sorting~10 min

A missão

Problema

Um painel mostra a latência das requisições como percentis, e não como média. Dadas uma lista de amostras de latência em milissegundos e uma lista de percentis, como [50, 90, 99], retorne um dicionário de cada percentil para o seu valor usando o método nearest rank (posto mais próximo): ordene as amostras, e o p-ésimo percentil é a amostra na posição ceil(p × n / 100), indexada a partir de 1, em que n é o número de amostras. Use aritmética inteira para a posição. Há até 1.000.000 de amostras.

Exemplos

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ê: uma requisição lenta em dez é invisível no p90 e é a história toda no p99
Input:  latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Por quê: com 100 amostras, o p-ésimo percentil é simplesmente o p-ésimo menor valor
Input:  latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Por quê: edge case: uma única amostra é todos os percentis

Dicas

0 / 3

Tempo-alvo
O(n log n + q)
Espaço-alvo
O(n)

Restrições

  • at most 10⁶ samples

Travou na ideia, e não no código? O básico de observabilidade explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado