Preguntas de Entrevista sobre Ordenación Topológica

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Qué evalúa realmente una pregunta de ordenación topológica

Las palabras «ordenación topológica» casi nunca aparecen en la pregunta. Te dan cursos con requisitos, objetivos de compilación, listas de tareas, una receta o un diccionario en un alfabeto alienígena, y la entrevista está atenta a tres cosas.

¿Ves el grafo? Todo lo que se formula como «X debe ir antes que Y» es una arista dirigida, y la respuesta es un orden de los vértices. ¿Pones los arcos en el sentido correcto? Es el fallo más común con diferencia, y produce código que se ejecuta, devuelve un orden y está al revés. ¿Sabes que la comprobación de ciclos y la ordenación son el mismo cálculo? «¿Se puede planificar?» y «dame un plan» son un solo algoritmo con dos return distintos.

Después de eso, todas las variantes son el mismo barrido llevando algo extra: un número de nivel, una duración, un conteo, un segundo grafo. Una vez que la plantilla es automática, la parte interesante de cada uno de estos problemas es el modelado, no el código. La mecánica en sí se trata en la guía de ordenación topológica; esta página trata de las ocho preguntas que de verdad se hacen.

Cada ejemplo resuelto de abajo se ejecutó con un script antes de escribirse.

2. Las dos plantillas, y cuándo gana cada una

Hay exactamente dos implementaciones que vale la pena conocer, y un entrevistador aceptará cualquiera. Escribe la que puedas producir sin dudar y sé capaz de decir por qué podrías querer la otra.

El algoritmo de Kahn, de su artículo de 1962, es el iterativo. Cuenta cuántos requisitos le quedan a cada vértice, guarda en una cola los que están a cero y emítelos.

from collections import deque

def kahn(n, edges):                  # edges guarda (u, v): u va antes que v
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1                # contar arcos HACIA v
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1            # u terminó, a v le falta uno menos
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []      # salida corta significa ciclo

La última línea lleva toda la prueba de ciclo. Si algunos vértices nunca llegan a grado de entrada cero, se están esperando entre sí, y len(order) < n es la prueba. Fíjate en que no hay ningún conjunto visited en ninguna parte: el contador de grado de entrada ya garantiza que cada vértice se emite exactamente una vez.

En este grafo la cola empieza como [1, 2], y el orden emitido es 1, 2, 4, 0, 5, 3, 6, 7. Salen los ocho vértices, así que no hay ciclo.

La versión DFS es la otra plantilla. Ejecuta una búsqueda en profundidad y añade cada vértice a una lista cuando termina, y luego invierte la lista. La sutileza que examinan los entrevistadores es el coloreado.

WHITE, GREY, BLACK = 0, 1, 2      # sin ver, en la pila, terminado

def dfs_topo(n, adj):
    colour = [WHITE] * n
    out = []
    def visit(u):
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:          # arista de retroceso: hay un ciclo
                return False
            if colour[v] == WHITE and not visit(v):
                return False
        colour[u] = BLACK
        out.append(u)                      # añadir al SALIR, no al entrar
        return True
    for v in range(n):
        if colour[v] == WHITE and not visit(v):
            return []
    return out[::-1]                       # postorden invertido

Tres colores, no un conjunto de visitados. Un simple conjunto visited no puede distinguir un arco de vuelta a la pila de recursión actual, que es un ciclo, de un arco hacia una rama ya terminada, que no lo es. Di esa frase en la entrevista y la pregunta de seguimiento sobre detección de ciclos ya está respondida.

¿Cuál usar? Kahn si el problema pide niveles, conteos, orden lexicográfico o cualquier cosa que se beneficie de procesar las fuentes por oleadas. DFS si ya estás escribiendo una búsqueda en profundidad por otro motivo, o si quieres el postorden inverso para una pasada de componentes fuertemente conexas. Ambos son O(V + E). La única diferencia práctica: el DFS recursivo necesita una profundidad de pila proporcional a la cadena más larga, que con una entrada adversa de cien mil tareas encadenadas alcanzará el límite de recursión por defecto de Python, y Kahn no.

3. Course schedule: ¿se pueden terminar todos los cursos?

