Entrevista técnica de código: Implementar un almacén clave-valor con versiones temporales

Planteamiento y alcance

Implementa una estructura en memoria con set(key, value, timestamp) y get(key, timestamp). get devuelve la versión más reciente para esa clave cuya marca de tiempo sea a lo sumo el tiempo de consulta; devuelve un fallo de búsqueda explícito cuando no existe ninguna. Aclara si las marcas de tiempo son monotónicas por clave, si las marcas de tiempo iguales se sobrescriben, si las lecturas y escrituras son concurrentes y si se requiere eliminación o persistencia. El punto central es mantener un invariante de historial por clave, no ordenar y escanear repetidamente cada registro.

Qué evalúa el entrevistador

Una respuesta sólida apunta a una búsqueda de O(log m), donde m es la cantidad de versiones para la clave, y explica el balance de escritura entre un enfoque de solo adición (append-only) y entradas fuera de orden. El entrevistador indagará sobre claves vacías, ambos límites de tiempo, marcas de tiempo duplicadas, valores nulos, claves desconocidas y la diferencia entre la versión efectiva más reciente y una versión posterior al tiempo de consulta. La afirmación de seguridad entre hilos (thread-safety) debe incluir la granularidad de los bloqueos y la semántica de instantáneas (snapshots).

Preguntas de aclaración antes de programar

1. ¿Las marcas de tiempo son monotónicas por clave? Si lo son, añade al final y usa un escaneo inverso corto o búsqueda binaria; si no, preserva el orden o rechaza escrituras desordenadas.
2. ¿Qué significan las marcas de tiempo iguales? Para una política de última escritura gana (last-write-wins), mantén una secuencia monotónicamente creciente como desempate estable; de lo contrario, rechaza los conflictos.
3. ¿Los valores pueden ser nulos? De ser así, un fallo de búsqueda no puede representarse también con null; devuelve un resultado con un indicador explícito found.
4. ¿Se requiere concurrencia? Completa primero el invariante monohilo, luego define la visibilidad y elige bloqueos por clave o instantáneas inmutables.
5. ¿El historial es ilimitado? Una ventana de retención o un límite de versiones cambia la expulsión de datos y el significado de una consulta antigua.

Estructura de respuesta en 30 segundos

“Almaceno un arreglo de versiones ordenado por tiempo para cada clave. get utiliza upper_bound(timestamp) para encontrar la primera versión mayor que la consulta y devuelve la entrada anterior, por lo que la búsqueda es O(log m). Si las escrituras no son monotónicas, uso inserción ordenada y menciono su costo; si el rendimiento de escritura domina, añado a un registro y construyo un índice por lotes. Un número de secuencia hace que las marcas de tiempo iguales sean deterministas, y los fallos de búsqueda tienen un estado explícito. Pruebo claves vacías, límites, escrituras fuera de orden y marcas de tiempo duplicadas.”

Solución paso a paso

Representa cada registro como (timestamp, sequence, value) y mantén el arreglo de cada clave no decreciente por (timestamp, sequence). Para get(k, t), encuentra la primera posición i con timestamp > t. Si i es cero, no hay una versión efectiva; de lo contrario, devuelve records[i - 1]. Esta regla de límite superior incluye una escritura exactamente en t.

Cuando las marcas de tiempo son monotónicas por clave, añadir al final ofrece un costo amortizado de O(1) para set y O(log m) para get. Con marcas de tiempo fuera de orden, ubicar el punto de inserción es logarítmico, pero desplazar un arreglo es O(m) en el peor de los casos. Un árbol balanceado evita los desplazamientos a costa de más asignaciones de memoria y sobrecarga de punteros. Un único arreglo global ordenado es incorrecto porque los límites de consulta son independientes por clave.

Las marcas de tiempo duplicadas necesitan una regla determinista. Para que gane la última escritura, asigna a cada llamada una secuencia creciente y ordena por (timestamp, sequence); el límite superior compara únicamente la marca de tiempo, de modo que el último registro en esa marca de tiempo gana. Si las marcas de tiempo pueden exceder el rango de enteros seguros del lenguaje, usa un tipo entero o comparador adecuado en lugar de convertir silenciosamente a punto flotante.

