Entrevista de codificación: ¿Cómo implementar una Skip List con búsqueda, inserción y eliminación?

Planteamiento y alcance

Implementa un conjunto ordenado de claves enteras con search, insert y delete. La estructura debe utilizar operaciones con un tiempo esperado de O(log n) y evitar las rotaciones requeridas por un árbol balanceado. Especifica si los duplicados se rechazan o se cuentan; este artículo opta por un conjunto, por lo que insertar una clave existente no realiza ninguna operación.

Esta pregunta aparece en reportes de entrevistas públicas y discusiones de implementación, incluidos un ejercicio de entrevista de Google y una publicación sobre entrevistas de LeetCode. La señal de codificación evaluada es el mantenimiento de múltiples niveles de punteros hacia adelante y la demostración de sus invariantes, no la memorización de una clase de biblioteca.

Qué evalúa el entrevistador

• Si mantienes el nivel cero como la lista ordenada completa y cada nivel superior como una subsecuencia de este.
• Si la inserción y la eliminación actualizan cada nivel de predecesores sin perder el enlace con la lista base.
• Si distingues un O(log n) esperado de una operación O(n) desafortunada y si pruebas los límites de niveles aleatorios.

Redis utiliza una representación de skip list para una codificación de conjuntos ordenados, mientras que las notas de algoritmos de MIT describen su análisis probabilístico. Estas son evidencias teóricas y de implementación; no implican que cada carga de trabajo deba reemplazar un árbol por una skip list.

Aclaraciones previas a la respuesta

1. ¿Conjunto o multiconjunto? Un conjunto rechaza claves duplicadas; un multiconjunto necesita un contador o una identidad de nodo única.
2. ¿Los llamadores necesitan consultas de rango o rango numérico (rank)? El rank requiere metadatos de tramo o ancho (span); la pregunta base solo requiere verificar pertenencia.
3. ¿Se requiere reproducción determinista? Inyecta una fuente aleatoria con semilla para las pruebas, mientras que en producción se utiliza un generador imparcial.
4. ¿Cuál es el límite de memoria? Cada nodo tiene una cantidad variable de punteros hacia adelante, por lo que el límite de niveles y la probabilidad afectan la memoria.

Una respuesta de 30 segundos

“Mantengo un centinela con un puntero hacia adelante para cada nivel y una lista ordenada en el nivel cero. La búsqueda comienza en el nivel más alto y avanza mientras la siguiente clave sea menor; registra el último predecesor en cada nivel. La inserción elige una altura aleatoria, empalma el nuevo nodo después de esos predecesores y no hace nada ante una clave existente. La eliminación usa el mismo arreglo de predecesores y desvincula el objetivo en cada nivel donde aparece, reduciendo luego la altura activa cuando las listas superiores quedan vacías. Con una probabilidad de altura geométrica, la búsqueda, la inserción y la eliminación toman un tiempo esperado de O(log n) y el espacio es esperado de O(n); una secuencia aleatoria patológica aún puede tomar O(n).”

Respuesta detallada paso a paso

Paso 1: Definir el invariante.

El nivel cero contiene todas las claves en orden estrictamente creciente. El nivel i + 1 es una subsecuencia del nivel i, y los punteros hacia adelante de cada nodo están ordenados por clave. Un centinela tiene punteros MAX_LEVEL y ninguna clave de usuario. El nivel activo es la lista no vacía más alta.

Paso 2: Buscar recolectando predecesores.

Comienza en el nivel activo más alto del centinela. Avanza mientras el siguiente nodo exista y su clave sea menor que el objetivo. Baja un nivel y continúa. Guarda el último nodo visitado en update[i]; tras el nivel cero, update[0].next[0] es el objetivo o su posición de inserción.

Paso 3: Insertar con una altura aleatoria.

Obtén una altura geométrica, por ejemplo promocionando repetidamente con probabilidad p = 1/2, limitada a MAX_LEVEL. Si el candidato en el nivel cero tiene la clave, retorna false. Para cada nivel por debajo de la nueva altura, apunta el nuevo nodo al siguiente del predecesor y luego apunta el predecesor al nuevo nodo. Extiende el nivel activo si es necesario.

type Node = { key: number; next: Array<Node | null> };

class SkipSet {
  private readonly maxLevel = 16;
  private readonly head: Node = { key: Number.NEGATIVE_INFINITY, next: [] };
  private level = 1;

  constructor() {
    this.head.next = Array(this.maxLevel).fill(null);
  }

  private randomLevel(): number {
    let h = 1;
    while (h < this.maxLevel && Math.random() < 0.5) h += 1;
    return h;
  }

