14

A few days ago I had interview in some big company, name is not required :), and interviewer asked me to find solution to the next task:

Predefined: There is dictionary of words with unspecified size, we just know that all words in dictionary are sorted (for example by alphabet). Also we have just a one method

String getWord(int index) throws IndexOutOfBoundsException

Needs: Need to develop algorithm to find some input word in dictionary using java. For this we should implement method

public boolean isWordInTheDictionary(String word)

Limitations: We cannot change the internal structure of dictionary, we have no access to internal structure, we do not know counts of elements in dictionary.

Issues: I have developed modified-binary search, and will publish my variant(works variant) of algorithm, but are there another variants with logarithmic complexity? My variant has complexity O(logN).

My variant of implementation:

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;
    }
}
10
  • 12
    Binary search is probably one of the best ways to go
    – alexcoco
    May 27, 2011 at 19:12
  • 2
    Hmm? You say your variant has complexity O(logN) which is what a search in a sorted list should be, generally, and that the desired solution has "logarithmic complexity" (meaning, I assume O(logN). What are you looking for? May 27, 2011 at 19:13
  • 4
    Complain to the dictionary writer about their terrible API and get them to change it. O(1)
    – Jamie
    May 27, 2011 at 19:13
  • @Seth I am looking for another algorithm, because interviewer told me that my variant is good but there is another with the same complexity. May 27, 2011 at 19:18
  • 2
    @alexcoco Thanks :) I know that modified binary search it is good Idea and I have implemented it, but I am looking for another solution. May 27, 2011 at 19:22

12 Answers 12

9

It sounds like the part they really want you to think about is how to handle the fact that you don't know the size of the dictionary. I think they assume that you can give them a binary search. So the real question is how do you manipulate the range of the search as it progresses.

Once you have found a value in the dictionary that is greater than your search target (or out of bounds), the rest looks like standard binary search. The hard part is how do you optimally expand the range when the target value is greater than the dictionary value that you've looked up. It looks like you are expanding by a factor of 1.5. This could be really problematic with a huge dictionary and a small fixed initial step like you have (100). Think if there were 50 million words how many times your algorithm would have to expand the range upwards if you're searching for 'zebra'.

Here's an idea: use the ordered nature of the collection to your advantage by assuming the first letter of each word is evenly distributed amongst the letters of the alphabet (this will never be true, but without knowing more about the collection of words it's probably the best you can do). Then weight the amount of your range expansion by how far from the end you would expect the dictionary word to be.

So if you took your initial step of 100 and looked up the dictionary word at that index and it was 'aardvark', you would expand your range a lot more for the next step than if it was 'walrus.' Still O(log n) but probably much better for most collections of words.

4
  • I have described to my interviewer the same idea, thanks I think it will be worked, but I think it is hard to implement during 20 mins. Above Algorithm I have implemented during 20-25 mins. May 27, 2011 at 20:34
  • +1 this is very interesting idea indeed. @Sergii Zagriichuk I wonder can you actually assume anything about the state of the dictionary, i.e. that its size will not significantly change? If so then you could upgrade your algorithm that at its first run it would find the initialStep. Even using binary search for it and for example remember the first time you get something else then null(no word) as answer. Then you could either store it in a file or have it in memory, thus every consecutive call after the first one would be optimized.
    – Boro
    May 28, 2011 at 8:33
  • @Sergii Zagriichuk following on my comment above I expanded my thought in my answer, assuming we are always dealing with a dictionary of unknown size. Please do check and let me know what do you think about such approach. Is it in your opinion feasible/usable.
    – Boro
    May 28, 2011 at 8:54
  • 1
    This idea is Interpolation_search and yes it is still O(log n) and maybe better O(log(log n)), this link was put by Seth Robertson, Thanks him for it :), but implementation of this algorithm is quite hard. May 28, 2011 at 16:01
6

Here is an alternative implementation that uses Collections.binarySearch. It fails if one of the words in the list starts with the Character '\uffff' (that is Unicode 0xffff and not a legal not a valid unicode character).

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

Update: I modified it so that it implements RandomAccess since the binarySearch in Collections would otherwise use a iterator based search on such a large list which would be extremely slow. This should now however be decently fast since the binary search will need only 31 iterations even though the List pretends to be as large as possible.

