ISRO CSE 2018 | Question: 36

Question

A hash table with $10$ buckets with one slot pet per bucket is depicted here. The symbols, $S1$ to $S7$ are initially entered using a hashing function with linear probing. The maximum number of comparisons needed in searching an item that is not present is

$$\begin{array}{|c|c|} \hline 0 & S7 \\ \hline 1 & S1 \\ \hline 2 &  \\ \hline 3 & S4 \\ \hline 4 & S2 \\ \hline 5 &  \\ \hline 6 & S5 \\\hline 7 &  \\ \hline 8 & S6 \\\hline 9 & S3 \\ \hline \end{array}$$

• A. $4$
• B. $5$
• C. $6$
• D. $3$

Comments

Maximum denotes the worst case

 

Answer 1

Ans is 5.Because in worst case we have to probe index 8,9,0,1 and 2 as they are contiguously filled.

Comments

But using formula for unsuccessful search in linear probing given as:
$Unsuccessful\ search=\frac{1}{2}(1+\frac{1}{(1-LF)^2})$

Where LF is the loading factor given as $\frac{7}{10}$ in this question.

We are getting unsuccessful search as $\frac{1}{2}(1+\frac{1}{0.09})\rightarrow\frac{1}{2}(\frac{109}{9})=6.055$

Source http://www.cs.tau.ac.il/~zwick/Adv-Alg-2015/Linear-Probing.pdf

Answer 2

Plz Refer here: https://gateoverflow.in/10905/gate1989-1-vii-isro2015-14

Comments

And refer to the most upvoted answer which is selected as Best answer.

Answer 3

Contiguous sequences of filled buckets:

• Sequence 0,1 (2 buckets)
• Sequence 3,4,6,8,9(5 buckets). 

• Empty buckets terminate searches:

  • The empty buckets 2,5 and 7 stop the search when encountered.

• By the worst case, I mean that if buckets 3,4,6,8,9 are sequentially filled and you are searching for a key that is not present, you will have to check all these buckets one by one before encountering an empty bucket (or cycling back to the start if no empty bucket is encountered).

  This sequential traversal would result in 5 comparisons in the worst case.

• Another way

• If buckets 3,4,6,8,9 are sequentially full, the worst-case number of comparisons for an unsuccessful search is 5. This is because the search will continue through the entire sequence before stopping.

Comments

i think it's not correct. we can max. search for 8,9,0,1,2 bcoz they are linearly or sequentially filled. and only possible when some key goes to 8 then we sequentially search for next loc. where it can be present but when we last compare with loc. 2 where no element present, then we can ensure that it's not present in the whole table. bcoz if loc. 2 is empty and if it was present then it must present in that exact loc. tell if i am wrong?