Entrevista técnica: Implementar un Snapshot Array

Problema y contexto aplicable

Implementa un arreglo de longitud fija que comience con cero en cada índice y admita tres operaciones:

• set(index, value) cambia un elemento en la versión actual, que aún no ha sido guardada en un snapshot.
• snap() guarda la versión actual y devuelve su ID. Los ID comienzan en 0 y aumentan de uno en uno.
• get(index, snapId) devuelve el valor en index cuando se tomó el snapshot snapId.

Asume que 1 <= length <= 50,000, 0 <= value <= 10^9, los índices y los ID de snapshots son válidos, y que se realizan a lo sumo 50,000 llamadas en total entre todas las operaciones. Una solución debe explicar tanto el comportamiento de la API como la razón por la cual el estado almacenado es suficiente para responder a cualquier consulta histórica.

Esta es una pregunta de programación y estructuras de datos. El planteamiento público aparece en las colecciones actuales de práctica para entrevistas, y la señal útil evaluada es si el candidato puede reemplazar snapshots completos por registros inmutables de cambios y luego encontrar el registro histórico correcto mediante una consulta de predecesor.

Lo que evalúa el entrevistador

La primera señal es el modelado de costos. Copiar todos los length valores en cada snap es fácil de razonar, pero cuesta O(length) en tiempo y espacio por snapshot, incluso si solo cambió un índice. Con 50,000 elementos y 50,000 operaciones, esa dirección de peor caso resulta innecesariamente costosa.

La segunda señal es elegir un índice que coincida con la consulta. get siempre proporciona un índice de arreglo, por lo que conviene almacenar un historial ordenado de cambios por índice. Una entrada de historial [s, v] significa que el valor v entró en vigencia a partir del ID de snapshot s. La respuesta es la entrada con el mayor s <= snapId, lo cual constituye una búsqueda estándar de predecesor.

La tercera señal es la semántica de los snapshots. Varias llamadas a set en el mismo índice antes del siguiente snap pertenecen a una sola versión; solo el último valor debe permanecer. Agregar entradas duplicadas con el mismo ID de snapshot desperdicia espacio y puede dificultar la formulación del invariante del historial. Combinarlas (coalescing) mantiene los ID estrictamente crecientes.

Por último, una respuesta sólida establece un invariante, demuestra la búsqueda binaria y prueba los casos límite temporales: el cero inicial, múltiples escrituras antes de un snapshot, escrituras después de un snapshot, índices sin modificar y consultas entre cambios dispersos.

Preguntas de aclaración antes de responder

• ¿snap() devuelve el ID antes o después de incrementarlo? Devuelve el ID actual y luego avanza a la siguiente versión de trabajo.
• ¿Se puede llamar a set varias veces antes de snap? Sí. La última escritura en un índice dentro de esa versión prevalece.
• ¿Puede get leer el estado actual sin snapshot? No. Recibe un ID válido devuelto por un snap() anterior.
• ¿La longitud y el rango de índices son fijos? Sí. No hay inserciones, eliminaciones ni cambios de tamaño.
• ¿Se pueden omitir ID de snapshots? Un índice puede no tener cambios en muchos snapshots consecutivos, aunque los ID globales se mantengan consecutivos.
• ¿Se requiere seguridad en subprocesos (thread safety)? No para este contrato en memoria de entrevista. La mutación concurrente requeriría sincronización externa alrededor de set y snap.
• ¿Qué debe devolver un índice sin modificar? Cero para todos los snapshots.
• ¿Se requiere persistencia entre reinicios del proceso? No. Eso agregaría requisitos de serialización y durabilidad ajenos a este problema de estructuras de datos.

Estructura de respuesta en 30 segundos

“Mantendría un historial ordenado para cada índice del arreglo en lugar de copiar todo el arreglo. Inicializaría cada historial con [0, 0]. El ID de snapshot actual comienza en cero. En set, sobrescribo la última entrada si ya pertenece al ID actual; de lo contrario, agrego [currentId, value]. En snap, devuelvo currentId y lo incremento. En get, realizo una búsqueda binaria en el historial de ese índice para encontrar la primera entrada cuyo ID sea mayor que snapId, y luego devuelvo el valor precedente. Los historiales tienen ID estrictamente crecientes, y el centinela garantiza que exista un predecesor. La construcción es O(length), set y snap son O(1) amortizado, get es O(log h), y el espacio es O(length + u) para u cambios retenidos.”

Análisis detallado paso a paso

Paso 1: Descartar las copias completas tras cuantificarlas.

Una implementación directa mantiene un arreglo mutable y lo copia entero en una lista en cada snap. Proporciona O(1) para set y get, pero snap cuesta O(length) y cada snapshot almacena length valores. Esto incurre en costos por índices que no cambiaron.