La pregunta. Hay n cursos y una lista de pares [a, b] que significa «para cursar a primero debes cursar b». ¿Puedes terminarlos todos?

El paso de modelado es toda la pregunta, y es donde la mayoría de los candidatos la pierde. El par [a, b] dice b antes que a, así que el arco va b → a, y lo que aumenta es indeg[a]. Hacerlo al revés sigue produciendo una ordenación topológica válida de otro grafo, así que nada falla y la respuesta es incorrecta en silencio en cualquier caso de prueba asimétrico.

def can_finish(n, prerequisites):
    edges = [(b, a) for a, b in prerequisites]   # b antes que a
    return len(kahn(n, edges)) == n

Eso es todo: ejecuta la ordenación y compara el conteo. Di en voz alta que existe un plan exactamente cuando el grafo de requisitos es acíclico, porque un ciclo es un conjunto de cursos que se esperan unos a otros.

Añade el arco 7 → 2 al grafo de ejemplo y la cola empieza solo con el vértice 1, emite 1 y 4 y luego se vacía. Seis vértices quedan atascados, y son precisamente el ciclo 2 → 0 → 3 → 6 → 7 → 2 junto con el vértice 5, que está detrás de él.

El seguimiento: ¿qué cursos son el problema? Los restantes con grado de entrada distinto de cero son los vértices sobre un ciclo o detrás de él, que suele ser la respuesta que buscan. Si insisten en el ciclo en sí y no en todo lo que bloquea, necesitas la versión DFS: cuando encuentras un vértice gris, la pila de recursión actual desde ese vértice en adelante es el ciclo.

La trampa. Invertir los arcos. Lee el par en voz alta como «a depende de b, así que b va primero» antes de teclear, y confirma la dirección con el entrevistador con un ejemplo de dos elementos.

4. Course schedule II: devolver un orden

La pregunta. La misma entrada, pero devuelve un orden válido, o una lista vacía si no existe ninguno.

Esto es kahn sin cambios, y por eso las dos preguntas suelen hacerse una detrás de otra. La única idea nueva es una que debes mencionar por tu cuenta: el orden no es único, y el corrector acepta cualquiera válido.

Kahn devuelve 1, 2, 4, 0, 5, 3, 6, 7 y el DFS devuelve 2, 5, 1, 4, 0, 3, 6, 7. Ninguno es más correcto que el otro, y un conteo exhaustivo dice que este grafo tiene 49 órdenes válidos distintos. Si tu solución se compara con una única respuesta esperada, lo que está mal es la prueba, no la solución.

El seguimiento: devuelve el orden lexicográficamente más pequeño. Sustituye la cola por un montículo de mínimos. En cada paso extraes el vértice disponible más pequeño en lugar del que se encoló antes, lo que fija de forma voraz el menor valor posible en cada posición. El coste pasa de O(V + E) a O(V + E log V), y saber enunciar ese compromiso es el sentido del seguimiento. En el grafo de ejemplo el orden más pequeño es 1, 2, 0, 3, 4, 5, 6, 7.

La trampa. Devolver order sin la comprobación de longitud. Con una entrada cíclica devuelves un plan parcial que parece totalmente plausible, y todas las pruebas automáticas con un ciclo fallan mientras tu ejecución local del caso feliz pasa.

5. Alien dictionary: recuperar un alfabeto

La pregunta. Te dan palabras ordenadas según un alfabeto desconocido. Recupera un orden de las letras coherente con esa ordenación, o indica que no existe ninguno.

Nada aquí parece un grafo hasta que te fijas en lo que te dice «ordenadas». Compara dos palabras adyacentes, busca la primera posición en la que difieren y habrás aprendido exactamente un hecho: esa letra de la primera palabra va antes que esa letra de la segunda. Todo lo que hay después de la primera diferencia no te dice nada. Luego ordena las letras topológicamente.

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        if len(w1) > len(w2) and w1.startswith(w2):
            return ""                       # «abc» antes que «ab» es imposible
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:         # no contar dos veces un duplicado
                    adj[a].add(b)
                    indeg[b] += 1
                break                       # solo cuenta la PRIMERA diferencia
    ...                                     # luego Kahn sobre las letras

