Найдите самое длинное слово с учетом коллекции

Ответ 1

Нет кода Java. Вы можете понять это сами.

Предполагая, что нам нужно делать это много раз, вот что я сделал бы:

• Я бы начал с создания "подписей" для каждого слова в словаре, состоящего из 26 бит, где бит [буква] установлен, если слово содержит один (или более) экземпляр буквы. Эти сигнатуры могут быть закодированы как Java int.

• Затем создайте сопоставление, которое отображает подписи в списки слов с этой сигнатурой.

Чтобы выполнить поиск с использованием предварительно вычисленной карты:

• Создайте подпись для набора букв, которые вы хотите найти для слов.

• Затем итерации по клавишам отображения, ищущим ключи, где (key & (~signature) == 0). Это дает вам короткий список "Возможностей", которые не содержат буквы, которая не находится в требуемом наборе букв.

• Перейдем по короткому списку, ища слова с правильным номером каждой из требуемых букв, записывая самый длинный хит.

Примечания:

• В то время как основной поиск примерно O(N) по количеству слов в словаре, тест чрезвычайно дешев.

• Этот подход имеет то преимущество, что требуется относительно небольшая структура данных в памяти, которая (скорее всего) имеет хорошую локальность. Это, вероятно, будет способствовать ускоренному поиску.

Вот идея ускорения шага поиска O(N) выше.

Начиная с карты сигнатур выше, создайте (precompute) производные карты для всех слов, содержащих определенные пары букв; т.е. для слов, содержащих AB, для AC, BC,... и для YZ. Затем, если вы ищете слова, содержащие (скажем) P и Q, вы можете просто отсканировать карту производных PQ. Это уменьшит шаг O(N) примерно на 26^2... за счет увеличения объема памяти для дополнительных карт.

Это может быть увеличено до 3 или более букв, но недостатком является взрыв в использовании памяти.

Другая потенциальная настройка - (каким-то образом) смещение выбора пары начальных букв в сторону букв/пар, которые происходят нечасто. Но это добавляет авансовые накладные расходы, которые могут быть больше, чем (средняя), которую вы получаете от поиска более короткого списка.

Ответ 2

Я подозреваю, что реализация на основе Trie будет не очень эффективной с точки зрения пространства, но она будет очень хорошо распараллеливаться, потому что вы могли бы спуститься во все ветки дерева параллельно и собрать самые глубокие узлы, которые вы можете достичь от каждой вершины ветвь с заданным набором букв. В конце вы просто собираете все самые глубокие узлы и выбираете самый длинный.

Я бы начал с этого алгоритма (извините, просто псевдокод), который не пытается распараллелить, а просто использует обычную старую рекурсию (и обратную трассировку), чтобы найти самое длинное совпадение:

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;
}

т.е. эта функция должна начинаться с корня node trie, со всей данной коллекцией букв. Для каждой буквы в коллекции вы пытаетесь найти ребенка node. Если он есть, вы рекурсируете и удаляете письмо из коллекции. В какой-то момент ваша коллекция писем будет пуста (лучший случай, все письма потребляют - вы могли бы немедленно выручить сразу, не продолжая пересекать три), или детей больше не останется с остальными буквами - в этом случае вы удалите самой node, потому что это ваше "самое длинное совпадение".

Это можно было бы неплохо распараллелить, если вы изменили шаг рекурсии, чтобы вы одновременно посещали всех дочерних элементов, собирали результаты и выбирали самый длинный результат и возвращали это.

Ответ 3

Прежде всего, хороший вопрос. Интервьюер хочет посмотреть, как вы решаете проблему. В этих проблемах вам необходимо проанализировать проблему и тщательно выбрать структуру данных.

В этом случае мне приходят две структуры данных: HashMaps и Tries. HashMaps не подходят, потому что у вас нет полного ключа, который вы хотите найти (вы можете использовать инвертированный индекс на основе карт, но вы сказали, что уже нашли эти решения). У вас есть только те части, где Trie лучше всего подходит.

Таким образом, идея с попытками состоит в том, что вы можете игнорировать ветки символов, которые не находятся в вашем словаре при обходе дерева.

В вашем случае дерево выглядит следующим образом (я не учитывал ветвление для не ветвящихся путей):

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

Итак, на каждом уровне этого три, мы смотрим на детей текущего node и проверяем, является ли дочерний символ в нашем словаре.

Если да: мы идем глубже в это дерево и удаляем дочерний символ из нашего словаря

Это продолжается до тех пор, пока вы не нажмете лист (больше нет детей), здесь вы знаете, что это слово содержит все символы в этом словаре. Это возможный кандидат. Теперь мы хотим вернуться в дерево, пока не найдем другой матч, который мы можем сравнить. Если новейшее найденное совпадение меньше, отмените его, если дольше это наш возможный кандидат на лучший матч сейчас.

