646 views
3 votes
3 votes

A spell-checker software reads an input file and prints out all words not in some online dictionary. Suppose the dictionary contains 10,000 words and the file has one million entries, so that the algorithm can make only one pass through the input file. A simple strategy is to read the dictionary into a hash table and look for each input word as it is read. Assuming that an average word is seven characters and that it is possible to store words of length L in (L + 1) bytes (so space waste is not much of a consideration), and assuming a closed table, how much space does this require? (Assume a pointer is 8 bytes and that the hash table is an array of pointers to words).

  1. 80,000 B
  2. 160,000 B
  3. 320,000 B
  4. 150,000 B

2 Answers

Best answer
6 votes
6 votes
Size of pointer is 8 bytes and that the hash table is an array of pointers to words.
Word is seven characters and that it is possible to store words of length L in (L + 1) i.e. 7+1 = 8 byte for each word.

Size of Hash Table is 10,000 entries. Each entry size is 8 byte. Total size = 10,000*8 = 80,000
No of words is 10,000. Space required to store 10,000 word is 10,000*8 = 80.000

Total space required for dictionary and Hash Table = 80.000 + 80,000 = 1.60.000 Byte
selected by
0 votes
0 votes

hash table is an array of pointers to words

10000 cells. Each cell has an 8 B pointer.

=> 80,000 B

Each pointer points to a word. Each word is 8 B.

=> 80,000 B

Total = 160,000 B

Option B

Answer:

Related questions

3 votes
3 votes
2 answers
2
Bikram asked Oct 4, 2016
678 views
Is the following implementation of hashCode() legal assming a hashtable of size 20?public int hashCode(x) { return 17; }yesno because it fills only one slotno because it ...
2 votes
2 votes
2 answers
4
Bikram asked Oct 4, 2016
347 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___