¿Cómo implementar una skip list y explicar su comportamiento esperado O(log N)?

1. Pregunta

Necesitas un diccionario ordenado que admita búsqueda de claves, inserción, eliminación y recorridos por rango. El conjunto de datos crece dinámicamente y el entrevistador desea operaciones con un promedio cercano a O(log N) sin requerir un árbol AVL o rojinegro. Diseña una skip list y analiza la aleatoriedad, los límites y la disposición en memoria.

2. Restricciones y aclaraciones

• Decide si las claves son únicas; si no lo son, define la política de sobrescritura, conteo u ordenamiento estable.
• Elige un nivel máximo y una probabilidad de promoción p; construye índices hacia arriba a partir de una lista enlazada base.
• La búsqueda, inserción y eliminación mantienen un predecesor para cada nivel; la iteración por rango sigue la lista base.
• Discute primero la estructura de un solo hilo. La concurrencia requiere bloqueo adicional, control de versiones o una demostración para un algoritmo libre de bloqueos (lock-free).

3. Idea central

Cada nodo posee un arreglo de tamaño aleatorio con punteros hacia adelante. La búsqueda comienza en la cabeza del nivel más alto: avanza mientras la siguiente clave sea menor que el objetivo; de lo contrario, desciende un nivel. La inserción registra los predecesores, elige una altura aleatoria e inserta el nodo en cada nivel correspondiente. La eliminación utiliza el mismo arreglo de predecesores para desvincularlo. Los niveles superiores dispersos proporcionan O(N) punteros esperados y O(log N) para la búsqueda, inserción y eliminación esperadas.

4. Implementación de referencia

randomLevel(rng, p, maxLevel):
  level = 1
  while level < maxLevel and rng.uniform01() < p:
    level += 1
  return level

findPredecessors(key):
  update = array(maxLevel)
  node = head
  for level from maxLevel - 1 down to 0:
    while node.forward[level] != nil and node.forward[level].key < key:
      node = node.forward[level]
    update[level] = node
  return update

insert(key, value):
  update = findPredecessors(key)
  if update[0].forward[0].key == key:
    update[0].forward[0].value = value
    return
  node = Node(key, value, randomLevel(rng, p, maxLevel))
  for level in 0 .. node.height - 1:
    node.forward[level] = update[level].forward[level]
    update[level].forward[level] = node

Verifica nil antes de leer una clave y asegúrate de que la nueva altura nunca exceda maxLevel. La eliminación reconecta cada nivel que apunta al objetivo con su sucesor. Si el nivel más alto queda vacío, reduce el conteo del nivel activo sin mover nodos.

5. Complejidad y peor caso

Con una probabilidad de promoción fija y una fuente aleatoria independiente, el nivel y la longitud de la ruta son logarítmicos en valor esperado, y el espacio esperado es O(N). Si la aleatoriedad falla o un adversario puede predecir los niveles, la estructura puede degenerar en una lista enlazada y las operaciones pasan a ser O(N). Utiliza una fuente aleatoria de alta calidad, limita la altura máxima, reconstruye periódicamente o elige un árbol balanceado determinista para cargas de trabajo adversarias.

6. Verificación y compensaciones de concurrencia

• Prueba claves ordenadas, duplicadas, vacías y extremas para búsqueda, actualización, eliminación e iteración por rango.
• Mide la distribución de alturas, la longitud promedio de la ruta y el recuento de punteros a lo largo de varios valores de N.
• Reproduce secuencias de operaciones aleatorias contra un mapa ordenado de referencia y compara contenidos y orden.
• Para la concurrencia, explica la granularidad del bloqueo, la eliminación lógica, la recuperación de memoria y el riesgo de ABA; envolver las escrituras de punteros en un único bloqueo no constituye un diseño lock-free.

7. Errores comunes

• Implementar la búsqueda sin arreglos de predecesores, obligando a que la inserción o eliminación vuelva a escanear la lista.
• Ignorar la política de claves duplicadas y producir un orden de rango inestable.
• Tratar el O(log N) esperado como una garantía del peor caso sin discutir la aleatoriedad ni las entradas adversarias.
• Usar un arreglo de altura fija que desperdicie memoria o permitir alturas sin límite que desborden el arreglo.

8. Puntos de evaluación en entrevistas

Busca desde los niveles altos hacia abajo

El candidato explica la condición de avance en cada nivel, cuándo descender y por qué la lista base contiene todos los elementos.

Mantiene los predecesores correctamente

El candidato almacena un arreglo de actualización (update array) para cada nivel y maneja la sobrescritura, punteros nil y la reducción del nivel activo más alto.

Explica la complejidad probabilística

El candidato indica el tiempo esperado O(log N), el espacio esperado O(N) y las condiciones que causan la degeneración a O(N).

Identifica los límites de concurrencia

El candidato discute bloqueos, versiones, eliminación lógica, recuperación de memoria y ABA en lugar de tratar el código de un solo hilo como si fuera concurrente.