Domanda da Interview, Recupera ordine alfabetico dal dizionario [chiusa]

StackOverflow https://stackoverflow.com/questions/3123554

Domanda

La mia ragazza si a questa domanda in un'intervista, e mi è piaciuto così tanto che ho pensato che avrei condividerlo ... Scrivere un algoritmo che riceve un dizionario (Array di parole). L'array è ordinato lessicografico, ma l'ordine abc può essere qualsiasi cosa. Ad esempio, potrebbe essere z, y, x, .., c, b, a. Oppure potrebbe essere completamente incasinato: d, g, w, y, ... E non ha nemmeno bisogno di includere tutte le lettere abc, e, infine, non deve essere lettere a tutti. Potrebbe essere qualsiasi simbolo che formano una stringa. Per esempio potrebbe essere costituito da 5, a,!, @, T ... Si ottiene l'idea. E 'fino al vostro algoritmo per scoprire quali sono le lettere (parte più semplice).

L'algoritmo deve restituire il corretto ordine lessicografico dei simboli.

Nota / Le cose da considerare: 1. Per un determinato dizionario, si può sempre scoprire l'ordine completo di tutte le lettere? Si consideri un dizionario che ha solo 1 parola, con più di 1 simbolo ... 2. Non è possibile supporre che il dizionario è senza errori. L'algoritmo dovrebbe determinare se il dizionario contiene contraddizioni e di uscita che ci sia un errore. 3. SUGGERIMENTO: Pensate a una struttura di dati buona per rappresentare i rapporti si scoprono tra i simboli. Questo dovrebbe rendere il problema molto più facile.

Vi posto la mia soluzione, probabilmente domani. In nessun modo posso richiedere che sia il più efficiente. Voglio vedere i pensieri 'di altre persone prima. Spero che ti piace la domanda

P.S. Credo che il miglior formato per Post Solutions è con pseudo codice, ma lascio questo per la vostra considerazione

È stato utile?

Soluzione

Questa è topologica ordinamento su un diretto aciclico grafico . È necessario prima build del grafico: i vertici sono lettere, e c'è un vantaggio se si è lessicografico inferiore rispetto agli altri. L'ordine topologico, allora si dà la risposta.

Una contraddizione è quando il grafo orientato non è aciclico. Unicità è determinato dal fatto che esista o meno un percorso hamiltoniano, che è verificabile in tempo polinomiale.

Costruire il grafico

A tale scopo, mettendo a confronto ogni due "parole" consecutivi dal dizionario. Diciamo che si dispone di queste due parole che appaiono uno dopo l'altro: 

x156@
x1$#2z

Poi si trova il più lungo prefisso comune, x1 in questo caso, e controllare immediatamente successivi caratteri dopo questo prefisso. In questo caso ,, abbiamo 5 e $. Dal momento che le parole appaiono in questo ordine nel dizionario, possiamo determinare che 5 deve essere più piccolo di lexicographically $.

