java - sheet - Encuentra la palabra más larga dada a una colección

java algorithms interview questions

Question

Es una pregunta de la entrevista de Google y encuentro la mayoría de las respuestas en línea usando HashMap o una estructura de datos similar. Estoy tratando de encontrar una solución usando Trie si es posible. ¿Alguien podría darme algunas pistas?

Aquí está la pregunta: le dan un diccionario, en la forma de un archivo que contiene una palabra por línea. P.ej,

abacus 
deltoid 
gaff 
giraffe 
microphone 
reef 
qar 

También recibe una colección de letras. P.ej,

{a, e, f, f, g, i, r, q}. 

La tarea es encontrar la palabra más larga en el diccionario que se puede escribir con la colección de letras. Por ejemplo, la respuesta correcta para los valores de ejemplo anteriores es "jirafa". (Tenga en cuenta que "arrecife" no es una respuesta posible, porque el conjunto de letras contiene solo una "e").

La implementación Java sería preferida.

Answer 1

Creo que las respuestas anteriores omitieron el punto clave. Tenemos un espacio con 27 dimensiones, la primera es la longitud y las otras las coordenadas de cada letra. En ese espacio tenemos puntos, que son palabras. La primera coordenada de una palabra es su longitud. Las otras coordenadas son, para cada dimensión de letra es el número de ocurrencias de esa letra en esa palabra. Por ejemplo, las palabras abacus , deltoid , gaff , jirafa , micrófono , arrecife , qar , abcdefghijklmnopqrstuvwxyz tienen coordenadas

