Capacidade de um encurtador de URL
A missão
Problema
Transforme os números iniciais de uma entrevista sobre um encurtador de URL em uma estimativa de capacidade. Dados os novos links curtos por dia, as leituras por escrita, os bytes armazenados por link, os anos de retenção e um fator de pico sobre a média, retorne um dicionário com: write_qps e read_qps, a média de requisições por segundo, arredondada para cima; peak_read_qps, as leituras por dia vezes o fator de pico, por segundo, arredondado para cima; storage_tb, todos os links mantidos durante o período de retenção, em terabytes de 10¹² bytes, arredondado para 1 casa decimal; e code_length, o menor código sobre 62 caracteres (a-z, A-Z, 0-9) com espaço para todos os links. Use 86.400 segundos por dia e 365 dias por ano, com aritmética inteira para os arredondamentos para cima.
Exemplos
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}
Por quê: 365 bilhões de links precisam de 7 caracteres, porque 62⁶ é só cerca de 57 bilhões
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}
Por quê: um serviço 100 vezes menor ainda precisa de 6 caracteres, já que 62⁵ fica abaixo de 1 bilhão
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}
Por quê: edge case: arredondar para cima mantém toda taxa em pelo menos 1, e 365 links já estouram os 62 códigos de um caractere
Dicas
0 / 3
Tudo começa pelas contagens por dia. As leituras por dia são os novos links por dia vezes a proporção de leitura, e o total de links é novos links por dia × 365 × anos.
A divisão com teto em inteiros é -(-a // b). Aplique o fator de pico antes de dividir, para que o arredondamento aconteça uma única vez.
Para o tamanho do código, comece em 1 e aumente enquanto 62 elevado a esse expoente for menor que o número total de links.
- Tempo-alvo
- O(log(total links))
- Espaço-alvo
- O(1)
Solução
Uma estimativa de capacidade em uma entrevista de design é um punhado de multiplicações, e o valor está em fazê-las em uma ordem fixa que o entrevistador consiga acompanhar: por dia, depois por segundo e, por fim, ao longo do período de retenção. As taxas são arredondadas para cima porque uma frota de servidores dimensionada para 1.157,4 escritas por segundo fica uma escrita aquém, e o fator de pico é aplicado antes da divisão para que só haja um passo de arredondamento. O armazenamento é o total de links vezes o tamanho do registro, informado em terabytes decimais. O tamanho do código sai do mesmo total: cada caractere a mais em base 62 multiplica o espaço por 62, então o loop para no primeiro tamanho que cabe, 7 caracteres para 365 bilhões de links. O loop roda O(log total) vezes e todo o resto é constante, então o tempo e o espaço são O(1) para entradas práticas.
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}Travou na ideia, e não no código? Projetar um encurtador de URL explica isso.