Entrevista de código: ¿Cómo implementar un arreglo dinámico y demostrar que append es O(1) amortizado?

Problema y escenarios de aplicación

Utilizando un arreglo fijo, implementa un arreglo dinámico con get(index), set(index, value) y append(value). Redimensiona cuando esté lleno, explica la política de crecimiento, el comportamiento en los límites, el tiempo de append en el peor caso y amortizado, y compara el crecimiento lineal con el geométrico.

Asume referencias o valores de tamaño fijo, índices basados en cero, excepciones para accesos fuera de rango y append en un arreglo vacío. Un banco público de entrevistas vincula la implementación de arreglos dinámicos/vectores con Microsoft, la gestión de memoria y el análisis amortizado; MIT 6.006 clasifica el append en arreglos dinámicos como Θ(1) amortizado.

Qué evalúa el entrevistador

Si separas size de capacity y mantienes el invariante de que los elementos válidos ocupan las primeras size posiciones.
Si eliges un crecimiento geométrico en lugar de agregar una posición a la vez.
Si puedes demostrar el límite amortizado mediante análisis agregado, contable o de potencial en lugar de limitarte a afirmar O(1).
Si cubres capacidad cero, desbordamiento de enteros, fallos de asignación, reducción de tamaño e inserción intermedia.

Preguntas para clarificar antes de responder

¿Se requiere únicamente append al final o también inserción intermedia, eliminación y pop? Esto cambia el análisis de complejidad.
¿Los valores son de tamaño fijo? ¿Se requieren semántica de referencias, invalidación de iteradores o seguridad entre hilos?
¿El objetivo es menos copias, menor sobrecarga de memoria o un límite estricto de latencia?
¿Se requiere reducción de tamaño? De ser así, ¿debería su umbral ser independiente del umbral de crecimiento para evitar oscilaciones (thrashing)?

Marco de respuesta de 30 segundos

Almacenaría un arreglo de respaldo, size y capacity. Append escribe directamente cuando hay una posición libre. Cuando está lleno, asigna un arreglo más grande, copia los primeros size elementos y escribe el nuevo valor. El crecimiento geométrico, como duplicar el tamaño, es la clave: el número total de elementos copiados a lo largo de n operaciones de append es una serie geométrica inferior a 2n, por lo que el trabajo total es O(n) y append es O(1) amortizado. La llamada de redimensionamiento en sí sigue siendo O(n), por lo que no es una garantía de O(1) en el peor caso por llamada.

Análisis detallado paso a paso

Estado e invariante

Mantén tres campos: el arreglo de respaldo data, la cantidad de elementos válidos size y las posiciones asignadas capacity. Mantén siempre el tamaño en al menos cero y no mayor que la capacidad; los elementos válidos ocupan [0, size). Append escribe en data[size] e incrementa el tamaño. get y set aceptan únicamente [0, size), nunca una posición de capacidad no inicializada.

Política de crecimiento geométrico

Cuando size == capacity, asigna al menos max(1, capacity * 2), copia los elementos anteriores y reemplaza la referencia de respaldo. La capacidad cero necesita un caso especial, o de lo contrario la multiplicación seguirá dando cero. Duplicar genera una racha de appends económicos comparable al tamaño actual; un factor mayor copia con menor frecuencia pero deja más espacio sin usar.

~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;

public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }

public int size() { return size; }

public Object get(int index) { check(index); return data[index]; }

public void set(int index, Object value) { check(index); data[index] = value; }

private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~

Object[] es una forma habitual de ilustrar la implementación bajo el borrado de tipos genéricos; el código de producción aún necesita una política explícita para valores nulos, fallos de asignación y concurrencia. El invariante y la complejidad no dependen de Java.

La demostración amortizada

Asume que la capacidad comienza en 1 y se duplica. A lo largo de n operaciones de append, las escrituras ordinarias cuestan n constantes; las copias de redimensionamiento ocurren en las capacidades 1, 2, 4, 8, y así sucesivamente, para un total inferior a 2n. Por lo tanto, el trabajo total es inferior a 3n más la inicialización, lo que resulta en un costo amortizado de O(1) por operación.

Esta es una garantía sobre una secuencia del peor caso, no un promedio sobre entradas aleatorias. El append que dispara un redimensionamiento todavía copia Θ(n) elementos, por lo que una llamada tiene un tiempo de O(n) en el peor caso. get y set son O(1) en el peor caso, y el almacenamiento de respaldo es O(n).

Crecimiento lineal y reducción de tamaño

