ISRO2018-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$

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