Capacidad de un acortador de URL
La misión
Problema
Convierte los números iniciales de una entrevista sobre un acortador de URL en una estimación de capacidad. Dados los enlaces cortos nuevos por día, las lecturas por escritura, los bytes guardados por enlace, los años de retención y un factor de pico sobre el promedio, devuelve un dict con: write_qps y read_qps, las solicitudes promedio por segundo, redondeadas hacia arriba; peak_read_qps, las lecturas por día multiplicadas por el factor de pico, por segundo, redondeadas hacia arriba; storage_tb, todos los enlaces guardados durante el período de retención en terabytes de 10¹² bytes, redondeado a 1 decimal; y code_length, el código más corto sobre 62 caracteres (a-z, A-Z, 0-9) con espacio para cada enlace. Usa 86 400 segundos por día y 365 días por año, con aritmética entera para el redondeo hacia arriba.
Ejemplos
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 mil millones de enlaces necesitan 7 caracteres, porque 62⁶ es solo unos 57 mil millones
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é: un servicio 100 veces más pequeño igual necesita 6 caracteres, ya que 62⁵ es menos de mil millones
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é: caso límite: redondear hacia arriba deja cada tasa en al menos 1, y 365 enlaces ya superan los 62 códigos de un solo carácter
Pistas
0 / 3
Todo parte de los conteos por día. Las lecturas por día son los enlaces nuevos por día multiplicados por la proporción de lecturas, y el total de enlaces es enlaces nuevos por día × 365 × años.
La división con redondeo hacia arriba en enteros es -(-a // b). Aplica el factor de pico antes de dividir, para que el redondeo ocurra una sola vez.
Para la longitud del código, empieza en 1 y auméntala mientras 62 elevado a esa potencia sea menor que el total de enlaces.
- Tiempo objetivo
- O(log(total links))
- Espacio objetivo
- O(1)
Solución
En una entrevista de diseño, una estimación de capacidad es un puñado de multiplicaciones, y el valor está en hacerlas en un orden fijo que el entrevistador pueda seguir: por día, luego por segundo y luego a lo largo del período de retención. Las tasas se redondean hacia arriba porque una flota de servidores dimensionada para 1157.4 escrituras por segundo se queda corta por una escritura, y el factor de pico se aplica antes de dividir para que haya un solo paso de redondeo. El almacenamiento es el total de enlaces por el tamaño de cada registro, expresado en terabytes decimales. La longitud del código sale del mismo total: cada carácter extra en base 62 multiplica el espacio por 62, así que el bucle se detiene en la primera longitud que alcanza, 7 caracteres para 365 mil millones de enlaces. El bucle corre O(log total) veces y todo lo demás es constante, así que el tiempo y el espacio son O(1) para entradas prácticas.
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}¿Lo que te frena es la idea y no el código? Diseña un acortador de URL lo explica.