GATE Overflow | Algorithms | Test 1 | Question: 21

Question

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).

• A. 80,000 B
• B. 160,000 B
• C. 320,000 B
• D. 150,000 B

Answer 1

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

Comments

how are you hashing the words? or seperate location for each word? and even if you use seperate location for each word ,why do you need to have a pointer  to actual data word? you just need to check if its properly hashed.

---

this question is quite confusing for me.

---

How to check if its properly hashed without using a pointer?

Answer 2

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