algorithm - tecnica - tipos de preguntas en una entrevista de trabajo

Pregunta de la entrevista, Recuperar orden alfabético del diccionario

Question

Mi novia recibió esta pregunta en una entrevista, y me gustó tanto que pensé que la compartiría ... Escribe un algoritmo que recibe un diccionario (Array of words). La matriz está ordenada lexicográficamente, pero el orden abc puede ser cualquier cosa. Por ejemplo, podría ser z, y, x, .., c, b, a. O podría estar completamente desordenado: d, g, w, y, ... Ni siquiera necesita incluir todas las letras abc, y finalmente no tiene que ser letras en absoluto. Podría ser cualquier símbolo que forme una cadena. Por ejemplo, podría estar compuesto por 5, α,!, @, Θ ... Tienes la idea. Depende de su algoritmo descubrir qué son las letras (parte fácil).

El algoritmo debe devolver el orden lexicográfico correcto de los símbolos.

Nota / Cosas a considerar: 1. Para un diccionario dado, ¿siempre puedes descubrir el orden completo de todas las letras? Considere un diccionario que solo tiene 1 palabra, con más de 1 símbolo ... 2. NO PUEDE asumir que el diccionario no contiene errores. El algoritmo debe determinar si el diccionario contiene contradicciones y generar un error. 3. SUGERENCIA: piense en una buena estructura de datos para representar las relaciones que descubre entre los símbolos. Esto debería hacer el problema mucho más fácil.

Publicaré mi solución probablemente mañana. De ninguna manera afirmo que sea la más eficiente. Quiero ver los pensamientos de otras personas primero. Espero que disfrutes la pregunta

PD: Creo que el mejor formato para publicar soluciones es con pseudo código, pero lo dejo a su consideración

Answer 1

Esta es una clasificación topológica en un gráfico acíclico dirigido . Primero debe construir el gráfico: los vértices son letras, y hay un borde si uno es lexicográficamente menor que el otro. El orden topológico te da la respuesta.

Una contradicción es cuando el gráfico dirigido no es acíclico. La singularidad se determina según si existe o no una ruta hamiltoniana, que se puede probar en tiempo polinomial.

Construyendo la grafica

Para hacerlo, compara cada dos "palabras" consecutivas del diccionario. Digamos que tiene estas dos palabras apareciendo una tras otra:

x156@
x1$#2z

Luego encuentra el prefijo común más largo, x1 en este caso, y verifica los siguientes caracteres inmediatamente después de este prefijo. En este caso, tenemos 5 y $ . Dado que las palabras aparecen en este orden en el diccionario, podemos determinar que 5 deben ser lexicográficamente más pequeños que $ .

Del mismo modo, dadas las siguientes palabras (aparecen una tras otra en el diccionario)

jhdsgf
19846
19846adlk

Podemos decir que ''j'' < ''1'' del primer par (donde el prefijo común más largo es la cadena vacía). El segundo par no nos dice nada útil (ya que uno es un prefijo de otro, por lo que no hay caracteres para comparar).

Ahora supongamos que más adelante vemos lo siguiente:

oi1019823
oij(*#@&$

Luego encontramos una contradicción, porque esta pareja dice que ''1'' < ''j'' .

El ordenamiento topológico.

Hay dos formas tradicionales de hacer una clasificación topológica. Algorítmicamente más simple es el enfoque de búsqueda primero en profundidad , donde hay un borde de x a y si y < x .

El pseudocódigo del algoritmo se encuentra en Wikipedia:

L ← Empty list that will contain the sorted nodes
S ← Set of all nodes with no incoming edges

function visit(node n)
    if n has not been visited yet then
        mark n as visited
        for each node m with an edge from n to m do
            visit(m)
        add n to L

for each node n in S do
    visit(n)

Al concluir el algoritmo anterior, la lista L contendría los vértices en orden topológico.

Comprobando la singularidad

Lo siguiente es una cita de Wikipedia:

Si una ordenación topológica tiene la propiedad de que todos los pares de vértices consecutivos en el orden ordenado están conectados por bordes, estos bordes forman una ruta Hamiltoniana dirigida en el DAG. Si existe una ruta hamiltoniana, el ordenamiento topológico es único; Ningún otro orden respeta los bordes del camino. A la inversa, si un ordenamiento topológico no forma una ruta hamiltoniana, el DAG tendrá dos o más ordenamientos topológicos válidos, ya que en este caso siempre es posible formar un segundo ordenamiento válido intercambiando dos vértices consecutivos que no están conectados por un borde el uno al otro Por lo tanto, es posible probar en tiempo polinomial si existe un ordenamiento único y si existe una ruta hamiltoniana.

Por lo tanto, para verificar si el orden es único o no, simplemente verifique si los dos vértices consecutivos en L (del algoritmo anterior) están conectados por bordes directos. Si lo son, entonces el orden es único.

Análisis de complejidad

Una vez que se construye el gráfico, la clasificación topológica es O(|V|+|E|) . La comprobación de unicidad es O(|V| edgeTest) , donde edgeTest es la complejidad de probar si dos vértices están conectados por un borde. Con una matriz de adyacencia , esto es O(1) .

La construcción del gráfico requiere solo un solo escaneo lineal del diccionario. Si hay W palabras, entonces es O(W cmp) , donde cmp es la complejidad de comparar dos palabras. Siempre compara dos palabras subsiguientes, por lo que puede hacer todo tipo de optimizaciones si es necesario, pero de lo contrario una comparación ingenua es O(L) donde L es la longitud de las palabras.

También puede hacer un cortocircuito en la lectura del diccionario una vez que haya determinado que tiene suficiente información sobre el alfabeto, etc., pero incluso un paso de construcción ingenuo tomaría O(WL) , que es el tamaño del diccionario.

Answer 2

Quieres encontrar un orden total de símbolos.

1) Usted claramente no siempre puede determinar un orden total.