Para la concurrencia, la extensión más pequeña bloquea una clave mientras reemplaza su arreglo o ejecuta una búsqueda binaria. Para mantener las lecturas sin bloqueos, un escritor puede construir un nuevo arreglo inmutable y reemplazar atómicamente la referencia; los lectores ven la instantánea antigua o la nueva, nunca un arreglo parcial. La persistencia añade un registro (log), suma de verificación (checksum) y un cursor de recuperación, y solo debe discutirse si el entrevistador amplía el alcance.

Ejemplo de respuesta de alta calidad

“Asumiré que las marcas de tiempo pueden llegar desordenadas, que las marcas de tiempo iguales utilizan la regla de que la última escritura gana, y que la primera versión es monohilo. Cada clave se asigna a un arreglo ordenado por (timestamp, sequence). get realiza una búsqueda de límite superior para encontrar la primera marca de tiempo mayor que la consulta y devuelve la versión precedente, lo que brinda una búsqueda O(log m) y un comportamiento de igualdad correcto. Si se garantiza que las marcas de tiempo son crecientes, set se convierte en amortizado O(1). Si las escrituras predominan sobre las lecturas, añadiría a un registro y construiría un índice de forma asíncrona. Las pruebas cubren claves desconocidas, antes de la primera versión, igual a la primera y última versión, después de la última versión, escrituras fuera de orden, marcas de tiempo duplicadas y valores nulos.”

Errores comunes

• Error → escanear linealmente en busca de la última versión; por qué falla → la búsqueda se vuelve O(m) y escala mal; solución → mantener historiales ordenados y usar búsqueda de límite superior.
• Error → usar timestamp < t; por qué falla → se omite una escritura exactamente en t; solución → encontrar el primer timestamp > t.
• Error → asumir que todas las escrituras son crecientes; por qué falla → un evento fuera de orden rompe el invariante del arreglo; solución → declarar la restricción y usar inserción ordenada o un árbol.
• Error → usar null tanto para un fallo de búsqueda como para un valor almacenado; por qué falla → quienes llaman a la función no pueden distinguir los estados; solución → devolver { found, value } o un tipo opcional explícito.
• Error → ignorar marcas de tiempo iguales; por qué falla → los resultados dependen del orden incidental; solución → añadir una secuencia o rechazar el conflicto.

Respuestas a preguntas de seguimiento

¿Cómo optimizarías si se garantiza que las marcas de tiempo son crecientes?

Añadir al final por clave para escrituras con costo amortizado O(1). Mantener la búsqueda binaria para lecturas predecibles de O(log m), o escanear hacia atrás solo cuando los patrones de acceso demuestren que las consultas suelen estar cerca de la versión más reciente. No afirmes que el escaneo hacia atrás toma tiempo constante en el peor de los casos.

¿Cómo retendrías solo los últimos 30 días por clave?

Define si el límite utiliza el tiempo del evento o el tiempo del servicio, luego elimina periódicamente el prefijo antiguo mientras conservas el orden. Una consulta anterior al límite debe devolver “historial no disponible”, no enmascararse como un fallo de búsqueda común.

¿Qué cambia para lectores y escritores concurrentes?

Define primero un punto de linealización. Un diseño directo utiliza un bloqueo de lectura-escritura (read-write lock) por clave. Para lecturas sin bloqueos, construye un nuevo arreglo e intercambia atómicamente su referencia para que los lectores observen una instantánea completa, ya sea la antigua o la nueva.

¿Cómo persistirías y te recuperarías después de una falla?

Añade a un registro secuenciado antes de confirmar una escritura, materializa periódicamente una instantánea del índice y reproduce el sufijo después de la recuperación mientras validas los números de secuencia. No añadas un diseño de base de datos completo cuando el enunciado solo pide memoria.