Allo stesso modo, date le seguenti parole (che appaiono uno dopo l'altro nel dizionario) 

jhdsgf
19846
19846adlk

Si può dire che 'j' < '1' dalla prima coppia (dove il più lungo prefisso comune è la stringa vuota). La seconda coppia non ci dice nulla di utile (dal momento che uno è un prefisso di un altro, quindi non ci sono caratteri da confrontare).

Ora supponiamo poi vediamo la seguente: 

oi1019823
oij(*#@&$

Poi abbiamo trovato una contraddizione, perché questa coppia dice che '1' < 'j'.

L'ordinamento topologico

Ci sono due modi tradizionali per fare ordinamento topologico. Algoritmicamente più semplice è la ricerca approccio in profondità, dove c'è un vantaggio da x a y se y < x.

Il pseudocodice dell'algoritmo è dato in 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 termine dell'algoritmo sopra, la lista L conterrebbe i vertici in ordine topologico.

Controllo unicità

La seguente è una citazione da Wikipedia:

  

Se un ordinamento topologico ha la proprietà che tutte le coppie di vertici consecutivi in ??modo ordinato sono collegati da bordi, allora questi bordi formare un percorso hamiltoniano diretto nel DAG. Se esiste un percorso hamiltoniano, l'ordinamento topologico è unico; nessun altro ordine rispetta i bordi del percorso. Al contrario, se un ordinamento topologico non forma un percorso hamiltoniano, il DAG avrà due validi ordinamenti topologici, per in questo caso è sempre possibile formare un secondo ordine valida scambiando due vertici consecutivi che non sono collegati da un bordo tra loro. Pertanto, è possibile prova in tempo polinomiale se esiste un ordinamento unico, e se esiste un percorso hamiltoniano.

Così, per verificare se l'ordine è unico o meno, si controlla semplicemente se tutti i due vertici consecutivi L (dal algoritmo di cui sopra) sono collegati da bordi diretti. Se lo sono, allora l'ordine è unico.

Analisi di complessità

Una volta che il grafico viene costruito, ordinamento topologico è O(|V|+|E|). controllo di univocità è O(|V| edgeTest), dove edgeTest è la complessità di testare se due vertici sono collegati da un bordo. Con un adiacenza matrice , questo è O(1).

Costruire il grafico richiede solo una singola scansione lineare del dizionario. Se ci sono parole W, allora è O(W cmp), dove cmp è la complessità del confronto tra due parole. Si confronta sempre due subseqparole confluenti, in modo da poter fare tutti i tipi di ottimizzazioni, se necessario, ma per il resto un confronto ingenuo è O(L) dove L è la lunghezza delle parole.

È anche possibile cortocircuito leggendo il dizionario una volta che hai stabilito che si dispone di informazioni sufficienti circa l'alfabeto, ecc, ma anche un passo edificio ingenuo prendereste O(WL), che è la dimensione del dizionario.

Altri suggerimenti

Si vuole trovare un ordine totale di simboli.

1) È chiaramente può non può sempre stabilire un ordine totale.

2) È possibile utilizzare un diretto, grafico aciclico a rappresentare l'ordine parziale tra simboli. Ogni lettera è rappresentata una sola volta nel grafico. Si popolano essa, cercando in tutte le coppie di lettere nella stessa posizione in ogni coppia di parole consecutive. Eventuali cicli si creano nel punto del grafico di un errore nel dizionario. È appiattire insieme di relazioni come a-> d, a-> b, b-> D in a-> b-> d. Se quello che si ottiene alla fine è un grafico con una fonte (lettera senza precedenti) e un lavandino (lettera con successori), si dispone di un ordine totale, come l'alfabeto.

ho risolto questo con l'altro algoritmo suggerito in Wikipedia. Ecco l'psuedocodarlo da 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)

penso che offre un approccio più "buon senso" per la ricerca di un percorso (vale a dire come vorrei risolverlo se stavo guardando un grafico e deve trovare un percorso). Eppure, offre alcun vantaggio per l'approccio in profondità suggerita da polygenelubricants (se si aggiunge il codice di rilevamento ciclo come suggerito nei commenti) Grazie per i vostri commenti. risposte

Hai il dizionario in un array di parole e vi consiglio di utilizzare questa struttura dati, perché è abbastanza buono e una conversione richiede tempo.

Si vuole trovare il giusto ordine dei caratteri,

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

Hai il numero m di parole nel dizionario. Sarebbe eccellente per avere un insieme di regole, come (Ci, Cj), i quali mezzi quella CI <= Cj, dove i, j sono numeri naturali positivi e i

A causa V è un numero enorme e superiore è di oltre m * m, un approccio buono a mio parere sarebbe il seguente: 

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

Abbiamo trovato l numero di regole

ForEach i = 1, l fare     foreach j = i + 1, l do         se charSet.exists (Chari, charJ) e charSet.exists (charJ, Chari)             error.add ( "paradosso di relazione", Chari, charJ)

Dopo questo si può costruire l'ordine delle parole, considerando Chari = charJ è sia (Chari, charJ) e (charJ, Chari) esiste nel set e dove CHARI <= charJ è l'unica regola, non viceversa, si può considerare che Chari

Conclusione: Utilizzando il "<=" relazione è meglio che usare il "<" relazione, perché "<=" è una piena e buona ordinato relazione nella teoria dei numeri, "<" è solo buon ordinamento. NOTA: L'uscita deve mostrare correttamente se Chari

Spero che questo aiuta.

Naturalmente, se Wj contiene Wi allora non possiamo estrarre una regola da lì

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top