[3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[6, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]
[7, 0, 0, 0, 2, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[4, 1, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[7, 1, 0, 0, 0, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[4, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[26, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

La buena estructura para un conjunto con coordenadas es un R-tree R o un R-tree R * . Teniendo en cuenta su colección [x0, x1, ..., x26], debe solicitar todas las palabras que contengan como mucho xi letra, para cada letra. Su búsqueda está en O (log N), donde N es el número de palabras en su diccionario. Sin embargo, no desea ver la palabra más grande en todas las palabras que coinciden con su consulta. Esta es la razón por la cual la primera dimensión es importante.

Usted sabe que la longitud de la palabra más grande está entre 0 y X, donde X = suma (x_i, i = 1..26). Puede buscar iterativamente de X a 1, pero también puede hacer un algoritmo de búsqueda binaria para la longitud de la consulta. Usas la primera dimensión de tu matriz como consulta. Empiezas de a = X a b = X / 2. Si su coincidencia es al menos, busque de a a (a + b) / 2, de lo contrario busque de b a b- (ab) / 2 = (3b-a) / 2. Lo haces hasta que tengas ba = 1. Ahora tiene la mayor longitud y todas las coincidencias con esta longitud.

Este algoritmo es asintóticamente mucho más eficiente que los algoritmos anteriores. La complejidad del tiempo está en O (ln (N) × ln (X)). La implementación depende de la biblioteca R-tree que use.

Answer 2

Descargo de responsabilidad: esta no es una solución trie, pero sigo pensando que es una idea que vale la pena explorar.

Cree algún tipo de función hash que solo contabilice las letras de una palabra y no su orden (no debe haber colisiones, excepto en el caso de las permutaciones). Por ejemplo, ABCD y DCBA generan el mismo hash (pero ABCDD no). Genere una tabla hash que contenga cada palabra en el diccionario, usando encadenamiento para colisiones de enlaces (por otro lado, a menos que tenga un requisito estricto de encontrar "todas" las palabras más largas y no solo una, puede simplemente colgar las colisiones, que son solo permutaciones, y renunciar a todo el encadenamiento).

Ahora, si su conjunto de búsqueda tiene 4 caracteres, por ejemplo A, B, C, D , entonces, como búsqueda näive, verifique los siguientes hash para ver si ya están contenidos en el diccionario:

hash(A), hash(B), hash(C), hash(D) // 1-combinations
hash(AB), hash(AC), hash(AD), hash(BC), hash(BD), hash(CD) // 2-combinations
hash(ABC), hash(ABD), hash(ACD), hash(BCD) // 3-combinations
hash(ABCD) // 4-combinations

Si busca los hashes en ese orden, la última coincidencia que encuentre será la más larga.

Esto termina teniendo un tiempo de ejecución que depende de la longitud del conjunto de búsqueda en lugar de la longitud del diccionario. Si M es el número de caracteres en el conjunto de búsqueda, entonces el número de búsquedas de hash es la suma M choose 1 + M choose 2 + M choose 3 + ... + M choose M que también es el tamaño del conjunto de poder del conjunto de búsqueda, entonces es O(2^M) . A primera vista, esto suena realmente malo ya que es exponencial, pero para poner las cosas en perspectiva, si su conjunto de búsqueda es de tamaño 10, solo habrá alrededor de 1000 búsquedas, que probablemente sean mucho más pequeñas que el tamaño del diccionario en un escenario práctico del mundo real. En M = 15 obtenemos 32000 búsquedas, y realmente, ¿cuántas palabras en inglés hay más de 15 caracteres?

Sin embargo, hay dos formas (alternativas) en las que puedo pensar para optimizarlo:

1) Busque coincidencias más largas primero, p. Ej. Combinaciones M, luego combinaciones (M-1), etc. ¡Tan pronto como encuentre una coincidencia, puede parar! Lo más probable es que solo cubra una pequeña fracción de su espacio de búsqueda, probablemente en la mitad peor.

2) Busque coincidencias más cortas primero (1-combos, 2-combos, etc.). Digamos que se te ocurre una falla en el nivel 2 (por ejemplo, ninguna secuencia en tu diccionario está compuesta solo por A y B ). Use una estructura de datos auxiliares (quizás un mapa de bits) que le permita verificar si alguna palabra en el diccionario está compuesta parcialmente por A y B (a diferencia de su tabla hash primaria que verifica la composición completa ). Si también falla en el mapa de bits secundario, sabrá que puede omitir todas las combinaciones de nivel superior, incluidas A y B (es decir, puede omitir hash(ABC) , hash(ABD) y hash(ABCD) porque no contiene palabras. ambos A y B ). Esto aprovecha el principio Apriori y reduciría drásticamente el espacio de búsqueda a medida que M crece y los errores se vuelven más frecuentes. EDITAR: me doy cuenta de que los detalles que abstrae en relación con la "estructura de datos auxiliares" son significativos. A medida que pienso más en esta idea, me doy cuenta de que se está inclinando hacia un escaneo de diccionario completo como un subprocedimiento, lo que derrota el punto de todo este enfoque. Aún así, parece que debería haber una forma de usar el principio Apriori aquí.

Answer 3

Groovy (casi Java):

def letters = [''a'', ''e'', ''f'', ''f'', ''g'', ''i'', ''r'', ''q'']
def dictionary = [''abacus'', ''deltoid'', ''gaff'', ''giraffe'', ''microphone'', ''reef'', ''qar'']
println dictionary
    .findAll{ it.toList().intersect(letters).size() == it.size() }
    .sort{ -it.size() }.head()

La elección del tipo de colección para contener el diccionario es irrelevante para el algoritmo. Si se supone que debes implementar un trie, eso es una cosa. De lo contrario, solo crea uno de una biblioteca apropiada para contener los datos. Ni Java ni Groovy tienen uno en su librería estándar del que soy consciente.

Answer 4

Lo primero que debe observar es que puede ignorar por completo el orden de las letras.

Tenga un trie (bueno, una especie de trie) de la siguiente manera:

• Desde la raíz, tenga 26 hijos (máximo), uno para cada letra.
• De cada nodo que no sea raíz, los hijos tienen el mismo número de letras mayor o igual que la letra del nodo.
• Haga que cada nodo almacene todas las palabras que se pueden hacer usando (exactamente) las letras en la ruta desde la raíz.

Construye el trie así:

Para cada palabra, clasifique las letras de esta palabra e inserte las letras ordenadas en el trie (creando una ruta de estas letras desde la raíz), creando todos los nodos necesarios a medida que avanza. Y almacene la palabra en el nodo final.

Cómo hacer una búsqueda:

Para un conjunto dado de letras, busque todos los subconjuntos de letras (la mayoría de las cuales, afortunadamente, no existirán) y genere las palabras en cada nodo encontrado.

Complejidad:

O(k!) , Donde k es el número de letras suministradas. ¡Eek! Pero afortunadamente cuantas menos palabras haya en el trie, menos caminos existirán y menos tiempo tomará. Y k es el número de letras suministradas (que debería ser relativamente pequeño), no el número de palabras en el trie.

En realidad, puede ser más en la línea de O(min(k!,n)) , que se ve mucho mejor. Tenga en cuenta que si le dan suficientes letras, tendrá que buscar todas las palabras, por lo tanto, debe hacer O(n) en el peor de los casos, por lo que, en términos de la peor complejidad de caso, no puede hacer mucho mejor.

Ejemplo:

Entrada:

aba
b
ad
da
la
ma

Ordenado

aab
b
ad
ad
al
am

Trie: (solo muestra niños no nulos)

     root
     /  /
    a    b
 /-/|/-/
a b d l m
|
b

Búsqueda de adb :

• Desde la raíz ...
• Ir a a niño
  • Ir al niño b
    • Sin hijos, regreso
  • Ir al niño d
    • Palabras de salida en el nodo - ad y da
    • Sin hijos, regreso
  • Todas las letras procesadas, devuelven
• Ir al niño b
  • Palabras de salida en el nodo - b
  • No busca a hijo, ya que solo existen niños> = b
  • No d niño, regreso
• No d hijo, detente

Answer 5

Primero, buena pregunta. El entrevistador quiere ver cómo afrontas el problema. En ese tipo de problemas, debe analizar el problema y elegir cuidadosamente una estructura de datos.

En este caso, vienen a mi mente dos estructuras de datos: HashMaps y Tries . HashMaps no son una buena HashMaps , porque no tiene una clave completa que desea buscar (puede usar un índice invertido basado en mapas, pero dijo que ya encontró esas soluciones). Solo tienes las partes, es donde el Trie es el que mejor se adapta.

Entonces la idea con los intentos es que puedes ignorar ramas de caracteres que no están en tu diccionario mientras atraviesas el árbol.

En su caso, el árbol se ve así (dejé fuera de la bifurcación para rutas no ramificadas):

* a bacus d deltoid g a gaff i giraffe m microphone r reef q qar

Entonces, en cada nivel de este trie, observamos los elementos secundarios del nodo actual y verificamos si el carácter del niño está en nuestro diccionario.

En caso afirmativo: profundizamos en ese árbol y eliminamos el carácter del niño de nuestro diccionario

Esto continúa hasta que tocas una hoja (ya no hay niños), aquí sabes que esta palabra contiene todos los caracteres de este diccionario. Este es un posible candidato. Ahora queremos volver al árbol hasta que encontremos otra coincidencia que podamos comparar. Si el fósforo encontrado más nuevo es más pequeño, deséchelo, si es más largo éste es nuestro candidato posible del mejor partido ahora.

Algún día, la recisión terminará y terminarás con el resultado deseado.

Tenga en cuenta que esto funciona si hay una sola palabra más larga, de lo contrario tendría que devolver una lista de candidatos (esta es la parte desconocida de la entrevista en la que debe preguntar qué desea ver el entrevistador como solución).

Así que ha requerido el código Java, aquí está con una Trie simplista y la versión de una sola palabra más larga:

public class LongestWord {

  class TrieNode {
    char value;
    List<TrieNode> children = new ArrayList<>();
    String word;

    public TrieNode() {
    }

    public TrieNode(char val) {
      this.value = val;
    }

    public void add(char[] array) {
      add(array, 0);
    }

    public void add(char[] array, int offset) {
      for (TrieNode child : children) {
        if (child.value == array[offset]) {
          child.add(array, offset + 1);
          return;
        }
      }
      TrieNode trieNode = new TrieNode(array[offset]);
      children.add(trieNode);
      if (offset < array.length - 1) {
        trieNode.add(array, offset + 1);
      } else {
        trieNode.word = new String(array);
      }
    }    
  }

  private TrieNode root = new TrieNode();

  public LongestWord() {
    List<String> asList = Arrays.asList("abacus", "deltoid", "gaff", "giraffe",
        "microphone", "reef", "qar");
    for (String word : asList) {
      root.add(word.toCharArray());
    }
  }

  public String search(char[] cs) {
    return visit(root, cs);
  }

  public String visit(TrieNode n, char[] allowedCharacters) {
    String bestMatch = null;
    if (n.children.isEmpty()) {
      // base case, leaf of the trie, use as a candidate
      bestMatch = n.word;
    }

    for (TrieNode child : n.children) {
      if (contains(allowedCharacters, child.value)) {
        // remove this child''s value and descent into the trie
        String result = visit(child, remove(allowedCharacters, child.value));
        // if the result wasn''t null, check length and set
        if (bestMatch == null || result != null
            && bestMatch.length() < result.length()) {
          bestMatch = result;
        }
      }
    }
    // always return the best known match thus far
    return bestMatch;
  }

  private char[] remove(char[] allowedCharacters, char value) {
    char[] newDict = new char[allowedCharacters.length - 1];
    int index = 0;
    for (char x : allowedCharacters) {
      if (x != value) {
        newDict[index++] = x;
      } else {
        // we removed the first hit, now copy the rest
        break;
      }
    }
    System.arraycopy(allowedCharacters, index + 1, newDict, index,
        allowedCharacters.length - (index + 1));

    return newDict;
  }

  private boolean contains(char[] allowedCharacters, char value) {
    for (char x : allowedCharacters) {
      if (value == x) {
        return true;
      }
    }
    return false;
  }

  public static void main(String[] args) {
    LongestWord lw = new LongestWord();
    String longestWord = lw.search(new char[] { ''a'', ''e'', ''f'', ''f'', ''g'', ''i'',
        ''r'', ''q'' });
    // yields giraffe
    System.out.println(longestWord);
  }

}

También solo puedo sugerir leer el libro Cracking the Coding Interview: 150 Programming Questions and Solutions , que lo guía a través de la toma de decisiones y la construcción de los algoritmos especializados en preguntas de la entrevista.

Answer 6

Sin código Java Puedes descubrirlo por ti mismo.

Suponiendo que tenemos que hacer esto muchas veces, esto es lo que haría:

• Comenzaría creando "firmas" para cada palabra en el diccionario que consta de 26 bits, donde bit [letter] se establece si la palabra contiene una (o más) instancias de la letra. Estas firmas se pueden codificar como Java int .

• Luego, cree un mapeo que asigne las firmas a listas de palabras con esa firma.

Para hacer una búsqueda usando el mapa precalculado:

• Crea la firma para el conjunto de letras para las que quieres encontrar las palabras.

• Luego itere sobre las teclas del mapeo buscando claves donde (key & (~signature) == 0) . Eso le da una breve lista de "posibles" que no contienen ninguna letra que no esté en el conjunto de letras requerido.

• Itere sobre la lista corta buscando palabras con el número correcto de cada una de las letras requeridas, registrando el golpe más largo.

Notas:

1. Mientras que la búsqueda principal es aproximadamente O(N) en el número de palabras en el diccionario, la prueba es extremadamente barata.

2. Este enfoque tiene la ventaja de requerir una estructura de datos en memoria relativamente pequeña, que (lo más probable) tiene una buena localidad. Es probable que conduzca a búsquedas más rápidas.

Aquí hay una idea para acelerar el paso de búsqueda O(N) anterior.

Comenzando con el mapa de la firma anterior, cree mapas preferenciales para todas las palabras que contengan pares de letras específicas; es decir, uno para las palabras que contienen AB, para AC, BC, ... y para YZ. Luego, si busca palabras que contengan (digamos) P y Q, puede escanear el mapa derivado de PQ. Eso reducirá el paso O(N) en aproximadamente 26^2 ... a costa de más memoria para los mapas adicionales.

Eso se puede extender a 3 o más letras, pero la desventaja es la explosión en el uso de la memoria.

Otra modificación potencial es (de alguna manera) sesgar la selección del par inicial de letras hacia letras / pares que ocurren con poca frecuencia. Pero eso agrega una sobrecarga inicial que podría ser mayor que el ahorro (promedio) que obtiene al buscar una lista más corta.

Answer 7

Sospecho que una implementación basada en Trie no sería muy eficiente en el uso del espacio, pero se paralelizaría muy bien, porque podrías descender en todas las ramas del árbol en paralelo y recoger los nodos más profundos a los que puedes llegar desde cada rama superior con el dado conjunto de letras. Al final, solo recogerá todos los nodos más profundos y seleccionará el más largo.

Comenzaría con este algoritmo (lo siento, solo pseudocódigo), que no intenta paralelizar, sino que simplemente usa la recursión antigua simple (y el retroceso) para encontrar la coincidencia más larga:

TrieNode visitNode( TrieNode n, LetterCollection c )
{
    TreeNode deepestNode = n;
    for each Letter l in c:
        TrieNode childNode = n.getChildFor( l );

        if childNode:
            TreeNode deepestSubNode = visitNode( childNode, c.without( l ) );
            if deepestSubNode.stringLength > deepestNode.stringLength:
                deepestNode = deepestSubNode;
   return deepestNode;
}

Es decir, se supone que esta función debe comenzar en el nodo raíz del trie, con toda la colección de letras dada. Para cada letra de la colección, intenta buscar un nodo secundario. Si hay uno, recurse y elimine la carta de la colección. En un momento su colección de cartas estará vacía (en el mejor de los casos, todas las letras se consumen; en realidad podría rescatar de inmediato sin continuar atravesando el trie) o no habrá más niños con ninguna de las letras restantes, en ese caso usted eliminará el nodo en sí, porque esa es su "combinación más larga".

Esto podría paralelizar muy bien si cambió el paso de recursión para que visite a todos los niños en paralelo, recopile los resultados y seleccione el resultado más largo y lo devuelva.

Answer 8

Suponiendo que un diccionario grande y una letra se establecen con menos de 10 u 11 miembros (como el ejemplo dado), el método más rápido es construir un árbol que contenga las posibles palabras que las letras pueden hacer, luego hacer coincidir la lista de palabras con el árbol. En otras palabras, la raíz de su árbol de letras tiene siete subnodos: {a, e, f, g, i, r, q}. La rama de "a" tiene seis subnodos {e, f, g, i, r, q}, etc. El árbol contiene todas las palabras posibles que se pueden hacer con estas letras.

Repase cada palabra de la lista y compárela con el árbol. Si la coincidencia es de longitud máxima (usa todas las letras), ha terminado. Si la palabra es menor que la máxima, pero más larga que cualquier palabra coincidente previamente, recuérdelo, esta es la "palabra más larga hasta el momento" (LWSF). Ignore cualquier palabra que tenga una longitud igual a menos que el LWSF. Además, ignore cualquier palabra que sea más larga que la longitud de la lista de letras.

Este es un algoritmo de tiempo lineal una vez que se construye el árbol de letras, por lo que siempre que la lista de palabras sea significativamente más grande que el árbol de letras, es el método más rápido.

Answer 9

Traté de codificar este problema en C ++ ... donde creé mi propia clave hash y revisé toda la combinación con los caracteres dados.

Pasando por toda la combinación de estos caracteres de entrada de la longitud más grande a 1

Aquí está mi solución

#include "iostream"
#include <string>

using namespace std;

int hash_f(string s){
        int key=0;
        for(unsigned int i=0;i<s.size();i++){
           key += s[i];
        }
        return key;
}

class collection{

int key[100];
string str[10000];

public: 
collection(){
    str[hash_f( "abacus")] = "abacus"; 
    str[hash_f( "deltoid")] = "deltoid"; 
    str[hash_f( "gaff")] = "gaff"; 
    str[hash_f( "giraffe")] = "giraffe"; 
    str[hash_f( "microphone")] = "microphone"; 
    str[hash_f( "reef")] = "reef"; 
    str[hash_f( "qar")] = "qar"; 
}

string  find(int _key){
    return str[_key];
}
};

string sub_str(string s,int* indexes,int n ){
    char c[20];
    int i=0;
    for(;i<n;i++){
        c[i] = s[indexes[i]];
    }
    c[i] = 0;
    return string(c);
}

string* combination_m_n(string str , int m,int n , int& num){

    string* result = new string[100];
    int index = 0;

    int * indexes = (int*)malloc(sizeof(int)*n);

    for(int i=0;i<n;i++){
        indexes[i] = i; 
    }

    while(1){
            result[index++] = sub_str(str , indexes,n);
            bool reset = true;
            for(int i=n-1;i>0;i--)
            {
                if( ((i==n-1)&&indexes[i]<m-1) ||  (indexes[i]<indexes[i+1]-1))
                {
                    indexes[i]++;
                    for(int j=i+1;j<n;j++) 
                        indexes[j] = indexes[j-1] + 1;
                    reset = false;
                    break;
                }
            }
            if(reset){
                indexes[0]++;
                if(indexes[0] + n > m) 
                    break;
                for(int i=1;i<n;i++)
                    indexes[i] = indexes[0]+i;
            }
    }
    num = index;
    return result;
}


int main(int argc, char* argv[])
{
    string str = "aeffgirq";
    string* r;
    int num;

    collection c;
    for(int i=8;i>0;i--){
        r = combination_m_n(str, str.size(),i ,num);
        for(int i=0;i<num;i++){
            int key = hash_f(r[i]);
             string temp = c.find(key);
            if(  temp != "" ){
                  cout << temp ;
            }
        }
    }
}