Tres detalles en seis líneas, y los entrevistadores comprueban los tres. Solo pares adyacentes. Comparar todos los pares de palabras añade aristas que la entrada no justifica. Solo la primera posición que difiere, y luego break. La regla del prefijo: si una palabra es un prefijo estricto de la anterior, la entrada se contradice y la respuesta es la cadena vacía, sin construir ningún grafo.

Con la entrada clásica ["wrt", "wrf", "er", "ett", "rftt"] las comparaciones dan t → f, w → e, r → t y e → r, y la ordenación devuelve "wertf". Con ["abc", "ab"] se activa la regla del prefijo y devuelve "". Con ["z", "x", "z"] las aristas z → x y x → z forman un ciclo, así que la comprobación de longitud también devuelve "".

El seguimiento: ¿es el alfabeto que devolviste el único? Esa es la cuestión de unicidad de la sección 7: el orden está forzado exactamente cuando la cola contiene una sola letra en cada paso. Cualquier letra que nunca aparece en una comparación flota libre y su posición es arbitraria.

La trampa. Construir el grafo a partir de las letras que aparecen en comparaciones en lugar de a partir de todas las letras de todas las palabras. Las letras que nunca se comparan tienen que aparecer igualmente en la salida, y omitirlas es el fallo que detecta una prueba oculta y no la tuya.

6. Cursos en paralelo: el número mínimo de semestres

La pregunta. Puedes cursar cualquier número de cursos a la vez, siempre que todos sus requisitos estén ya hechos. ¿Cuál es el menor número de semestres necesario?

La respuesta es el número de niveles del DAG, y el nivel de un vértice es uno más que el mayor nivel entre sus predecesores. Lleva ese número a lo largo del mismo barrido.

def min_semesters(n, edges):
    order = kahn(n, edges)
    if len(order) != n:
        return -1                          # un ciclo: nunca termina
    level = [1] * n
    for u in order:                        # todo predecesor de u ya es definitivo
        for v in adj[u]:
            level[v] = max(level[v], level[u] + 1)
    return max(level)

Como el bucle se ejecuta en orden topológico, cada predecesor de u ya ha contribuido antes de que se lea u, y esa es la propiedad que hace que baste una pasada. En el grafo de ejemplo los niveles son {1, 2}, luego {0, 4, 5}, luego {3}, luego {6}, luego {7}, así que la respuesta es 5 semestres.

El seguimiento: ¿y si solo puedes cursar como mucho k cursos por semestre? La respuesta fácil se viene abajo. El paralelismo ilimitado es lineal porque tomar con voracidad todo lo disponible es óptimo; limitar la anchura lo convierte en planificación con restricciones de precedencia en k máquinas, que es NP-difícil en general. Dos máquinas idénticas con tareas unitarias es el caso tratable clásico, resuelto por Coffman y Graham en 1972. Reconocer que el seguimiento cambia de clase de complejidad, en lugar de intentar parchear el bucle, es lo que el entrevistador quiere oír.

La trampa. Asignar un nivel la primera vez que se alcanza un vértice, como si fuera un BFS ordinario desde las fuentes. Un vértice debe esperar a su predecesor más lento, así que el nivel es un máximo, no una primera llegada. La variante BFS por oleadas solo funciona si extraes una capa entera cada vez y nunca miras un vértice antes de que su grado de entrada llegue a cero.

7. ¿Es único el orden? Reconstrucción de secuencias

La pregunta. Dado un DAG, decide si tiene exactamente un orden topológico válido. El envoltorio habitual es la reconstrucción de secuencias: te dan una secuencia y un conjunto de subsecuencias y te preguntan si la secuencia es la única coherente con ellas.

La prueba es una línea dentro del bucle de Kahn.

    while q:
        if len(q) > 1:
            return False              # hubo elección: el orden no es forzado
        u = q.popleft()
        ...

Si la cola llega a contener dos vértices, ambos están disponibles y cualquiera puede ir a continuación, así que existen al menos dos órdenes válidos. Si contiene exactamente uno en cada paso, nunca hubo que elegir y el orden está forzado.