2) Puedes usar un gráfico acíclico dirigido para representar el orden parcial entre símbolos. Cada letra está representada solo una vez en la gráfica. Lo llena observando todos los pares de letras en la misma posición en cada par de palabras consecutivas. Cualquier ciclo que cree en el gráfico apunta a un error en el diccionario. Usted aplana el conjunto de relaciones como a-> d, a-> b, b-> d en a-> b-> d. Si lo que obtiene al final es un gráfico con una fuente (letra sin predecesores) y un sumidero (letra sin sucesores), tiene un orden total, como el alfabeto.

Answer 3

Resolví esto usando el otro algoritmo sugerido en Wikipedia. Aquí está el psuedocode de Wikipedia:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

Creo que ofrece un enfoque más "de sentido común" para encontrar un camino (es decir, cómo lo resolvería si estuviera mirando un gráfico y tiene que encontrar un camino). Aún así, no ofrece ninguna ventaja al enfoque de primero en profundidad sugerido por los polietelubricantes (si agrega el código de detección de ciclo como se sugiere en los comentarios) Gracias por sus comentarios. respuestas

Answer 4

Tiene el diccionario en una serie de palabras y sugiero utilizar esta estructura de datos, porque es lo suficientemente bueno y la conversión lleva tiempo.

Quieres encontrar el orden correcto de los personajes,

C1, C2, C3, C4, ..., Cn

Tienes m numero de palabras en tu diccionario. Sería excelente tener un conjunto de reglas, como (Ci, Cj), lo que significa que Ci <= Cj, donde i, j son números naturales positivos e i <m, j <m. Deberíamos tener un conjunto de errores.

Debido a que V es un número enorme y es mayor que m * m, un buen enfoque en mi opinión sería el siguiente:

foreach i = 1, m do
    foreach j = i + 1, m do
        findFirstDifferenceInTheWords
        /*charI is the first difference in Wi from Wj and charJ is the first difference in 
          Wj*/
        if (Wi <> Wj)
            if (Wi contains Wj or Wj contains Wi) == false
            charSet.add(charI, charJ)
        else if k exists and the following is true ((i < k < j) and (Wi <> Wk))
            error.addIfDoesntExist("paradox", Wi)
        else
            error.addIfDoesntExist("redundant", Wi)
        end_if
    end_foreach
end_foreach

Hemos encontrado l número de reglas

foreach i = 1, lo hago foreach j = i + 1, lo hago si charSet.exists (charI, charJ) y charSet.exists (charJ, charI) error.add ("relación paradójica", charI, charJ)

Después de esto, puede construir el orden de las palabras considerando que charI = charJ es a la vez (charI, charJ) y (charJ, charI) existe en el conjunto y donde charI <= charJ es la única regla, no al revés, podemos considerar que charI <charJ.

Conclusión: usar la relación "<=" es mejor que usar la relación "<", porque "<=" es una relación ordenada y completa en la teoría numérica, "<" es simplemente una buena ordenación. NOTA: La salida debe mostrarse correctamente si charI <charJ o charI = charJ. Por ejemplo, puede usar esta notación: caracteres (C1C2C3, C4, C5C6, ...) Donde C1 = C2 = C3 <C4 <C5 = C6 ...

Espero que esto ayude.

Por supuesto, si Wj contiene Wi, entonces no podemos extraer una regla desde allí.