Databases
StackOverflow2013
Postsdbo
POFind word in dictionary of unknown size using only a method to get a word by index
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFind word in dictionary of unknown size using only a method to get a word by index
    primarykey
    data
    text
    <p>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:</p> <p><strong>Predefined:</strong> There is dictionary of words with <strong>unspecified size</strong>, we just know that all words in dictionary are sorted (for example by alphabet). Also we have just a one method </p> <pre><code>String getWord(int index) throws IndexOutOfBoundsException </code></pre> <p><strong>Needs:</strong> Need to develop algorithm to find some input word in dictionary using java. For this we should implement method </p> <pre><code>public boolean isWordInTheDictionary(String word) </code></pre> <p><strong>Limitations:</strong> We cannot change the internal structure of dictionary, we have no access to internal structure, we do not know counts of elements in dictionary.</p> <p><strong>Issues:</strong> I have developed modified-binary search, and <strong>will publish</strong> my variant(works variant) of algorithm, but are there another variants with logarithmic complexity? My variant has complexity O(logN).</p> <p>My variant of implementation:</p> <pre><code>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 &gt; 0) { if ((flag &amp; 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 &lt; 0) { if ((flag &amp; 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 &gt; 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 &lt;= 1) return 1; return constantIndex / 2; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USDukeling
    1. USSergii Zagriichuk
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. This table or related slice is empty.
      1. VTUpMod
    1. COBinary search is probably one of the best ways to go
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. USalexcoco
    2. COWhat's your question?
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. USMatt Ball
    3. COHmm? 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?
      singulars
      1. POFind word in dictionary of unknown size using only a method to get a word by index
      1. USSeth Robertson
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload