Entrevista técnica de código: Resolver Alien Dictionary con ordenamiento topológico

Planteamiento y contexto aplicable

Dado un arreglo words de cadenas ASCII no vacías en minúsculas, asume que se afirma que el arreglo está ordenado según un alfabeto desconocido. Devuelve cualquier ordenamiento que contenga cada carácter distinto de la entrada exactamente una vez y haga que la lista de palabras esté ordenada. Devuelve una cadena vacía cuando no exista dicho ordenamiento. Si funcionan varios alfabetos, cualquiera de ellos es aceptable.

Para la versión de entrevista, asume a lo sumo 10,000 palabras y a lo sumo 100,000 caracteres en total. Estas son restricciones del ejercicio, no límites de una plataforma en particular. Para ["wrt", "wrf", "er", "ett", "rftt"], una respuesta es "wertf". La lista ["abc", "ab"] es imposible porque una palabra más larga precede a su propio prefijo. La lista ["z", "x", "z"] es imposible porque implica tanto z < x como x < z.

La parte difícil viene antes del ordenamiento topológico. La entrada proporciona palabras ordenadas; las aristas del grafo deben deducirse. Una solución correcta debe inferir exactamente las restricciones justificadas por la comparación lexicográfica, retener los caracteres que no tienen aristas y distinguir un prefijo inválido de un ciclo dirigido.

Lo que evalúa el entrevistador

La primera señal es si el candidato deriva una arista a partir del primer carácter que difiere entre dos palabras adyacentes. Si "wrt" aparece antes de "wrf", la comparación demuestra t < f. Los caracteres posteriores a esa primera diferencia no revelan nada sobre este par porque la comparación lexicográfica ya se ha decidido.

La segunda señal es el razonamiento de prefijos. Cuando todos los caracteres comparados coinciden, la palabra más corta debe ir primero. "ab" antes de "abc" no agrega ninguna arista y sigue siendo válido; "abc" antes de "ab" contradice todo alfabeto posible. El ordenamiento topológico por sí solo no puede descubrir esta contradicción porque no crea ninguna arista.

La tercera señal es la construcción completa del grafo. Cada carácter observado necesita un nodo, incluido un carácter aislado de una entrada de una sola palabra. La evidencia repetida para la misma arista no debe incrementar el grado de entrada dos veces. Un conjunto por nodo de origen mantiene la adyacencia y el grado de entrada consistentes.

Las señales finales son la demostración y la validación. El algoritmo de Kahn devuelve un orden completo solo cuando elimina cada nodo. Una salida más corta demuestra que queda un ciclo. Múltiples opciones con grado de entrada cero significan que la evidencia no determina un único alfabeto; eso es válido bajo el contrato base y no debe etiquetarse erróneamente como un error.

Preguntas para aclarar antes de responder

• ¿La entrada incluye todos los caracteres del alfabeto? Esta respuesta ordena cada carácter observado en las palabras. No puede inventar ni ubicar caracteres no vistos sin una definición externa del alfabeto.
• ¿Se acepta cualquier orden válido? El problema base acepta cualquiera. Exigir el resultado más pequeño según el orden de caracteres del lenguaje anfitrión necesita un min-heap y cambia la complejidad.
• ¿Cómo debe representarse la imposibilidad? Este contrato utiliza una cadena vacía tanto para un prefijo inválido como para un ciclo. Una API de producción puede devolver un motivo estructurado y un testigo.
• ¿Qué es un carácter? La entrada base contiene letras ASCII en minúsculas. Los puntos de código Unicode o los grupos de grafemas requieren un contrato de tokenización antes de la construcción del grafo.
• ¿Pueden repetirse las palabras? Sí. Las palabras adyacentes iguales no añaden ninguna restricción. No hacen que el diccionario sea inválido.
• ¿El alfabeto debe ser único? No. Una pregunta de seguimiento puede detectar la unicidad verificando el número de nodos disponibles con grado de entrada cero en cada paso.
• ¿La entrada puede estar vacía? Esta versión requiere al menos una palabra no vacía. Si se permite una entrada vacía, confirma si el resultado esperado es un alfabeto vacío o una solicitud inválida.

Estructura de respuesta en 30 segundos

“Crearé un nodo de grafo para cada carácter distinto. Para cada par de palabras adyacentes, escaneo hasta la primera diferencia; eso da una arista dirigida desde el carácter de la palabra anterior hacia el carácter de la palabra posterior. Si no hay diferencia y la palabra anterior es más larga, el orden de los prefijos es imposible, por lo que devuelvo una cadena vacía. Desduplico las aristas mientras mantengo los grados de entrada, y luego ejecuto el ordenamiento topológico de Kahn desde todos los caracteres con grado de entrada cero. Si proceso cada nodo, el resultado respeta cada comparación inferida; si proceso menos nodos, un ciclo hace que el diccionario sea inconsistente. El tiempo total es lineal respecto a los caracteres de entrada más el grafo, y se aceptan múltiples órdenes topológicos válidos.”

Análisis detallado paso a paso

Sea C el número total de caracteres en todas las palabras, U el número de caracteres distintos y E el número de aristas de precedencia distintas. Inicializa graph[ch] como un conjunto y indegree[ch] como cero para cada carácter encontrado. Esta inicialización es necesaria antes de comparar palabras: un carácter puede ser válido y no tener restricciones, por lo que los extremos de las aristas por sí solos no definen el conjunto de nodos.

Compara solo palabras adyacentes. Las comparaciones adyacentes son suficientes porque demostrar que cada par vecino está ordenado demuestra que toda la lista está ordenada por transitividad. También evitan el número cuadrático de comparaciones entre pares de palabras. Para un par first y second, inspecciona las posiciones coincidentes hasta la longitud más corta:

1. En el primer desajuste first[i] != second[i], agrega first[i] -> second[i] y detén la comparación de ese par.
2. Si todas las posiciones compartidas coinciden y first es más largo, devuelve una cadena vacía.
3. Si todas las posiciones compartidas coinciden y first no es más largo, no agregues ninguna arista.

Solo una arista recién insertada incrementa el grado de entrada del destino. Supongamos que tanto "za" < "zb" como "ca" < "cb" implican a -> b. Contar esa arista dos veces dejaría a b con un grado de entrada positivo después de que a sea eliminado y reportaría falsamente un ciclo.

El algoritmo de Kahn coloca cada carácter con grado de entrada cero en una cola. Su invariante es: para cada carácter no procesado, el grado de entrada es igual al número de aristas entrantes desde otros caracteres no procesados; la cola contiene exactamente los caracteres sin tal predecesor. Eliminar un carácter de la cola es seguro. Decrementar cada vecino saliente modela la eliminación de esas aristas, y un vecino entra en la cola cuando desaparece su último predecesor no cumplido.

from collections import deque


def alien_order(words: list[str]) -> str:
    graph = {char: set() for word in words for char in word}
    indegree = {char: 0 for char in graph}

    for first, second in zip(words, words[1:]):
        limit = min(len(first), len(second))

        for index in range(limit):
            before = first[index]
            after = second[index]
            if before == after:
                continue

            if after not in graph[before]:
                graph[before].add(after)
                indegree[after] += 1
            break
        else:
            if len(first) > len(second):
                return ""

    ready = deque(
        char for char, degree in indegree.items() if degree == 0
    )
    order: list[str] = []

    while ready:
        char = ready.popleft()
        order.append(char)

        for neighbor in graph[char]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)

    return "".join(order) if len(order) == len(indegree) else ""

La demostración tiene dos niveles. Primero, la extracción del grafo es sólida: cada arista proviene del primer desajuste de un par adyacente, por lo que todo alfabeto válido debe respetarla. La verificación de prefijo elimina el único caso adyacente en el que no existe desajuste pero el ordenamiento es imposible. Segundo, el ordenamiento topológico es sólido: el invariante de la cola asegura que cada carácter de salida aparezca después de todos los predecesores inferidos. Por lo tanto, cada par de palabras adyacentes está ordenado, lo que hace que la lista completa esté ordenada.

