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

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)的问题.如果你正在搜索"斑马",那么想想你的算法有多少次会向上扩展范围.

这是一个想法:通过假设每个单词的第一个字母均匀分布在字母表的字母中来使用集合的有序特性(这将永远不会成立,但是在不知道更多关于单词集合的情况下,它可能是你能做的最好).然后将您的范围扩展量加权到您希望词典单词结束的距离.

因此,如果你采取了100步的初始步骤并查找该索引处的字典单词并且它是"aardvark",那么下一步的扩展范围会比"海象"要大得多.仍然是O(log n),但对于大多数单词集合可能要好得多.

Answer 2

这是一个使用的替代实现Collections.binarySearch.如果列表中的一个单词以Character开头'\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因为集合中的binarySearch否则会在如此大的列表上使用基于迭代器的搜索,这将非常慢.然而,现在这应该是相当快的,因为即使List假装尽可能大,二进制搜索也只需要31次迭代.

这是一个稍微修改过的版本,可以记住最小的失败索引,将其声明的大小收敛到字典的实际大小,从而避免连续查找中的几乎所有异常.虽然只要字典的大小发生变化,您就需要创建一个新的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开始).

如果您要查找的单词"小于"当前字典单词,则将当前索引与"低"值之间的距离减半.(当然,"低"从0开始).

如果您要查找的单词"大于"您刚检查的索引处的单词,则将当前索引与"高"值之间的距离减半("高"从2开始)或者,如果索引和"高"是相同的,是指数的两倍.

如果索引加倍会使您超出范围异常,则将当前值与加倍值之间的距离减半.因此,如果从16到32引发异常,请尝试24.当然,要记录32超过最大值的事实.

所以搜索序列可能看起来像1,2,4,8,16,12,1 - 找到了!

它与二进制搜索的概念相同,但不是以low = 0,high = n-1开始,而是从low = 0,high = 2开始,并在需要时将高值加倍.它仍然是O(log N),尽管常量将比"普通"二进制搜索稍大一些.