İçeriğe geç

Nearest rank ile gecikme yüzdelikleri

Kolay#percentiles#sorting~10 dk

Görev tanımı

Problem

Bir dashboard istek gecikmesini (latency) bir ortalama yerine yüzdelikler olarak raporluyor. Milisaniye cinsinden gecikme örneklerinden oluşan bir liste ve [50, 90, 99] gibi bir yüzdelik listesi verildiğinde, nearest-rank yöntemiyle her yüzdelikten değerine giden bir dict döndür: örnekleri sırala; p. yüzdelik, n örnek sayısı olmak üzere 1 tabanlı ceil(p × n / 100) sırasındaki örnektir. Sıra için tam sayı aritmetiği kullan. En fazla 1.000.000 örnek var.

Örnekler

Input:  latencies = [12, 15, 11, 13, 240, 14, 12, 16, 13, 12], ps = [50, 90, 99]
Output: {50: 13, 90: 16, 99: 240}
Neden: ondaki bir yavaş istek p90'da görünmez, p99'da ise bütün hikâyedir
Input:  latencies = 1 to 100, ps = [50, 90, 99, 100]
Output: {50: 50, 90: 90, 99: 99, 100: 100}
Neden: 100 örnekle p. yüzdelik basitçe p. en küçüktür
Input:  latencies = [7], ps = [50, 99]
Output: {50: 7, 99: 7}
Neden: edge case: tek bir örnek her yüzdeliktir

İpuçları

0 / 3

Hedef zaman
O(n log n + q)
Hedef alan
O(n)

Kısıtlar

  • at most 10⁶ samples

Kodda değil de fikirde mi takıldın? Gözlemlenebilirliğin temelleri bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case