  search(key: number): boolean {
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
    }
    return node.next[0]?.key === key;
  }

  insert(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    if (update[0].next[0]?.key === key) return false;
    const height = this.randomLevel();
    if (height > this.level) {
      for (let i = this.level; i < height; i += 1) update[i] = this.head;
      this.level = height;
    }
    const fresh: Node = { key, next: Array(height).fill(null) };
    for (let i = 0; i < height; i += 1) {
      fresh.next[i] = update[i].next[i];
      update[i].next[i] = fresh;
    }
    return true;
  }

  delete(key: number): boolean {
    const update = Array<Node>(this.maxLevel);
    let node = this.head;
    for (let i = this.level - 1; i >= 0; i -= 1) {
      while (node.next[i] && node.next[i]!.key < key) node = node.next[i]!;
      update[i] = node;
    }
    const target = update[0].next[0];
    if (!target || target.key !== key) return false;
    for (let i = 0; i < this.level; i += 1) {
      if (update[i].next[i] !== target) break;
      update[i].next[i] = target.next[i] ?? null;
    }
    while (this.level > 1 && !this.head.next[this.level - 1]) this.level -= 1;
    return true;
  }
}

Paso 4: Eliminar cada ocurrencia del nodo objetivo.

El arreglo de predecesores identifica al predecesor del objetivo en cada nivel. Desvincula solo los niveles donde update[i].next[i] sea ese objetivo; los niveles superiores podrían no contenerlo. Luego, reduce el nivel activo mientras el puntero superior del centinela esté vacío.

Paso 5: Analizar complejidad y memoria.

Con una probabilidad de promoción p estrictamente entre cero y uno, la altura esperada es constante y la longitud esperada de la ruta de búsqueda es logarítmica. La búsqueda, la inserción y la eliminación toman un tiempo esperado de O(log n); una mala secuencia aleatoria tiene un peor caso de O(n). La cantidad esperada de punteros es n/(1-p) salvo constantes, por lo que p = 1/2 intercambia aproximadamente dos punteros por nodo por rutas más cortas.

Paso 6: Probar estructura, aleatoriedad y límites.

Usa un generador con semilla en las pruebas. Verifica búsqueda/eliminación en lista vacía, primera y última clave, duplicados, eliminar el único nodo, eliminar a través de niveles, valores negativos y ciclos repetidos de inserción/eliminación. Tras cada operación, recorre el nivel cero y compáralo con un Set de referencia; verifica que cada nivel superior esté ordenado y que cada nodo también aparezca en el nivel cero. Ejecuta muchas semillas para detectar corrupción de altura y punteros.

Respuesta de muestra de alta calidad

“Modelizo un conjunto con un centinela y una cadena ordenada en el nivel cero. Cada nivel superior es una subsecuencia del nivel cero. La búsqueda desciende desde el nivel activo más alto y registra el predecesor en cada nivel. La inserción rechaza una clave existente, elige una altura geométrica aleatoria y empalma el nodo después de esos predecesores. La eliminación busca el mismo arreglo de predecesores, desvincula el objetivo de cada nivel donde aparece y recorta los niveles superiores vacíos.

Las operaciones toman un tiempo esperado de O(log n) con un espacio esperado de O(n), pero un tiempo de peor caso de O(n) sigue siendo posible si las alturas aleatorias son desfavorables. Utilizaría una fuente aleatoria con semilla para pruebas deterministas, compararía el nivel cero con un conjunto de referencia tras cada operación y verificaría los invariantes de orden y subsecuencia para todos los niveles superiores.”

Errores comunes

• Actualizar solo el nivel cero → la búsqueda en niveles superiores puede saltarse o retener la clave → empalma o desvincula cada nivel que contenga el nodo.
• Tratar la altura aleatoria como una garantía → una secuencia patológica puede producir una ruta lineal → declara los límites esperados y de peor caso.
• Permitir nodos duplicados involuntariamente → la semántica de búsqueda y eliminación se vuelve ambigua → elige el comportamiento de conjunto o multiconjunto antes de codificar.
• No recortar los niveles superiores vacíos → las búsquedas inspeccionan niveles obsoletos y el control interno se desajusta → reduce el nivel activo tras la eliminación.
• Probar únicamente la pertenencia final → un puntero superior corrupto puede permanecer oculto → verifica los invariantes de orden y subsecuencia tras cada operación.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Cómo admitirías claves duplicadas?

Elige un contrato. Un multiconjunto puede almacenar un contador en cada nodo de clave, haciendo que las inserciones y eliminaciones repetidas actualicen el contador, o almacenar un número de secuencia único en la clave de comparación. Contar nodos es preferible cuando la memoria lo permite; las identidades únicas son útiles para eliminar una ocurrencia específica.

Pregunta de seguimiento 2: ¿Cómo agregas consultas de rango (rank)?

Almacena un tramo o ancho (span) junto a cada puntero hacia adelante. Durante la búsqueda, acumula los anchos a medida que avanzas a la derecha; la inserción y la eliminación actualizan los anchos afectados en cada nivel. La implementación simple de conjunto no tiene suficientes metadatos para responder consultas de rango en tiempo logarítmico.

Pregunta de seguimiento 3: ¿Cuándo elegirías un árbol balanceado en su lugar?

Usa un árbol balanceado cuando los límites del peor caso, la forma determinista de iteración o un conjunto rico de operaciones ordenadas importen más que la simplicidad de implementación. Una skip list encaja cuando el rendimiento logarítmico esperado, las variantes concurrentes sencillas o un índice ordenado basado en punteros son aceptables. Mide la sobrecarga de memoria y la carga de trabajo en lugar de afirmar que una estructura es universalmente más rápida.