Here is a slightly modified version that remembers the smallest failed index to converge its proclaimed size to the actual size of the dictionary en passant and thus avoids almost all exceptions in successive lookups. Although you would need to create a new ListProxy instance whenever the size of the dictionary could have changed.

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;
}
8
  • This is interested solution but I have tested it and it is not working. :(By the way, it is binary search, and I am looking for another solution, because binary search I have implemented. May 27, 2011 at 20:02
  • Can you tell me what is not working? I don't think there is something better than binary search for this problem, I just tried to provide a approach that is faster and easier to implement and potentially also faster.
    – x4u
    May 27, 2011 at 20:08
  • 1
    @x4u +1 for a very neat solution. I was thinking about actually reusing the default binarysearch but I didn't know that it could be so nice and easy. :) If I only could I would give you even +2 for this one :) Thanks for that it was stored for future. BTW what would your argument for not extending ArrayList (which already implements RandomAccess)?
    – Boro
    May 28, 2011 at 8:24
  • Yes, it was not worked first variant of your code, this variant is correct, and yes this is good solution, but, I think, the company cant accept solution like this, because the mandatory knows how to implement binary search or another algorithm. May 28, 2011 at 9:25
  • 1
    @Sergii Zagriichuk: Binary search is an interesting and important little algorithm that every developer should know and understand and also should have implemented a few times in his life, but it can be quite tricky to get it fast and robust. Jon Bentley discusses it in length in his book amazon.com/Programming-Pearls-2nd-Jon-Bentley/dp/0201657880 which is well worth its money. So when you don't need anything special I would always recommend to rely on a tested existing implementations even though the on in Collections is not as good as it could be but you will know that it works.
    – x4u
    May 28, 2011 at 12:30
5

You have the right idea, but I think your implementation is overly complicated. You want to do a binary search, but you don't know what the upper bound is. So instead of starting at the middle, you start at index 1 (assuming dictionary indexes start at 0).

If the word you're looking for is "less than" the current dictionary word, halve the distance between the current index and your "low" value. ("low" starts at 0, of course).

If the word you're looking for is "greater than" the word at the index you just examined, then either halve the distance between the current index and your "high" value ("high" starts at 2) or, if index and "high" are the same, double the index.

If doubling the index gives you an out of range exception, you halve the distance between the current value and the doubled value. So if going from 16 to 32 throws an exception, try 24. And, of course, keep track of the fact that 32 is more than the max.

So a search sequence might look like 1, 2, 4, 8, 16, 12, 14 - found!

It's the same concept as a binary search, but rather than starting with low = 0, high = n-1, you start with low = 0, high = 2, and double the high value when you need to. It's still O(log N), although the constant is going to be a bit larger than with a "normal" binary search.

4
  • 1
    Your approach is nice for very small lists but has a worse worst case than just assuming Integer.MAX_VALUE as the upper bound since it needs to step up and then down again which could be at most 61 iterations. with Integer.MAX_VALUE as the upper bound you need always 30 iterations on average regardless of the actual list size and the implementation becomes a bit easier.
    – x4u
    May 27, 2011 at 20:35
  • @x4u: I did state that it's going to be a bit slower. Worst case it'll be twice as slow. In practice it shouldn't be that bad because this approach will in general throw fewer exceptions because word dictionaries don't typically have hundreds of millions of entries. So, whereas the normal binary search requires fewer probes, many of those probes will throw exceptions, which are very expensive. May 27, 2011 at 20:55
  • I agree with you about the negative impact of the exceptions although if the list could be assumed to be static in size (it's not stated in the question) you could track the lowest failed index from previous runs to reduce the proclaimed list size rapidly and thus avoid most of the exceptions.
    – x4u
    May 27, 2011 at 21:07
  • Please take a look to my implementation, this implementation the same as you described, just started not from 1 but from 100. May 28, 2011 at 9:23
3

You can incur a one-time cost of O(n), if you know that the dictionary will not change. You can add all the words in the dictionary to a hashtable, and then any subsequent calls to isWordInDictionary() will be O(1) (in theory).

8
  • :) I cannot change internal state of dictionary, this was written in limitation, please take a look at it. May 27, 2011 at 19:31
  • 2
    Right, but if you know that the dictionary won't change, then you can do something like what I said, without needing to touch its internal state.
    – Jamie
    May 27, 2011 at 19:34
  • Yes, But I do not know it, I know just information that I've written. May 27, 2011 at 19:36
  • Hmm, fair enough. In that case I'm befuddled.
    – Jamie
    May 27, 2011 at 19:43
  • 1
    Though now that I think about it, we might be able to assume at least some things. It seems like that at least we know that the contents of the dictionary won't be modified at the same time as you're calling getWord; otherwise, bad things would probably happen. I'm not sure if one can then make an argument that the dictionary won't be mutable, but it seems somewhat plausible.
    – Jamie
    May 27, 2011 at 20:02
2

Use the getWord() API to copy the entire contents of the dictionary into a more sensible data structure (e.g. hash table, trie, perhaps even augmented by a Bloom filter). ;-)