Hay una segunda forma equivalente de decirlo que impresiona: el orden es único exactamente cuando los vértices consecutivos están unidos por un arco, es decir, cuando el orden topológico es un camino hamiltoniano en el DAG. Ambas formulaciones se comprueban en O(V + E), y citar la versión del camino hamiltoniano demuestra que entiendes por qué la unicidad es una propiedad estructural y no un accidente de la cola.

En el grafo de ejemplo, los tamaños de la cola en las ocho extracciones son 2, 2, 3, 2, 2, 1, 1, 1. El primer paso ya ofrece elegir entre 1 y 2, así que el orden no es único, lo que confirman los 49 órdenes válidos contados en la sección 4. En la cadena 0 → 1 → 2 → 3 los tamaños son 1, 1, 1, 1 y el orden está forzado.

El seguimiento: la propia reconstrucción de secuencias. Construye el grafo a partir de los pares consecutivos de cada subsecuencia, ejecuta la comprobación anterior y verifica además que el orden emitido es igual a la secuencia dada. Hacen falta ambas condiciones: un orden único distinto de la secuencia que te dieron sigue siendo un «no».

La trampa. Comprobar el tamaño de la cola solo una vez, al principio. Un grafo puede empezar con una sola fuente y ramificarse tres pasos después, así que la comparación tiene que hacerse en cada iteración. Conviene saberlo: «cada nivel contiene exactamente un vértice» es una prueba equivalente, porque un orden forzado convierte los niveles en una cadena estricta, así que razonar por niveles no está mal, solo te cuesta una segunda pasada para calcularlos.

8. El camino más largo y el camino crítico

La pregunta. Cada tarea dura un número conocido de días y no puede empezar hasta que sus requisitos estén hechos. ¿Cuándo termina el proyecto y qué tareas son las que lo deciden?

Es el problema del camino más largo, y en un grafo general es NP-difícil. En un DAG es lineal, y la razón es el orden topológico: cada predecesor de un vértice es definitivo antes de leer ese vértice, así que una sola pasada hacia delante lo resuelve.

def critical_path(n, edges, dur):
    order = kahn(n, edges)
    finish = list(dur)                     # fin más temprano si nada lo bloquea
    prev = [-1] * n
    for u in order:
        for v in adj[u]:
            if finish[u] + dur[v] > finish[v]:
                finish[v] = finish[u] + dur[v]
                prev[v] = u                # recordar quién forzó el retraso
    end = max(range(n), key=lambda v: finish[v])
    path = []
    while end != -1:
        path.append(end); end = prev[end]
    return max(finish), path[::-1]

Asigna al grafo de ejemplo las duraciones 3, 2, 4, 5, 1, 2, 6, 3 para los vértices 0 a 7 y los tiempos de finalización más tempranos salen 7, 2, 4, 12, 3, 6, 18, 21. El proyecto dura 21 días y el camino crítico es 2 → 0 → 3 → 6 → 7, cuyas duraciones suman exactamente 21. Esa cadena es lo que un gestor llama «el camino crítico»: si cualquier tarea de ella se retrasa un día, todo el proyecto se retrasa un día, mientras que la tarea 5 tiene holgura y puede desplazarse días sin que nadie lo note. Es el método de Kelley y Walker de 1959, y decir su nombre en voz alta no cuesta nada.

El seguimiento: el camino más corto en su lugar. Cambia la comparación a < y tienes caminos más cortos desde un origen en un DAG, en O(V + E), y funciona con pesos negativos, algo que Dijkstra no puede hacer. Siempre que un entrevistador mencione aristas negativas en un grafo acíclico, esta es la respuesta, no Bellman-Ford. Compara con el caso general en algoritmos de camino más corto.

La trampa. Relajar en el orden equivocado. Iterar sobre los vértices de 0 a n-1 en lugar de sobre el orden topológico da un valor que depende del etiquetado: en este grafo informa en silencio de 17 en lugar de 21, porque el vértice 0 se lee antes de que el vértice 2 haya contribuido a él. Todo el sentido del orden topológico es que hace que baste una pasada.