В какой-то день рекурсия закончится, и вы получите нужный результат.

Обратите внимание, что это работает, если есть одно длинное слово, иначе вам нужно будет вернуть список кандидатов (это неизвестная часть интервью, где вы должны спросить, что интервьюер хочет увидеть в качестве решения).

Итак, вам нужен код Java, здесь он имеет упрощенную Trie и одну длинную версию слова:

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 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);
  }

}

Я также могу только предложить прочитать книгу Cracking the Coding Interview: 150 вопросов и решений для программирования, он поможет вам в принятии решений и построении тех алгоритмов, которые специализируются на вопросах интервью.

Ответ 4

Отказ от ответственности: это не решение trie, но я все еще думаю, что это идея, которую стоит изучить.

Создайте некую хэш-функцию, которая учитывает только буквы в слове, а не их порядок (никаких столкновений не должно быть возможным, кроме как в случае перестановок). Например, ABCD и DCBA генерируют один и тот же хеш (но ABCDD нет). Создайте такую ​​хэш-таблицу, содержащую каждое слово в словаре, используя цепочку для связывания коллизий (с другой стороны, если у вас нет строгого требования найти "все" самые длинные слова, а не только одно, вы можете просто отказаться от столкновений, которые просто перестановки и отказаться от цепочки).

Теперь, если ваш набор поиска имеет длину 4 символа, например A, B, C, D, то в качестве поискового запроса вы проверяете следующие хэши, чтобы узнать, содержатся ли они в словаре:

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

Если вы ищете хэши в этом порядке, последнее совпадение, которое вы найдете, будет самым длинным.

Это заканчивается тем, что время выполнения зависит от длины набора поиска, а не от длины словаря. Если M - количество символов в наборе поиска, то число поисков хэшей - это сумма M choose 1 + M choose 2 + M choose 3 + ... + M choose M, которая также является размером набора параметров поиска, поэтому он O(2^M). На первый взгляд это звучит очень плохо, так как оно экспоненциально, но для того, чтобы помещать вещи в перспективу, если ваш набор поиска - это размер 10, будет всего около 1000 поисковых запросов, что, вероятно, намного меньше, чем ваш размер словаря в практическом реальном сценарии. В M = 15 мы получаем 32000 запросов, и действительно, сколько английских слов там длиннее 15 символов?

Есть два (альтернативных) способа, которые я могу придумать для его оптимизации:

1) Искать более длинные совпадения, например, M-комбинации, тогда (M-1) -комбинации и т.д. Как только вы найдете совпадение, вы можете остановиться! Скорее всего, вы будете покрывать лишь небольшую часть своего поискового пространства, возможно, в худшую половину.

2) Сначала найдите короткие совпадения (1-комбо, 2-комбо и т.д.). Скажем, вы придумали промах на уровне 2 (например, ни одна строка в вашем словаре не состоит только из A и B). Используйте вспомогательную структуру данных (возможно, битмап), которая позволяет вам проверить, действительно ли какое-либо слово в словаре частично состоит из A и B (в отличие от вашей основной хеш-таблицы, которая проверяет для композиции полная). Если вы получаете пропущенную информацию о вторичном растровом изображении, то вы знаете, что можете пропустить все комбинации более высокого уровня, включая A и B (т.е. вы можете пропустить hash(ABC), hash(ABD) и hash(ABCD), потому что нет слов содержат как A, так и B). Это использует принцип Apriori и резко сокращает пространство поиска, когда M растет, а промахи становятся более частыми. EDIT: Я понимаю, что детали, которые я абстрагирую, относящихся к "вспомогательной структуре данных", значительны. Поскольку я думаю больше об этой идее, я понимаю, что она склоняется к полному сканированию слова как подпроцедуре, которая поражает точку всего этого подхода. Тем не менее, похоже, что здесь следует использовать принцип Apriori.

Ответ 5

Я думаю, что вышеупомянутые ответы пропустили ключевой момент. У нас есть пространство с 27 размерами, первое - длина, а остальные - координаты каждой буквы. В этом пространстве есть точки, которые являются словами. Первой координатой слова является его длина. Другие координаты - для каждого буквенного измерения - количество вхождений этой буквы в это слово. Например, слова abacus, deltoid, gaff, giraffe, microphone, reef, qar, abcdefghijklmnopqrstuvwxyz имеют координаты

[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]

Хорошая структура для набора с координатами - R-tree или R * -Tree. Учитывая вашу коллекцию [x0, x1,..., x26], вы должны спросить все слова, содержащие не более буквы xi, для каждой буквы. Ваш поиск находится в O (log N), где N - количество слов в вашем словаре. Однако вы не хотите смотреть на самое большое слово во всех словах, соответствующих вашему запросу. Вот почему первое измерение важно.