Agregar únicamente c posiciones a la vez hace que los costos de copia sean aproximadamente c + 2c + ...; insertar n elementos cuesta Θ(n²), por lo que append se degrada a Θ(n) amortizado. El crecimiento geométrico suele ser la mejor compensación, aunque un factor mayor incrementa el espacio pico sin utilizar.

Si se admite pop, reduce el tamaño por debajo de un nivel mínimo de uso. Mantén separados los umbrales de crecimiento y reducción —por ejemplo, duplicar cuando esté lleno y reducir a la mitad por debajo de un cuarto— para evitar reubicaciones repetidas cuando append y pop se alternan. La reducción de tamaño preserva las operaciones al final en O(1) amortizado, pero agrega pausas por liberación y copia.

Casos límite evaluables

Prueba el primer append en un arreglo vacío, append con la capacidad exacta, crecimiento repetido, referencias duplicadas, índices negativos, index == size, capacidades enormes, desbordamiento y fallos de asignación. Un contador de copias controlado puede verificar que n operaciones de append realicen Θ(n) copias totales; comprobar únicamente el contenido final permitiría que una implementación cuadrática con crecimiento lineal pasara la prueba.

Ejemplo de respuesta de alta calidad

Separaría el arreglo de respaldo, size y capacity, manteniendo siempre los elementos válidos en las primeras size posiciones. Append escribe en la capacidad libre; cuando está lleno, asigna el doble de la capacidad, copia los elementos anteriores y luego escribe el valor. Una capacidad inicial de cero recibe un caso especial de una posición.

La demostración de duplicación es la parte importante: a lo largo de n operaciones de append, las copias por redimensionamiento se mantienen por debajo de 2n; sumar n escrituras constantes resulta en O(n) de trabajo total y O(1) amortizado para append. La llamada de redimensionamiento en sí sigue siendo O(n), por lo que el costo amortizado no es un límite estricto de latencia por llamada. El crecimiento lineal cuesta Θ(n²) en copias totales. Si se requiere reducción de tamaño, usaría histéresis y probaría entradas vacías, límites, desbordamiento y fallos de asignación.

Errores comunes

Agregar una posición cada vez que se llena → la copia total se vuelve cuadrática → usa crecimiento geométrico y muestra la serie.
Decir que append es O(1) en el peor caso → ignorar la copia por redimensionamiento → distinguir entre O(n) para una llamada individual y O(1) amortizado para la secuencia.
Validar get contra la capacidad → devolver una posición no inicializada → requerir que el índice sea al menos cero y menor que el tamaño.
Duplicar una capacidad de cero → el arreglo nunca crece → usa una capacidad mínima de uno.
Reducir el tamaño de inmediato con bajo uso → alternar append/pop provoca movimientos repetidos → separa los umbrales de crecimiento y reducción.

Preguntas de seguimiento y respuestas

¿Qué sucede si cada append debe tener un tiempo O(1) en el peor caso?

El redimensionamiento de un arreglo contiguo realiza una migración O(n), por lo que no puede prometer ese límite estricto tal como está planteado. Un arreglo segmentado, una migración incremental o la preasignación con un límite superior conocido pueden cambiar la compensación, a costa de la localidad, constantes de indexación o espacio. Primero confirma si el requisito es verdaderamente para el peor caso.

¿Qué cambia si el factor de crecimiento es 1.25 en lugar de 2?

Cualquier factor estrictamente mayor que 1 sigue proporcionando O(1) amortizado para append al final, pero las copias ocurren con mayor frecuencia y el espacio libre es menor. A medida que el factor se acerca a 1, las constantes aumentan; elige en función del presupuesto de memoria, el comportamiento del asignador y los objetivos de latencia, no solo de Big-O.

¿Cómo demuestras que el crecimiento lineal es O(n²)?

Si cada redimensionamiento agrega c posiciones, el j-ésimo redimensionamiento copia aproximadamente jc elementos. Los primeros n elementos disparan alrededor de n/c redimensionamientos, por lo que el total es c + 2c + ... + (n/c)c = Θ(n²). Por lo tanto, append amortizado es Θ(n).

¿Cómo cambia la complejidad la inserción intermedia?

Incluso con capacidad libre, la inserción intermedia desplaza un sufijo y es O(n) en el peor caso. La copia por redimensionamiento es trabajo adicional; los arreglos dinámicos están optimizados para acceso aleatorio y operaciones al final, no para todo tipo de inserción.

¿Cómo funcionaría un append concurrente?

Usa un bloqueo (lock), pertenencia a un único hilo o un protocolo de índice atómico con redimensionamiento coordinado. Hacer que solo size sea atómico no protege toda la secuencia de verificar capacidad, asignar, copiar y publicar. Si no se requiere concurrencia, define explícitamente el límite de un solo hilo.