9. Estados finalmente seguros: ordenar el grafo inverso

La pregunta. Un nodo es seguro si todos los caminos que salen de él llegan a un nodo terminal, de modo que nunca puedes quedarte atrapado en un ciclo. Devuelve todos los nodos seguros en orden ascendente.

Formulado hacia delante esto es incómodo. Invierte todos los arcos y se convierte en una ordenación topológica: quita los nodos con grado de salida cero, que son los terminales, y cada vez que el grado de salida restante de un nodo llega a cero, todos sus sucesores eran seguros, así que él también lo es.

def safe_nodes(graph):
    n = len(graph)
    rev = [[] for _ in range(n)]
    outdeg = [len(graph[u]) for u in range(n)]
    for u in range(n):
        for v in graph[u]:
            rev[v].append(u)
    q = deque(v for v in range(n) if outdeg[v] == 0)   # terminales
    safe = []
    while q:
        u = q.popleft()
        safe.append(u)
        for p in rev[u]:
            outdeg[p] -= 1
            if outdeg[p] == 0:
                q.append(p)
    return sorted(safe)

Es el algoritmo de Kahn con el grado de entrada sustituido por el de salida y los arcos invertidos, y conviene decirlo explícitamente porque demuestra que reconoces la plantilla bajo un disfraz. En el ejemplo estándar [[1,2], [2,3], [5], [0,5], [5], [], []] la respuesta es [2, 4, 5, 6]: los nodos 5 y 6 son terminales, 2 y 4 solo llevan a ellos, y 0, 1 y 3 están en el ciclo 0 → 1 → 3 → 0.

El seguimiento: hazlo con DFS. Otra vez tres colores. Un nodo es seguro si ningún arco desde él alcanza un vértice gris, y puedes memoizar el resultado por nodo para que todo siga siendo lineal. Los entrevistadores suelen querer oír ambas, porque la versión del grafo inverso es la que los candidatos rara vez encuentran por sí solos.

La trampa. Responder «los nodos que no están en un ciclo». Según esa lectura, el nodo 3 no está en ningún ciclo propio, pero tiene un arco hacia el ciclo que pasa por 0, así que no es seguro. La seguridad trata de todos los caminos desde el nodo, no del nodo en sí.

10. Ordenar elementos por grupo: dos niveles a la vez

La pregunta. Los elementos pertenecen a grupos, algunos elementos deben ir antes que otros y los elementos del mismo grupo deben quedar contiguos en la salida. Devuelve un orden válido o una lista vacía.

Esta es la variante difícil, y la idea es pequeña: ejecuta dos ordenaciones topológicas. Una sobre los grupos, con un arco entre grupos cada vez que un elemento de uno debe ir antes que un elemento de otro, y otra sobre los elementos dentro de cada grupo. Luego concatena los grupos en el orden de grupos, cada uno relleno con sus propios elementos ordenados.

La única parte delicada son los elementos sin grupo. Un elemento con grupo -1 no está restringido por ninguna agrupación, así que dale a cada uno un grupo nuevo y propio. Juntarlos todos en un único grupo es la respuesta errónea clásica: obliga a elementos sin relación a ser contiguos y puede convertir un caso resoluble en uno sin solución.

Si cualquiera de las dos ordenaciones falla, falla todo el caso, así que la comprobación de longitud se hace dos veces. La complejidad sigue siendo O(V + E) en ambas pasadas, ya que cada elemento y cada dependencia se tocan un número constante de veces.

El seguimiento: ¿es un curso requisito de otro? Eso es Course Schedule IV, y pide alcanzabilidad en lugar de un orden. Procesa los vértices en orden topológico y une el conjunto alcanzable de cada vértice en sus sucesores, usando bitsets: O(V × E / 64) en la práctica, y el orden topológico es lo que garantiza que un conjunto está completo antes de copiarse hacia delante.

La trampa. Ordenar los grupos pero olvidar que un grupo también puede formar un ciclo consigo mismo a través de dos elementos de grupos distintos. Construye el grafo de grupos a partir de las dependencias de elementos solo cuando los dos grupos difieren, o crearás bucles que hacen fallar la ordenación sin motivo.