Un único registro global de eventos evita copias, pero get(index, snapId) podría tener que escanear hacia atrás a través de actualizaciones de índices no relacionados. Como la consulta ya especifica un índice, particionar el historial por índice elimina eventos irrelevantes.

Paso 2: Definir qué significa una entrada de historial.

Para un índice determinado, supongamos que su historial retenido es:

[[0, 0], [2, 7], [5, 4]]

El valor es 0 para los snapshots 0 y 1, 7 para los snapshots 2 a 4, y 4 a partir del snapshot 5 en adelante. Cada entrada representa un punto de cambio, no una copia para un snapshot individual. Por lo tanto, el registro deseado para el snapshot t es el registro situado más a la derecha cuyo ID sea a lo sumo t.

Inicializa cada índice con [0, 0]. Este centinela expresa el valor inicial y garantiza que toda consulta de snapshot válida tenga un predecesor, por lo que get no necesita una rama especial para historial vacío.

Paso 3: Combinar escrituras dentro de la versión actual.

Antes del primer snap, el ID actual es 0. Si a set(3, 5) le sigue set(3, 8), el snapshot 0 debe contener 8. La segunda llamada sobrescribe [0, 5] con [0, 8]. Después de que snap() avance el ID actual, la siguiente escritura agregará un nuevo registro.

Esto mantiene el invariante de que los ID de snapshots en cada historial son estrictamente crecientes y cada historial contiene a lo sumo un registro por cada ID. La cantidad de cambios retenidos no es mayor que la cantidad de llamadas a set.

Paso 4: Implementar la búsqueda de predecesor mediante límite superior (upper bound).

type Version = [snapId: number, value: number];

class SnapshotArray {
  private readonly histories: Version[][];
  private currentSnapId = 0;

  constructor(length: number) {
    this.histories = Array.from({ length }, () => [[0, 0]]);
  }

  set(index: number, value: number): void {
    const history = this.histories[index];
    const latest = history[history.length - 1];

    if (latest[0] === this.currentSnapId) {
      latest[1] = value;
    } else {
      history.push([this.currentSnapId, value]);
    }
  }

  snap(): number {
    return this.currentSnapId++;
  }

  get(index: number, snapId: number): number {
    const history = this.histories[index];
    let left = 0;
    let right = history.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);
      if (history[middle][0] <= snapId) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return history[left - 1][1];
  }
}

La búsqueda utiliza el intervalo semiabierto [left, right). Al terminar, left es la primera posición con un ID mayor que snapId. Su predecesor es la entrada situada más a la derecha con un ID a lo sumo snapId. Esta es la misma partición de límite superior documentada en las bibliotecas estándar de bisección.

Paso 5: Demostrar la corrección a partir del invariante.

Para cada índice, los registros tienen ID estrictamente crecientes. Un registro [s, v] se crea o se finaliza antes de tomar el snapshot s y permanece como el valor efectivo hasta el siguiente registro de ese índice. Por lo tanto, entre los registros cuyos ID no superan un snapshot solicitado, el que tiene el mayor ID es exactamente la última escritura visible para ese snapshot.

La búsqueda binaria devuelve el primer registro después de ese prefijo admisible, por lo que left - 1 selecciona su mayor ID. El centinela [0, 0] hace que el prefijo admisible no sea vacío para cualquier ID de snapshot válido. Por consiguiente, get devuelve el valor requerido.

Paso 6: Analizar la complejidad y verificar los límites.

Crear los historiales cuesta O(length) en tiempo y espacio. set lee o agrega al final de un historial en tiempo amortizado O(1). snap es O(1). Si un índice tiene h registros retenidos, get cuesta O(log h). En todo el objeto, el espacio es O(length + u), donde u es la cantidad de registros de cambio retenidos que no son centinelas y u es a lo sumo el número de llamadas a set.

Como mínimo, prueba:

Una prueba diferencial aleatoria puede comparar esta estructura contra la solución base de copias completas. La solución base es demasiado costosa para restricciones de producción, pero constituye un oráculo de prueba simple y confiable.

Respuesta de muestra de alta calidad

“La consulta fundamental es la búsqueda histórica para un índice conocido, por lo que mantendría un historial de cambios ordenado por índice. Cada historial comienza con [0, 0]; un par [s, v] indica que v está vigente desde el snapshot s hasta el siguiente par.

El ID actual comienza en cero. set solo examina el último par. Si ese par ya usa el ID actual, reemplaza el valor porque prevalece la última escritura previa a un snapshot. De lo contrario, agrega un nuevo par. snap devuelve el ID actual y lo incrementa.

Para get(index, snapId), ejecuto una búsqueda de límite superior en el historial de ese índice: encuentro el primer par con ID mayor que el ID solicitado y devuelvo el valor del par anterior. Los ID por índice son estrictamente crecientes, y el centinela inicial garantiza que el predecesor exista. Este predecesor es precisamente el último valor escrito a más tardar en el snapshot solicitado.

