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

Question

Несколько дней назад у меня было собеседование в какой-то крупной компании, имя не требуется :), и интервьюер попросил меня найти решение следующей задачи:

Предопределено: Естьсловарь слов с неопределенным размером , мы просто знаем, что все слова в словаре отсортированы (например, по алфавиту).Также у нас есть только один метод

String getWord(int index) throws IndexOutOfBoundsException

Требуется: Необходимо разработать алгоритм для поиска входного слова в словаре с использованием Java.Для этого мы должны реализовать метод

public boolean isWordInTheDictionary(String word)

Ограничения: Мы не можем изменить внутреннюю структуру словаря, у нас нет доступа к внутренней структуре, мы не знаем количества элементов в словаре.

Проблемы: Я разработал модифицированный двоичный поиск, и опубликует мой вариант (рабочий вариант) алгоритма, но есть ли другие варианты с логарифмической сложностью?Мой вариант имеет сложность O (logN).

Мой вариант осуществления:

public class Dictionary {
    private static final int BIGGEST_TOP_MASK = 0xF00000;
    private static final int LESS_TOP_MASK = 0x0F0000;
    private static final int FULL_MASK = 0xFFFFFF;
    private String[] data;
    private static final int STEP = 100; // for real test step should be Integer.MAX_VALUE
    private int shiftIndex = -1;
    private static final int LESS_MASK = 0x0000FF;
    private static final int BIG_MASK = 0x00FF00;


    public Dictionary() {
        data = getData();
    }

    String getWord(int index) throws IndexOutOfBoundsException {
        return data[index];
    }

    public String[] getData() {
        return new String[]{"a", "aaaa", "asss", "az", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "test", "u", "v", "w", "x", "y", "z"};
    }


    public boolean isWordInTheDictionary(String word) {
        boolean isFound = false;
        int constantIndex = STEP; // predefined step
        int flag = 0;
        int i = 0;
        while (true) {
            i++;
            if (flag == FULL_MASK) {
                System.out.println("Word is not found ... Steps " + i);
                break;
            }
            try {
                String data = getWord(constantIndex);
                if (null != data) {
                    int compareResult = word.compareTo(data);
                    if (compareResult > 0) {
                        if ((flag & LESS_MASK) == LESS_MASK) {
                            constantIndex = prepareIndex(false, constantIndex);
                            if (shiftIndex == 1)
                                flag |= BIGGEST_TOP_MASK;
                        } else {
                            constantIndex = constantIndex * 2;
                        }
                        flag |= BIG_MASK;

                    } else if (compareResult < 0) {
                        if ((flag & BIG_MASK) == BIG_MASK) {
                            constantIndex = prepareIndex(true, constantIndex);
                            if (shiftIndex == 1)
                                flag |= LESS_TOP_MASK;
                        } else {
                            constantIndex = constantIndex / 2;
                        }
                        flag |= LESS_MASK;
                    } else {
// YES!!! We found word.
                        isFound = true;
                        System.out.println("Steps " + i);
                        break;
                    }
                }
            } catch (IndexOutOfBoundsException e) {
                if (flag > 0) {
                    constantIndex = prepareIndex(true, constantIndex);
                    flag |= LESS_MASK;
                } else constantIndex = constantIndex / 2;
            }
        }
        return isFound;
    }

    private int prepareIndex(boolean isBiggest, int constantIndex) {
        shiftIndex = (int) Math.ceil(getIndex(shiftIndex == -1 ? constantIndex : shiftIndex));
        if (isBiggest)
            constantIndex = constantIndex - shiftIndex;
        else
            constantIndex = constantIndex + shiftIndex;
        return constantIndex;
    }

    private double getIndex(double constantIndex) {
        if (constantIndex <= 1)
            return 1;
        return constantIndex / 2;
    }
}

Answer 1

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

Как только вы нашли в словаре значение, которое больше, чем ваша цель поиска (или за ее пределами), остальное похоже на стандартный двоичный поиск. Сложная часть заключается в том, как оптимально расширить диапазон, если целевое значение больше значения словаря, которое вы искали. Похоже, вы расширяетесь в 1,5 раза. Это может быть действительно проблематично с огромным словарём и небольшим фиксированным начальным шагом, как у вас (100). Подумайте, если бы было 50 миллионов слов, сколько раз ваш алгоритм должен был бы расширить диапазон вверх, если вы ищете «зебра».

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

Итак, если вы сделали начальный шаг в 100 и посмотрели словарное слово по этому индексу, и это было «aardvark», вы бы расширили свой диапазон намного больше для следующего шага, чем если бы это был «морж». Все еще O (log n), но, вероятно, намного лучше для большинства наборов слов.