11. Las respuestas de complejidad

Tenlas preparadas, porque se preguntan tal cual y la respuesta es corta.

Dos cosas que añadir sin que te lo pidan. Primero, el grafo normalmente no te lo dan como lista de adyacencia: llega como una lista de pares, y construir la lista también cuesta O(V + E), así que citar una cota que ignore la construcción es incorrecto. Segundo, una ordenación topológica no es una ordenación por comparación y no está limitada por O(n log n): es lineal precisamente porque la entrada ya aporta las restricciones de orden en lugar de obligarte a descubrirlas.

La versión DFS recursiva también usa O(V) de profundidad de pila en el peor caso, que es un límite real y no teórico. Una cadena de 100.000 tareas agota el límite de recursión por defecto de Python, de 1000, mucho antes de agotar la memoria.

12. Errores que suspenden la entrevista

Ordenados según su frecuencia; los dos primeros explican la mayoría de las soluciones rechazadas.

• Construir los arcos al revés. El par [a, b] en Course Schedule significa b antes que a. Al revés, el código sigue devolviendo un orden, solo que es un orden para el problema reflejado. Lee el par en voz alta antes de teclear.
• Omitir la comprobación len(order) == V. Sin ella, una entrada cíclica produce un plan parcial que parece correcto. El conteo es la prueba de ciclo, y el orden es el subproducto.
• Usar un conjunto de visitados en la versión DFS. Dos estados no pueden distinguir una arista de retroceso de un arco hacia una rama terminada, así que o te pierdes ciclos o te los inventas. Tres colores, siempre.
• Perder vértices sin aristas. Construir el grafo solo a partir de la lista de pares descarta en silencio todos los cursos sin requisitos y sin dependientes. Parte del número de vértices que te dieron.
• Asignar niveles en la primera llegada. Un vértice espera a su predecesor más lento, así que su nivel es un máximo sobre los predecesores, no el primer valor que le llega.
• Relajar fuera del orden topológico. Los barridos de camino más largo y más corto solo son correctos porque cada predecesor es definitivo cuando se lee un vértice. Iterar por los índices de los vértices devuelve en silencio un número menor.
• Contar dos veces dependencias duplicadas. Si la entrada puede repetir un par, elimina duplicados antes de contar los grados de entrada o resta una vez por cada arco guardado. Contar un duplicado en un sitio y no en el otro deja un vértice atascado para siempre con grado de entrada uno.
• Afirmar que el orden es único. Casi nunca lo es, y afirmarlo invita a la pregunta de seguimiento que no has preparado. Di «un orden válido» y ofrece la prueba de unicidad si la quieren.
• No preguntar por la entrada. ¿Pueden repetirse las dependencias? ¿Puede un curso depender de sí mismo? ¿Los identificadores de vértice son enteros consecutivos o cadenas arbitrarias? Cada respuesta cambia las diez primeras líneas que escribes.

El hábito que evita la mayoría de estos errores: antes de escribir nada, di en qué dirección van los arcos y cuál es la respuesta cuando la ordenación se queda corta. Si no puedes decir ambas cosas en una frase, aún no estás listo para teclear.

14. Referencias

Los artículos que introdujeron estas técnicas y los libros que las analizan, en orden cronológico.

1. Kelley, J. E. y Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
2. Kahn, A. B. (1962). “Topological sorting of large networks.” Communications of the ACM, 5(11), 558–562.
3. Knuth, D. E. (1968). The Art of Computer Programming, Volume 1: Fundamental Algorithms, sección 2.2.3. Addison-Wesley.
4. Coffman, E. G. y Graham, R. L. (1972). “Optimal scheduling for two-processor systems.” Acta Informatica, 1(3), 200–213.
5. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
6. Tarjan, R. E. (1976). “Edge-disjoint spanning trees and depth-first search.” Acta Informatica, 6(2), 171–185.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. y Stein, C. (2009). Introduction to Algorithms, 3.ª edición, sección 22.4. MIT Press.
8. Sedgewick, R. y Wayne, K. (2011). Algorithms, 4.ª edición, sección 4.2. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6.ª edición. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3.ª edición, sección 5.10. Springer.