java - 仅使用一种通过索引获取单词的方法在未知大小的词典中查找单词

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)。想一想如果您要搜索“斑马”，如果有 5000 万个单词，您的算法必须将范围向上扩展多少次。

这里有一个想法:通过假设每个单词的第一个字母均匀分布在字母表中的字母中，利用集合的有序性质对您有利(这永远不会是真的，但在不了解更多关于单词集合的情况下这可能是你能做的最好的)。然后根据您期望的字典单词距离末尾的距离来衡量范围扩展的数量。

因此，如果您采取初始步骤 100 并在该索引处查找字典单词并且它是“aardvark”，那么与“海象”相比，您下一步的范围会扩大很多。仍然是 O(log n)，但对于大多数单词集合来说可能要好得多。