3
  • 2
    And? We have complexity just to copy all words O(n), and + complexity to find word, it is not real answer and solution! May 27, 2011 at 19:29
  • It's not a real question either though, is it? An up-front copy of O(N) is fine if it saves time for large numbers of subsequent queries. But we don't know what the real requirements and constraints are because it's an interview question.
    – DNA
    May 28, 2011 at 15:38
  • Yes, But it is real question from real interview, Yes, I agree with you, that in real development we have to re-develop dictionary based on some better structure and use this structure to find word, and yes you are right for it, but I am asking about solution for interview question, not just to "real world" question and I have put description about it in subject, that this question from interview :) Cheers :). May 28, 2011 at 15:56
2

In a different language:

#!/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";

The main benefit of this one is it is a bit simpler to understand. I think it may be more efficient if your first guesses are below the target since I don't think you are taking advantage of the space you have already "searched", but that is just with a quick glance at your code. Since it is looking for numbers for simplicity, it doesn't have to deal with not finding the target, but that is an easy extension.

3
  • Thank you for implementation but it the same algorithm that I have implemented just using perl :) May 27, 2011 at 19:50
  • @Sergii Zagriichuk: Well, as I said I think it is more efficient, but yes it is a binary search. May 27, 2011 at 20:04
  • 1
    @Sergii Zagriichuk: The only other idea is to use interpolative search, assuming a random distribution (which we know English is not) to compute a probabilistic location point other than in the middle. en.wikipedia.org/wiki/Interpolation_search but that adds a fair bit of complexity and would need to be adjusted for the language you are searching in, adding even more. May 27, 2011 at 20:24
2

@Sergii Zagriichuk hope the interview went well. Good luck with that.

I think just as @alexcoco said Binary Search is the answer.

Other options I see are only available if you could extend the dictionary. You could make it slightly better. E.g. You could count the words on each letter, and keep their track this way you would effectively had to work only on a subset of words.

Or yea as guys are saying to entirely implement your own dictionary structure.

I know this doesn't answer you question properly. But I cannot see other possibilities.

BTW would be nice to see your algorithm.

EDIT: Expanding on my comment under answer of bshields...

@Sergii Zagriichuk even better it would be to remember the last index where we had null (no word), I think. Then at each run you could check if it is still true. If not then expand the range to a 'previous index' obtained by reversing the binary search behaviour, so we have null again. This way you would always adjust the size of the range of your search algorithm, thus adapting to the current state of the dictionary as needed. Plus the changes would have to be significant in order to cause your range adjustment so the adjustment wouldn't have any real negative impact on the algorithm. Also dictionaries tend to be static in nature so this should work :)

2
  • I have publish my implementation in first post, please take a look ... And thank you for your answer ... :) May 27, 2011 at 19:43
  • Yes, this solution of found size of dictionary I know, Thanks for explaining :) May 28, 2011 at 9:28
0

On one hand yes you are right with binary search implementation. But on the other hand in case dictionary is static and is not changed between lookups - we could suggest different algorithm. Here we have common problem - string sorting/search is different comparing to sorting/searching int array, so getWord(int i).compareTo(string) is O(min(length0, length1)).

