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

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

Ну, я думаю, что информация, которую сортирует словарь, может быть использована лучше.Скажем, вы ищете слово «зебра», тогда как первый предположение поиска привело к «abcg».Таким образом, мы можем использовать эту информацию при выборе второго индекса догадки.как в моем случае, полученное слово начинается с a, тогда как я ищу что-то, начинающееся с z.Поэтому вместо того, чтобы делать статический скачок, я могу сделать некоторый вычисленный скачок, основанный на текущем результате и желаемом результате.Таким образом, предположим, что если мой следующий прыжок приведет меня к слову «yvu», я сейчас очень близко, поэтому я сделаю довольно медленный маленький прыжок, чем в предыдущем случае.

Answer 2

С одной стороны, да, вы правы в реализации бинарного поиска.Но, с другой стороны, в случае, если словарь является статическим и не изменяется между поисками - мы могли бы предложить другой алгоритм.Здесь мы сталкиваемся с общей проблемой - сортировка / поиск строк отличается от сортировки / поиска в массиве int, поэтому getWord (int i) .compareTo (string) равно O (min (length0, length1)).

Предположим, что мыУ нас есть запрос на поиск слов w0, w1, ... wN, во время поиска мы могли бы построить дерево с указателями (возможно, какое-то суффиксное дерево подойдет для этой задачи).Во время следующего поискового запроса у нас есть следующий набор a1, a2, ... aM, поэтому, чтобы уменьшить среднее время, мы могли бы сначала уменьшить диапазон путем поиска позиции в дереве.Проблема с этой реализацией заключается в параллелизме и использовании памяти, поэтому следующим шагом является реализация стратегии по уменьшению дерева поиска.

PS: основная цель состояла в том, чтобы проверить идеи и проблемы, которые вы предлагаете.