Si el algoritmo produce menos de U caracteres, cada nodo restante tiene un grado de entrada positivo. Comenzar desde cualquier nodo restante y seguir repetidamente una arista entrante debe volver a visitar un nodo en un grafo finito; el segmento repetido es un ciclo dirigido. Ningún alfabeto lineal puede satisfacer ese ciclo. Por el contrario, un grafo acíclico siempre tiene un nodo con grado de entrada cero, por lo que el algoritmo de Kahn finalmente elimina todos los nodos y devuelve un orden válido.

Construir todos los nodos y escanear palabras adyacentes toma O(C). Cada nodo y arista distintos se procesan una vez mediante el algoritmo de Kahn, por lo que el tiempo total es O(C + U + E) y el espacio adicional es O(U + E). Con ASCII en minúsculas, U es a lo sumo 26, pero mantener el límite simbólico hace que el razonamiento sea reutilizable.

La validación debe verificar propiedades cuando son posibles múltiples respuestas. Un resultado no vacío debe contener los caracteres de entrada distintos exactamente una vez. Para cada par adyacente, compáralo usando el mapa de rangos devuelto y confirma que está ordenado; por separado, confirma que ninguna palabra más larga preceda a su prefijo. Prueba una sola palabra, palabras repetidas, caracteres aislados, evidencia de aristas duplicadas, un prefijo válido, un prefijo inválido, un ciclo, una cadena y un grafo con varios nodos de grado de entrada cero.

DFS con estados blanco, gris y negro es una alternativa correcta. Detecta ciclos a través de una arista a un nodo gris e invierte el postorden para el resultado. El algoritmo de Kahn hace visible la ambigüedad a través del conjunto de listos y evita preocupaciones sobre la profundidad de recursión, por lo que es la recomendación más clara para este contrato.

Respuesta de muestra de alta calidad

“Primero necesito inferir un orden parcial a partir de las palabras ordenadas. Creo un nodo para cada carácter, incluidos los caracteres que nunca participan en una arista. Para cada par vecino, escaneo hasta el primer desajuste. Si el par es wrt y wrf, agrego t -> f y me detengo porque las posiciones posteriores no pueden afectar esa comparación. Si no hay desajuste y la primera palabra es más larga, como abc antes de ab, la entrada ya es inconsistente.

Almaceno los vecinos en conjuntos para que la evidencia repetida de una relación incremente el grado de entrada solo una vez. Luego ejecuto el algoritmo de Kahn: encolo todos los caracteres con grado de entrada cero, saco uno hacia la respuesta, decremento sus vecinos salientes y encolo un vecino cuando su grado de entrada llega a cero. El invariante es que los caracteres en cola no tienen predecesores restantes entre los caracteres no procesados, por lo que cada carácter emitido es seguro.

Si la longitud de la salida es igual al número de caracteres distintos, se respeta cada arista inferida. Esas aristas más las comprobaciones de prefijos hacen que cada par de palabras adyacentes esté ordenado, por lo que toda la lista está ordenada. Si la longitud es menor, el grafo restante contiene un ciclo y ningún alfabeto funciona. El tiempo de ejecución es O(C + U + E) con espacio O(U + E). Probaría una palabra más larga antes de su prefijo, un ciclo de dos aristas, evidencia duplicada para una arista, una sola palabra y un caso con varias salidas válidas; para el último caso validaría las propiedades de ordenamiento en lugar de esperar una sola cadena.”

Errores comunes