Suppose we have request to find words w0, w1, ... wN, during lookup we could build up a tree with indicies (probably some suffix tree will good enough for this task). During next lookup request we have following set a1, a2, ... aM, so to decrease average time we could first decrease range by searching position in the tree. The problem with this implementation is concurrency and memory usage, so next step is implementing strategy to make search tree smaller.

PS: main aim was to check ideas and problems you suggest.

1
  • Your suggestion based on the static (not changeable) dictionary, but I had no this requirements and I cannot implement some search tree(but I have provided this solution to interviewer) May 30, 2011 at 12:35
0

Well i think the info that dictionary is sorted can be utilized in a better way. Say you are looking for a word "Zebra" , whereas the first guess search resulted in "abcg". So we can use this info in chossing the second guess index . like in my case the resulted word is starting with a , whereas i am looking for something starting with z. So rather than making a static jump , i can make some calculated jump based on the current result and desired result. So in this way suppose if my next jump takes me to the word "yvu" , i now i am very near , so i will make a rather slow small jump than in the prev case.

3
  • You have described (but not all details, just a a few things) of interpolation search, but this search will be worse in case you have all word started from Z compexity O(n), but my variant will be O(log n) in all cases. Jun 3, 2011 at 14:24
  • ummm ... i just put up a example case ... in case everything is starting from letter 'z' , yet there will be some delta between the data elements in start of the dictionary then once in last. So my point was to build up this sort of AI logic ... and yes it has to be persistent system as the last results will be helpfull in deciding current jump evalution.
    – mohit
    Jun 3, 2011 at 15:22
  • So, For it I should build some matrix of letter position or BST, but I cannot change internal state of dictionary, it was written in predefined section, if dictionary is static yes we can build once some structure not just like you wrote and it can be some hashtable or BST or RBT and use this structure to find word, but dictionary is not static! Jun 3, 2011 at 17:15
0

Here is my solution.. uses O(logn) operations. First part of the code tries to find a estimate of the length and then the second part takes advantage of the fact that the dictionary is sorted and performs a binary search.

boolean isWordInTheDictionary(String word){
    if (word == null){
        return false;
    }
    // estimate the length of the dictionary array
    long len=2;
    String temp= getWord(len);

    while(true){
        len = len * 2;
        try{
          temp = getWord(len);
        }catch(IndexOutOfBoundsException e){
           // found upped bound break from loop
           break;
        }
    }

    // Do a modified binary search using the estimated length
    long beg = 0 ;
    long end = len;
    String tempWrd;
    while(true){
        System.out.println(String.format("beg: %s, end=%s, (beg+end)/2=%s ", beg,end,(beg+end)/2));
        if(end - beg <= 1){
            return false;
        }
        long idx = (beg+end)/2;
        tempWrd = getWord(idx);
        if(tempWrd == null){
            end=idx;
            continue;
        }
        if ( word.compareTo(tempWrd) > 0){
            beg = idx;
        }
        else if(word.compareTo(tempWrd) < 0){
            end= idx;
        }else{
            // found the word..
            System.out.println(String.format("getword at index: %s, =%s", idx,getWord(idx)));
            return true;
        }
    }
}
2
  • Your solution is not working at all! And complexity is not equals to O(log N), it is higer. Aug 12, 2011 at 11:32
  • Why do you think this will not work? I have tested this code with a dictionary. the complexity is 2 * O(logn) which is O(logn)
    – SXS
    Oct 19, 2011 at 4:58
0

Assuming the dictionary is 0-based, I would decompose the search in two parts.

First, given that the index to parameter to getWord() is an integer, and assuming that the index must be a number between 0 and the maximum positive integer, perform a binary search over that range in order to find the maximum valid index (irrespective of the word values). This operation is O(log N), since is a simple binary search.

Once obtained the size of the dictionary, a second ordinary binary search (again of complexity O(log N)) will bring on the desired answer.

Since O(log N)+O(log N) is O(log N), this algorithm complies with your requirement.

0

I'm in a hiring proccess which asked me this same problem... My approach was a bit different, and considering the dictionary (webservice) I have, it's about 30% more efficient (for the words I've tested).

Here is the solution: https://github.com/gustavompo/wordfinder

I'll not post the whole solution here because it's decoupled through classes and methods, but the core algorithm is this:

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.