The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
1.8k views

A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ values into an empty hash table, the table is shown as below

$0$  
$1$  
$2$ $42$
$3$ $23$
$4$ $34$
$5$ $52$
$6$ $46$
$7$ $33$
$8$  
$9$  
   
   

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

  1. $46, 42, 34, 52, 23, 33$
  2. $34, 42, 23, 52, 33, 46$
  3. $46, 34, 42, 23, 52, 33$
  4. $42, 46, 33, 23, 34, 52$
asked in DS by Veteran (101k points)
retagged by | 1.8k views
+1

A)  46, 42, 34, 52, 23, 33

now...46,42,34....will be inserted without any problem...but 52 creates problem..if we use this sequence then 52 will check and it find 42  there in 3rd slot so ..there is collission so it will look for next slot..which empty...so 52 will be placed..in slot no.-3...so we won't get above table..for this sequence..

B)34, 42, 23, 52, 33, 46

34,42,23,52..will be placed without any problem...but 33 creates problem..if we use this sequence then 33 will check  .there is collission so it will look for next slot -3..which filled with 23 then next slot-4 which is also filled with 34...then next slot-5 which is also filled with 52..then next slot-6 which is free so..33 will be placed in 6..slot..which not the right input..coz in 6 slot..46 need to be placed..

D)42, 46, 33, 23, 34, 52

42,46, will be placed without any problem..33 creates problem...slot 3 is free and 33 will be placed in it..but in table in 3rd slot..23 is dere so..it is also wrong..

C)...it will b placed without ..any problem..

+1
thank u so much @tauhin_gangwar i understood now :)

3 Answers

+15 votes
Best answer

Option (C)

$46, 34, 42, 23, 52, 33$

$46 -$ position $6$

$34$ position $4$

$42$ position $2$

$23$ position $3$

$52$ position $2 -$ collision next empty is $5$

$33$ position $3 -$ collision next empty is $7$

answered by Boss (11.5k points)
edited by
+11 votes

answer = option C : solve by checking each option

answered by Boss (30.8k points)
0 votes
taking each option and drawing hash table is not fastest approach

option elimination will be correct approach here

by looking at given hash table we draw following conclusion

1) 52 must come after 42 , hence sequence is 42 , 52

2)33 must come after 33 hence sequence is 23 ,33

3)52 must come after 23 & 34 . note that order between 23 and 34 does not matter

4)33 must come after 34 52 & 46 note that order between this three number does not matter

now check each option , you will find c is correct
answered by Active (1.8k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,823 comments
57,593 users