La construcción cuesta O(length). set y snap son O(1) amortizado, get es O(log h) para los h registros de cambio de ese índice, y el espacio total es O(length + u). Probaría ceros iniciales, asignaciones repetidas antes de un snapshot, cambios dispersos a lo largo de varios snapshots, lecturas pasadas tras escrituras posteriores, índices sin tocar y trazas aleatorias contra un oráculo de copias completas.”

Errores comunes

• Copiar todo el arreglo en cada snapshot → el tiempo y el espacio escalan con todos los índices, incluidos los no modificados → almacenar solo los puntos de cambio por índice.
• Mantener un solo registro global de actualizaciones → una lectura puede escanear índices no relacionados → particionar los historiales por el índice proporcionado en cada consulta.
• Agregar en cada set → escrituras repetidas en una misma versión generan ID duplicados y registros desperdiciados → sobrescribir el final cuando tenga el ID actual.
• Buscar un ID de snapshot exacto → un índice puede no haber cambiado en ese snapshot → encontrar el mayor ID registrado menor o igual al solicitado.
• Usar lower bound y devolverlo directamente → puede apuntar a un cambio posterior → obtener el límite superior (upper bound) de la solicitud y devolver el predecesor.
• Iniciar los historiales vacíos → los índices sin modificar requieren casos especiales → inicializar cada historial con [0, 0].
• Incrementar antes de retornar en snap → el primer ID devuelto se convierte en 1 y los registros cambian de versión → devolver el ID actual y luego incrementar.
• Afirmar que get es O(log length) → busca en los registros de cambio de un solo índice → indicar O(log h) y definir h.
• Probar únicamente el ejemplo publicado → las sobrescrituras en la misma versión y los historiales dispersos quedan sin verificar → agregar casos límite y un oráculo diferencial.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Puede snap() ser O(1) si un snapshot debe ser inmutable?

Sí. La inmutabilidad es lógica: una vez devuelto un ID, las escrituras futuras se agregan bajo un ID mayor y nunca mutan registros pertenecientes a ID anteriores. snap() solo avanza el límite de la versión; no necesita materializar una copia completa.

Pregunta de seguimiento 2: ¿Por qué usar un historial por índice en lugar de un mapa por snapshot?

Un mapa por snapshot obliga a que una búsqueda puntual busque hacia atrás a través de los snapshots hasta encontrar ese índice. Los historiales por índice organizan los registros por la primera clave de consulta, de modo que get busca únicamente cambios relevantes. Un mapa orientado a snapshots puede ser útil cuando la consulta principal sea “enumerar todo lo modificado en el snapshot s”, lo cual constituye un contrato diferente.

Pregunta de seguimiento 3: ¿Podría get utilizar una búsqueda binaria de la biblioteca estándar?

Sí, siempre que el lenguaje exponga el contrato exacto de límite superior (upper bound) para una clave. Por ejemplo, una posición de bisección derecha es el punto de inserción posterior a los ID existentes iguales a snapId; restar uno produce el predecesor. Confirma la extracción de claves y el comportamiento de concurrencia en la documentación de la biblioteca en lugar de asumir que todas las funciones auxiliares de búsqueda binaria devuelven el mismo límite.

Pregunta de seguimiento 4: ¿Qué cambia si se pueden eliminar snapshots?

Primero define si eliminar un ID hace que los snapshots posteriores queden inaccesibles o si los ID permanecen estables. Los ID estables generalmente requieren conteo de referencias o compactación que preserve cada valor aún alcanzable por un snapshot retenido. Eliminar un registro a ciegas puede alterar el valor heredado por snapshots posteriores.

Pregunta de seguimiento 5: ¿Cómo harías persistente la estructura?

Almacena registros de cambio append-only indexados por (array_id, index, snap_id) y publica un límite de snapshot duradero solo después de que se confirmen todas las escrituras precedentes. Las lecturas necesitan un índice de predecesores sobre (array_id, index, snap_id). La recuperación, las transacciones y la compactación pasan a ser preocupaciones del sistema de almacenamiento que van más allá de la implementación en memoria para la entrevista.

Pregunta de seguimiento 6: ¿Qué pasa si las lecturas superan ampliamente a las escrituras en un arreglo pequeño y fijo?

Las copias completas pueden volverse razonables si el arreglo es pequeño y las lecturas O(1) importan más que el costo de los snapshots. Compara la longitud real, la cantidad de snapshots, la tasa de lectura y el presupuesto de memoria. El diseño basado en historial de cambios optimiza las escrituras dispersas y la creación de snapshots; no es automáticamente el mejor para todas las cargas de trabajo.