URL kısaltıcı kapasite tahmini
Görev tanımı
Problem
Bir URL kısaltıcı (URL shortener) mülakatının açılış sayılarını bir kapasite tahminine çevir. Günlük yeni kısa link sayısı, yazma başına okuma, link başına saklanan byte, saklama yılı ve bir tepe/ortalama çarpanı verildiğinde şunları içeren bir dict döndür: write_qps ve read_qps, saniye başına ortalama istekler, yukarı yuvarlanmış; peak_read_qps, günlük okumalar çarpı saniye başına tepe çarpanı, yukarı yuvarlanmış; storage_tb, saklama süresi boyunca tutulan bütün linkler, 10¹² byte'lık terabyte cinsinden, 1 ondalığa yuvarlanmış; code_length da her link için yer bırakan, 62 karakter (a-z, A-Z, 0-9) üzerinden en kısa kod. Günde 86.400 saniye ve yılda 365 gün kullan; yukarı yuvarlama için tam sayı aritmetiği kullan.
Örnekler
Input: new_per_day = 100_000_000, reads_per_write = 100, bytes_per_url = 500, years = 10, peak = 3
Output: {'write_qps': 1158, 'read_qps': 115741, 'peak_read_qps': 347223, 'storage_tb': 182.5, 'code_length': 7}
Neden: 365 milyar link 7 karakter ister, çünkü 62⁶ yalnız yaklaşık 57 milyar
Input: new_per_day = 1_000_000, reads_per_write = 10, bytes_per_url = 500, years = 5, peak = 2
Output: {'write_qps': 12, 'read_qps': 116, 'peak_read_qps': 232, 'storage_tb': 0.9, 'code_length': 6}
Neden: 100 kat küçük bir servis de yine 6 karakter ister, çünkü 62⁵ bir milyarın altında
Input: new_per_day = 1, reads_per_write = 1, bytes_per_url = 100, years = 1, peak = 1
Output: {'write_qps': 1, 'read_qps': 1, 'peak_read_qps': 1, 'storage_tb': 0.0, 'code_length': 2}
Neden: edge case: yukarı yuvarlama her oranı en az 1 tutar, 365 link de tek karakterlik 62 kodu zaten aşar
İpuçları
0 / 3
Her şey günlük sayılardan başlar. Günlük okumalar, günlük yeni linkler çarpı okuma oranıdır; toplam linkler de günlük yeni linkler × 365 × yıl.
Tam sayılarda tavan bölmesi -(-a // b). Tepe çarpanını bölmeden önce uygula, böylece yuvarlama bir kez olur.
Kod uzunluğu için 1'den başla ve 62 üzeri o sayı toplam link sayısından küçük olduğu sürece büyüt.
- Hedef zaman
- O(log(total links))
- Hedef alan
- O(1)
Çözüm
Bir tasarım mülakatında kapasite tahmini bir avuç çarpmadır ve değeri, onları mülakatçının takip edebileceği sabit bir sırayla yapmakta yatar: günlük, sonra saniyelik, sonra saklama süresi boyunca. Oranlar yukarı yuvarlanır, çünkü saniyede 1.157,4 yazma için boyutlandırılmış bir sunucu filosu bir yazma eksiktir; tepe çarpanı da yalnız tek bir yuvarlama adımı olsun diye bölmeden önce uygulanır. Depolama, toplam link sayısı çarpı kayıt boyutudur ve ondalık terabyte cinsinden raporlanır. Kod uzunluğu aynı toplamdan çıkar: her ek base-62 karakteri alanı 62 ile çarpar, bu yüzden döngü sığan ilk uzunlukta durur; 365 milyar link için 7 karakter. Döngü O(log total) kez döner ve geri kalan her şey sabittir; pratik girdiler için zaman ve alan O(1).
def url_shortener_capacity(new_per_day, reads_per_write, bytes_per_url, years, peak):
day = 86_400
reads_per_day = new_per_day * reads_per_write
total = new_per_day * 365 * years # links kept over the retention period
length = 1
while 62 ** length < total: # each character multiplies the space by 62
length += 1
return {
"write_qps": -(-new_per_day // day), # ceiling division
"read_qps": -(-reads_per_day // day),
"peak_read_qps": -(-reads_per_day * peak // day),
"storage_tb": round(total * bytes_per_url / 10 ** 12, 1),
"code_length": length,
}
print(url_shortener_capacity(100_000_000, 100, 500, 10, 3))
# -> {'write_qps': 1158, 'read_qps': 115741, 'peak_read_qps': 347223, 'storage_tb': 182.5, 'code_length': 7}
print(url_shortener_capacity(1_000_000, 10, 500, 5, 2))
# -> {'write_qps': 12, 'read_qps': 116, 'peak_read_qps': 232, 'storage_tb': 0.9, 'code_length': 6}
print(url_shortener_capacity(1, 1, 100, 1, 1))
# -> {'write_qps': 1, 'read_qps': 1, 'peak_read_qps': 1, 'storage_tb': 0.0, 'code_length': 2}Kodda değil de fikirde mi takıldın? URL kısaltıcı tasarla bunu anlatıyor.