Skip to content
GATETECH
Official PYQ · 2014Set 3 · Q40Arrays, Stacks and QueuesMCQ1 mark

GATE CS 2014 Set 3 Q40 — Arrays, Stacks and Queues

Explain with AI

Consider a hash table with 100100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 33 slots are unfilled after the first 33 insertions?

Choose one option
View worked solution

Answer: A

Under the assumption of simple uniform hashing, each key is equally likely to hash to any of the 100100 slots, independently of where other keys are hashed.

We want to find the probability that the first 33 slots remain unfilled after 33 insertions. This means all 33 inserted keys must hash to any of the remaining 9797 slots (slots 44 to 100100).

  • For the 1st1^{\text{st}} insertion, the probability of landing in one of the 9797 allowed slots is 97100\frac{97}{100}.
  • For the 2nd2^{\text{nd}} insertion, the probability of landing in one of the 9797 allowed slots is 97100\frac{97}{100}.
  • For the 3rd3^{\text{rd}} insertion, the probability of landing in one of the 9797 allowed slots is 97100\frac{97}{100}.

Since the insertions are independent, the joint probability is the product of these individual probabilities:

P(first 3 slots unfilled)=97100×97100×97100=97×97×971003P(\text{first 3 slots unfilled}) = \frac{97}{100} \times \frac{97}{100} \times \frac{97}{100} = \frac{97 \times 97 \times 97}{100^3}

Therefore, the correct option is A.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Arrays, Stacks and Queues questions