Answer 2

Вот альтернативная реализация, которая использует Collections.binarySearch. Сбой, если одно из слов в списке начинается с символа '\uffff' (то есть Unicode 0xffff и не является допустимым , не является допустимым символом Unicode ).

public static class ListProxy extends AbstractList<String> implements RandomAccess
{
    @Override public String get( int index )
    {
        try {
            return getWord( index );
        } catch( IndexOutOfBoundsException ex ) {
            return "\uffff";
        }
    }

    @Override public int size()
    {
        return Integer.MAX_VALUE;
    }
}

public static boolean isWordInTheDictionary( String word )
{
    return Collections.binarySearch( new ListProxy(), word ) >= 0;
}

Обновление: я изменил его так, чтобы он реализовал RandomAccess, так как в противном случае двоичный поиск в коллекциях использовал бы итераторный поиск в таком большом списке, который был бы чрезвычайно медленным. Однако теперь это должно быть прилично быстрым, поскольку для бинарного поиска потребуется всего 31 итерация, хотя список претендует на максимально большой размер.

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

public static class ListProxy extends AbstractList<String> implements RandomAccess
{
    private int size = Integer.MAX_VALUE;

    @Override public String get( int index )
    {
        try {
            if( index < size )
                return getWord( index );
        } catch( IndexOutOfBoundsException ex ) {
            size = index;
        }
        return "\uffff";
    }

    @Override public int size()
    {
        return size;
    }
}

private static ListProxy listProxy = new ListProxy();

public static boolean isWordInTheDictionary( String word )
{
    return Collections.binarySearch( listProxy , word ) >= 0;
}

Answer 3

У вас правильная идея, но я думаю, что ваша реализация слишком сложна.Вы хотите выполнить бинарный поиск, но не знаете, какова верхняя граница.Поэтому вместо того, чтобы начинать с середины, вы начинаете с индекса 1 (при условии, что словарные индексы начинаются с 0).

Если искомое слово «меньше» текущего словарного слова, уменьшите расстояние междутекущий индекс и ваше «низкое» значение.(«low» начинается с 0, конечно).

Если искомое слово «больше» чем слово в только что изученном вами индексе, то либо вдвое уменьшите расстояние между текущим индексом иваше «высокое» значение («высокое» начинается с 2) или, если индекс и «высокий» совпадают, удвойте индекс.

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

Так что последовательность поиска может выглядеть как 1, 2, 4, 8, 16, 12, 14 - найдено!

Это то же самое понятие, что и двоичный поиск, но вместо того, чтобы начинать с low = 0, high = n-1, вы начинаете с low = 0, high =2, и удвойте высокое значение, когда вам нужно.Это все равно O (log N), хотя константа будет немного больше, чем при «нормальном» двоичном поиске.

Answer 4

Вы можете понести единовременную стоимость O (n), если знаете, что словарь не изменится. Вы можете добавить все слова в словаре в хеш-таблицу, и тогда любые последующие вызовы isWordInDictionary () будут иметь значение O (1) (теоретически).

Answer 5

На другом языке:

#!/usr/bin/perl

$t=0;
$cur=1;
$under=0;
$EOL=int(rand(1000000))+1;
$TARGET=int(rand(1000000))+1;
if ($TARGET>$EOL)
{
  $x=$EOL;
  $EOL=$TARGET;
  $TARGET=$x;
}
print "Looking for $TARGET with EOL $EOL\n";

sub testWord($)
{
  my($a)=@_;
  ++$t;
 return 0 if ($a eq $TARGET);
 return -2 if ($a > $EOL);
 return 1 if ($a > $TARGET);
 return -1;
}

while ($r = testWord($cur))
{
  print "Tested $cur, got $r\n";
  if ($r == 1) { $over=$cur; }
  if ($r == -1) { $under=$cur; }
  if ($r == -2) { $over = $cur; }
  if ($over)
  {
    $cur = int(($over-$under)/2)+$under;
    $cur++ if ($cur <= $under);
    $cur-- if ($cur >= $over);
  }
  else
  {
    $cur *= 2;
  }
}
print "Found $TARGET at $r in $t tests\n";

Главное преимущество этого в том, что его немного проще понять. Я думаю, что это может быть более эффективно, если ваши первые догадки ниже цели, так как я не думаю, что вы пользуетесь пространством, которое вы уже «искали», но это просто с первого взгляда на ваш код. Поскольку он ищет цифры для простоты, ему не нужно иметь дело с поиском цели, но это простое расширение.

Answer 6

@ Сергей Загрийчук надеюсь, что интервью прошло хорошо.Удачи с этим.

