Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2014 Set 3 · Q40
MCQ2 marksEasy
Time
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
Select one answerSingle correct
Pick an option to check
Solution
Step-by-step verified solution
Official answer: A) (97 × 97 × 97)/1003
Searching, Sorting and HashingUnder the assumption of simple uniform hashing, any given key is equally likely to hash into any of the 100 slots, independently of where any other key has hashed.
There are 100 total slots. For the first 3 slots to remain unfilled after an insertion, the key must be placed into any of the remaining slots.
For each insertion, the probability of choosing one of the other 97 slots is:
Since 3 independent insertions are performed, the joint probability that all 3 keys hash into the remaining 97 slots is:
Thus, option (A) is the correct answer.
Try the question first, then check your work.
Examiner trap
The misconception this question tests
Under simple uniform hashing, each of the 3 independent insertions must avoid the first 3 specific slots and choose from the remaining 97 slots.
This Searching, Sorting and Hashing previous year question is Q40 of the GATE CSE 2014 Set 3 paper. Find more GATE CSE PYQs on Searching, Sorting and Hashing in Algorithms, or browse all GATE CSE PYQs.
Free diagnostic
Where do you stand for GATE?
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Searching, Sorting and Hashing PYQs now with no account.
One GATE CSE PYQ every morning
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Searching, Sorting and Hashing in GATE CSE
Searching, Sorting and Hashing has 27 GATE CSE PYQs across 20 papers from 2012 to 2026. 7 of them are 2-mark MCQs like this one, and GATE CSE 2014 Set 3 has 3.
How GATE tests Searching, Sorting and HashingMore from GATE CSE 2014 Set 3
- Q42Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order. int ProcessArray(int *listA, int x, int…MCQ2 marksMedium
- Q38Consider the decision problem 2CNFSAT defined as follows: is a satisfiable propositional formula in CNF with at most two literals per clause For example, = (x1…MCQ2 marksMedium
- Q43An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory acce…NAT2 marksHard
- Q37Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a *shortcut*. A shortcut is simpl…NAT2 marksEasy
Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.