• Usar cada posición que difiere en un par de palabras → las posiciones posteriores no participan una vez que el primer desajuste decide el orden lexicográfico → agrega solo la arista del primer desajuste y deténte.
• Ejecutar únicamente ordenamiento topológico → "abc" antes de "ab" no crea ninguna arista y se pasa por alto → verifica la contradicción de más largo antes del prefijo durante la comparación de pares.
• Crear nodos solo al agregar aristas → los caracteres aislados desaparecen de la respuesta → inicializa un nodo para cada carácter observado.
• Incrementar el grado de entrada para aristas duplicadas → un nodo válido nunca llega a cero → utiliza un conjunto de adyacencia e incrementa solo en la primera inserción.
• Devolver el resultado parcial cuando la cola se vacía → las restricciones cíclicas parecen exitosas → exige que la longitud de salida sea igual al conteo de caracteres distintos.
• Exigir una respuesta fija única → los órdenes parciales válidos pueden tener varias extensiones lineales → prueba el orden devuelto frente a caracteres, aristas y comparaciones de palabras.
• Comparar cada par de palabras → el trabajo puede volverse cuadrático respecto a la cantidad de palabras → las comparaciones adyacentes son suficientes para establecer el orden.
• Afirmar que la ambigüedad significa entrada inválida → múltiples alfabetos pueden explicar la misma evidencia → devuelve cualquier orden válido a menos que la unicidad sea parte del contrato.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Cómo determinas si el alfabeto es único?

Durante el algoritmo de Kahn, inspecciona el conjunto de listos antes de cada extracción. Si en algún momento contiene más de un carácter, al menos dos opciones pueden intercambiarse en diferentes órdenes topológicos válidos, por lo que la evidencia es ambigua. Si siempre contiene exactamente un carácter y se procesan todos los nodos, el orden es único. Un conjunto de listos vacío antes de la finalización sigue significando un ciclo.

Pregunta de seguimiento 2: ¿Cómo devuelves el resultado válido más pequeño según el orden normal de caracteres?

Reemplaza la cola con un min-heap ordenado según el orden de caracteres del lenguaje anfitrión. Elegir el carácter actualmente válido más pequeño produce la extensión lineal más pequeña mediante un argumento de intercambio voraz. El tiempo pasa a ser O(C + E + U log U); aclara explícitamente que este desempate es externo al alfabeto alienígena.

Pregunta de seguimiento 3: ¿Cómo devolverías una explicación útil para una entrada inválida?

Para una contradicción de prefijo, devuelve las dos palabras adyacentes y sus índices. Para un ciclo, ejecuta un DFS de tres colores en el grafo restante después de que Kahn se detenga, mantén punteros a los padres y reconstruye los caracteres que forman un ciclo de arista hacia atrás. Un resultado estructurado puede distinguir invalid_prefix, cycle y valid sin sobrecargar la cadena vacía.

Pregunta de seguimiento 4: ¿Se puede procesar la lista de palabras como un flujo (stream)?

Mantén la palabra anterior, agrega nodos de cada nueva palabra y deriva la restricción del par adyacente cuando llegue la siguiente palabra. El grafo y los grados de entrada aún necesitan almacenamiento hasta que termine el flujo porque la evidencia posterior puede agregar predecesores o crear un ciclo. Ejecuta el ordenamiento topológico solo después de haber observado todas las palabras, a menos que la fuente proporcione un límite de finalización.

Pregunta de seguimiento 5: ¿Cómo enumerarías todos los alfabetos válidos?

Realiza un backtracking sobre todos los caracteres actuales con grado de entrada cero. Elige uno, elimina sus aristas salientes, realiza la recursión y luego restaura el estado. Esto enumera solo órdenes válidos, pero la salida puede aproximarse a U!; confirma un alfabeto pequeño o un límite de salida antes de implementarlo.

Pregunta de seguimiento 6: ¿Qué cambia para palabras en Unicode?

Define primero la unidad de comparación. Los puntos de código no siempre coinciden con los caracteres percibidos por el usuario, y la intercalación (collation) de la configuración regional puede tratar de manera especial las formas normalizadas o las secuencias de múltiples puntos de código. Tokeniza cada palabra de acuerdo con los símbolos del alfabeto declarados, normaliza solo si el contrato lo requiere, y luego ejecuta el mismo algoritmo de grafos sobre los tokens. Sin ese contrato, el “orden de caracteres” queda subespecificado.