Я думаю, как @alexcoco сказал, что Binary Search - это ответ.

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

Или, да, как говорят парни, полностью реализовать собственную структуру словаря.

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

Кстати, было бы неплохо увидеть ваш алгоритм.

РЕДАКТИРОВАТЬ: Расширение на мой комментарий под ответом bshields ...

@ Сергей Загрийчук, еще лучше было бы вспомнить последний индексгде у нас был ноль (нет слов), я думаю.Затем при каждом запуске вы можете проверить, все ли это правда.Если нет, тогда расширьте диапазон до «предыдущего индекса», полученного путем изменения поведения бинарного поиска, поэтому мы снова получим нулевое значение.Таким образом, вы всегда будете регулировать размер диапазона вашего алгоритма поиска, тем самым адаптируясь к текущему состоянию словаря по мере необходимости.Кроме того, изменения должны быть значительными, чтобы вызвать настройку диапазона, чтобы настройка не оказала реального негативного влияния на алгоритм.Также словари имеют тенденцию быть статичными по природе, поэтому это должно работать:)

Answer 7

Используйте API getWord () для копирования всего содержимого словаря в более разумную структуру данных (например, хеш-таблицу, trie, возможно, даже дополненную фильтром Блума).; -)

Answer 8

Я нахожусь в процессе найма, который задал мне эту же проблему ... Мой подход был немного другим, и, учитывая мой словарь (веб-сервис), он примерно на 30% эффективнее (для слов, которые я проверял).

Вот решение: https://github.com/gustavompo/wordfinder

Я не буду публиковать здесь полное решение, потому что оно отделено от классов и методов, но основной алгоритм таков:

public WordFindingResult FindWord(string word)
    {
        var callsCount = 0;
        var lowerLimit = new WordFindingLimit(0, null);
        var upperLimit = new WordFindingLimit(int.MaxValue, null);
        var wordToFind = new Word(word);
        var wordIndex = _initialIndex;

        while (callsCount <= _maximumCallsCount)
        {
            if (CouldNotFindWord(lowerLimit, upperLimit))
                return new WordFindingResult(callsCount, -1, string.Empty, WordFindingResult.ErrorCodes.NOT_FOUND);

            var wordFound = RetrieveWordAt(wordIndex);
            callsCount++;

            if (wordToFind.Equals(wordFound))
                return new WordFindingResult(callsCount, wordIndex, wordFound.OriginalWordString);

            else if (IsIndexTooHigh(wordToFind, wordFound))
            {
                upperLimit = new WordFindingLimit(wordIndex, wordFound);
                wordIndex = IndexConsideringTooHighPreviousResult(lowerLimit, wordIndex);
            }
            else
            {
                lowerLimit = new WordFindingLimit(wordIndex, wordFound);
                wordIndex = IndexConsideringTooLowPreviousResult(lowerLimit, upperLimit, wordToFind);
            }

        }
        return new WordFindingResult(callsCount, -1, string.Empty, WordFindingResult.ErrorCodes.CALLS_LIMIT_EXCEEDED);
    }

    private int IndexConsideringTooHighPreviousResult(WordFindingLimit maxLowerLimit, int current)
    {
        return BinarySearch(maxLowerLimit.Index, current);
    }

    private int IndexConsideringTooLowPreviousResult(WordFindingLimit maxLowerLimit, WordFindingLimit minUpperLimit, Word target)
    {
        if (AreLowerAndUpperLimitsDefined(maxLowerLimit, minUpperLimit))
            return BinarySearch(maxLowerLimit.Index, minUpperLimit.Index);

        var scoreByIndexPosition = maxLowerLimit.Index / maxLowerLimit.Word.Score;
        var indexOfTargetBasedInScore = (int)(target.Score * scoreByIndexPosition);
        return indexOfTargetBasedInScore;
    }

Answer 9

Предполагая, что словарь основан на 0, я бы разбил поиск на две части.

Во-первых, учитывая, что индекс параметра getWord () является целым числом, и предполагая, что индекс должен бытьчисло от 0 до максимального положительного целого числа, выполните бинарный поиск по этому диапазону, чтобы найти максимальный допустимый индекс (независимо от значений слова).Эта операция - O (log N), поскольку это простой двоичный поиск.

После получения размера словаря второй обычный двоичный поиск (опять же со сложностью O (log N)) приведет к желаемомуответ.

Поскольку O (log N) + O (log N) равно O (log N), этот алгоритм соответствует вашему требованию.

Answer 10

Вот мое решение .. использует O (logn) операции.Первая часть кода пытается найти оценку длины, а затем вторая часть использует тот факт, что словарь отсортирован и выполняет двоичный поиск.