在字典中查找未知大小的单词，仅使用一种按索引获取单词的方法

algorithm binary-search java

2022-09-03 18:20:15

前几天我在某大公司面试，名字不要求:)，面试官让我找到下一个任务的解决方案：

预定义：有一个单词的字典具有未指定的大小，我们只知道字典中的所有单词都是排序的（例如按字母顺序）。另外，我们只有一种方法

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

答案 1

听起来他们真正希望你考虑的部分是如何处理你不知道字典大小的事实。我认为他们假设你可以给他们一个二进制搜索。因此，真正的问题是，随着搜索的进行，您如何操纵搜索的范围。

一旦您在字典中找到大于搜索目标（或超出界限）的值，其余值看起来就像标准的二进制搜索。困难的部分是，当目标值大于查找的字典值时，如何以最佳方式扩展范围。看起来你正在扩张1.5倍。对于一个巨大的字典和一个像你一样的小型固定初始步骤（100），这可能真的有问题。想想看，如果有5000万个单词，如果你正在寻找“斑马”，你的算法必须将范围向上扩展多少倍。

这里有一个想法：通过假设每个单词的第一个字母均匀分布在字母表中，利用集合的有序性质来发挥你的优势（这永远不会是真的，但是如果不更多地了解单词的集合，它可能是你能做的最好的）。然后，根据您期望的字典单词距离终点的距离来加权范围扩展的量。

因此，如果您迈出了100的第一步，并在该索引处查找字典单词，它是“aardvark”，那么在下一步中，您将比“海象”更多地扩展您的范围。仍然是O（log n），但对于大多数单词集合来说可能要好得多。

答案 2

下面是使用的替代实现。如果列表中的某个单词以字符开头（即 Unicode 0xffff而不是合法且无效的 unicode 字符），则失败。Collections.binarySearch'\uffff'

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

更新：我修改了它，以便它实现，因为集合中的二进制搜索将使用基于迭代器的搜索，在如此大的列表上，这将非常慢。然而，现在这应该是相当快的，因为二进制搜索只需要31次迭代，即使列表假装尽可能大。RandomAccess

这是一个稍微修改过的版本，它记住最小的失败索引，将其声明的大小收敛到字典的实际大小，从而避免了连续查找中的几乎所有异常。尽管您需要在字典大小可能已更改时创建一个新的 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;
}