• Register
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
  • Questions
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Unanswered
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Tags
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Categories
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Users
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exams Taken
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580
  • Exam List
    Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 580

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

DSA - Graphs and Hashing -Q19


Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
+2 votes

A program that checks spelling works in the following way :  

A hash table has been defined in which each entry is a Boolean variable initialized to false.A hash function has been applied to each word in the dictionary, and the appropriate entry in the hash table has been set to true. To check the spelling in a document, the hash function is applied to every word in the document, and the appropriate entry in the hash table is examined. Which of the following is(are) correct?

I. true means the word was in the dictionary.

II. false means the word was not in the dictionary.

III. Hash table size should increase with document size.

(A) I only

(B) II only

(C) I and II only

(D) II and III only

asked Aug 3, 2020 by gbeditor-2 (72,840 points)
reshown Aug 6, 2020 by gbeditor-2

1 Answer

+1 vote
 
Best answer
I. true means the word was in the dictionary.

This is Not correct because True may not mean that word was in dictionary. Assume the scenario where a word w1 in the dictionary hashes to a slot m so we will set m to True. But now assume that another word w2 also hashes to slot m then we will again apply  hash  function and it will now hash to some slot n and slot n will be marked true. But observe that the word corresponding to slot n didn't make slot n true But some other word (w2) made slot n true. So, when the word corresponding to slot n comes in the document then it will hash to slot n and slot n, though is true, doesn't mean that the word was in dictionary.

II. false means the word was not in the dictionary.

This is true. Initially all entries are false and if after the hashing of all words in the hash table if still a slot is false then it means that the word was not in dictionary.

III. Hash table size should increase with document size.

Hash table size depends on the dictioanry, Not on document.
answered Aug 14, 2020 by deepak-gatebook (226,240 points)
Amazing explanation Deepak
Answer:

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177

Warning: count(): Parameter must be an array or an object that implements Countable in /home/customer/www/thegatebook.in/public_html/qa/qa-include/qa-theme-base.php on line 177
...