Вы знаете, что длина самого большого слова находится между 0 и X, где X = sum (x_i, я = 1..26). Вы можете искать итеративно с X на 1, но вы также можете сделать алгоритм бинарного поиска для длины запроса. В качестве запроса используется первое измерение вашего массива. Вы начинаете с a = X до b = X/2. Если их по крайней мере совпадение, вы выполняете поиск от a до (a + b)/2, иначе вы выполняете поиск с b на b- (a-b)/2 = (3b-a)/2. Вы делаете это, пока не получите b-a = 1. Теперь у вас самая большая длина и все совпадения с этой длиной.

Этот алгоритм асимптотически намного эффективнее алгоритмов выше. Сложность времени в O (ln (N) × ln (X)). Реализация зависит от используемой библиотеки R-дерева.

Ответ 6

Groovy (почти 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()

Выбор типа коллекции для хранения словаря не имеет отношения к алгоритму. Если вы должны реализовать три, это одна вещь. В противном случае просто создайте один из соответствующей библиотеки для хранения данных. Ни Java, ни Groovy не имеют одной в своей стандартной библиотеке, о которой я знаю.

Ответ 7

Я попытался закодировать эту проблему на С++.. где я создал свой собственный хеш-ключ и прошел через все комбинации с заданными символами.

Прохождение всей комбинации этих входных символов с наибольшей длины до 1

Вот мое решение

#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 ;
            }
        }
    }
}

Ответ 8

Предполагая, что большой словарь и набор букв с менее чем 10 или 11 членами (например, данный пример), самый быстрый способ - построить дерево, содержащее возможные слова, которые могут сделать буквы, а затем сопоставить список слов с деревом, Другими словами, ваш корень дерева букв имеет семь подносов: {a, e, f, g, i, r, q}. Филиал "a" имеет шесть подносов {e, f, g, i, r, q} и т.д. Таким образом, дерево содержит все возможные слова, которые могут быть сделаны с этими буквами.

Пройдите через каждое слово в списке и сопоставьте его с деревом. Если совпадение является максимальной длиной (использует все буквы), все готово. Если слово меньше max, но дольше, чем любое предыдущее совпадающее слово, запомните его, это "самое длинное слово до сих пор" (LWSF). Игнорируйте любые слова, длина которых меньше LWSF. Также игнорируйте любые слова, длина которых превышает длину списка букв.

Это алгоритм линейного времени после построения дерева букв, так что, если список слов значительно больше, чем дерево букв, это самый быстрый метод.

Ответ 9

В первую очередь следует отметить, что вы можете полностью игнорировать порядок букв.

У вас есть trie (ну, вроде trie), как показано ниже:

• Из корня, у вас 26 детей (максимум), по одному для каждой буквы.
• От каждого не-root node есть дети, равные числу букв, больших или равных букве node.
• Храните все node все слова, которые могут быть сделаны с использованием (точно) букв в пути от корня.

Создайте trie следующим образом:

Для каждого слова сортируйте буквы этого слова и вставьте отсортированные буквы в trie (путем создания пути этих букв от корня), создавая все необходимые узлы по мере продвижения. И сохраните это слово в последнем node.

Как сделать поиск:

Для заданного набора букв найдите все подмножества букв (большинство из которых, надеюсь, не будут существовать) и выведите слова в каждом встреченном node.

Сложность:

O(k!), где k - количество прилагаемых букв. Ик! Но, к счастью, чем меньше слов есть в trie, тем меньше будет путей и тем меньше времени это займет. И k количество прилагаемых букв (которое должно быть относительно небольшим), а не количество слов в trie.

На самом деле это может быть больше в строках O(min(k!,n)), что выглядит намного лучше. Обратите внимание: если вам дано достаточно писем, вам придется искать все слова, поэтому вам нужно сделать O(n) работу в худшем случае, поэтому с точки зрения сложности наихудшего случая вы не можете много сделать лучше.

Пример:

Input:

aba
b
ad
da
la
ma

Сортировка:

aab
b
ad
ad
al
am

Trie: (только показывая непустых детей)

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

Поиск adb:

• Из корня...
• Перейти к дочернему a
  • Перейти к дочернему b
    • Нет детей, возвращение
  • Перейти к дочернему d
    • Выходные слова в node - ad и da
    • Нет детей, возвращение
  • Все обработанные письма, возврат
• Перейти к дочернему b
  • Выходные слова в node - b
  • Не ищет дочерний элемент a, так как существуют только дети >= b
  • Нет d child, return
• Нет d child, stop