ISRO-DEC2017-50

Question

The characters of the string $\text{K R P C S N Y T J M}$ are inserted into a hash table of the size of size $10$ using a hash function
$h(x)=(ord(x)-ord(A)+1)$ $mod$ $10$

If linear probing is used to resolve collisions, then the following insertion causes the collision

• A. $Y$
• B. $C$
• C. $M$
• D. $P$

Comments

yes @srivivek95

h(x)=[ (ord(x)−ord(A)+1 ] mod 10

akash ord(x) means possition of x i.e. if A is 1 then C = 3

---

S=19??? right

---

yes...

Answer 1

$A \rightarrow 1$

$B \rightarrow 2$

$C \rightarrow 3$

$D \rightarrow 4$

$E \rightarrow 5$

$F \rightarrow 6$

$G \rightarrow 7$

$H \rightarrow 8$

$I \rightarrow 9$

$J \rightarrow 10$

$K \rightarrow 11$

$L \rightarrow 12$

$M \rightarrow 13$

$N \rightarrow 14$

$O \rightarrow 15$

$P \rightarrow 16$

$Q \rightarrow 17$

$R \rightarrow 18$

$S \rightarrow 19$

$T \rightarrow 20$

$U \rightarrow 21$

$V \rightarrow 22$

$W \rightarrow 23$

$X \rightarrow 24$

$Y\rightarrow 25$

$Z \rightarrow 26$

$h(x)= ( ( ord(x) - ord(A) ) + 1 ) \mod\ 10 $

$h(K)= ( ( ord(K) - ord(A) ) + 1 ) \mod\ 10  = ( (11 - 1 ) + 1) \mod\ 10 = 1$

$h(R)= ( ( ord(R) - ord(A) ) + 1 ) \mod\ 10  = ( (18 - 1 ) + 1) \mod\ 10 = 8$

$h(P)= ( ( ord(P) - ord(A) ) + 1 ) \mod\ 10  = ( (16 - 1 ) + 1) \mod\ 10 = 6$

$h(C)= ( ( ord(C) - ord(A) ) + 1 ) \mod\ 10  = ( (3 - 1 ) + 1) \mod\ 10 = 3$

$h(S)= ( ( ord(S) - ord(A) ) + 1 ) \mod\ 10  = ( (19 - 1 ) + 1) \mod\ 10 = 9$

$h(N)= ( ( ord(N) - ord(A) ) + 1 ) \mod\ 10  = ( (14 - 1 ) + 1) \mod\ 10 = 4$

$h(Y)= ( ( ord(Y) - ord(A) ) + 1 ) \mod\ 10  = ( (25 - 1 ) + 1) \mod\ 10 = 5$

$h(T)= ( ( ord(T) - ord(A) ) + 1 ) \mod\ 10  = ( (20 - 1 ) + 1) \mod\ 10 = 0$

$h(J)= ( ( ord(J) - ord(A) ) + 1 ) \mod\ 10  = ( (10 - 1 ) + 1) \mod\ 10 = 0$

$h(M)= ( ( ord(M) - ord(A) ) + 1 ) \mod\ 10  = ( (13 - 1 ) + 1) \mod\ 10 = 3$

0	T
1	K
2	J
3	C
4	N
5	Y
6	P
7	M
8	R
9	S

J and M are causing the collision

The ord() method returns an integer representing the Unicode code point of the given Unicode character in python.

# code point of integer
print(ord('5'))

# code point of alphabet 
print(ord('A'))

# code point of character
print(ord('$'))


output:
53
65
36

Comments

I think question is incomplete since mod 10 is not given in hash function

---

Yes, the question is incomplete

Answer 2

Hash function h(x) = ((ord(x) – ord(A) + 1)) %10

Given string is K R P C S N Y T J M. Take alphabetic ordering of each character is worth saving time to solve these questions. Therefore,

K will be inserted at index (11-1+1)%10 = 1

R at index (18-1+1) %10 = 8

P at index (16-1+1) % 10 = 6

C at index (3-1+1) % 10 = 3

S at index (19-1+1) % 10 = 9

N at index (14-1+1) % 10 = 4

Y at index (25-1+1) %10 = 5

T at index (20-1+1) % 10 = 0

J at index (10-1+1) %10 = 0 (Ist collision occurs, because 0th index is already filled by T).

M at index (13-1+1) % 10 = 3 (2nd collision occurs, because 3rd index is already filled by C).

Only J and M causes collision.

Final Hash table will be:

0	T
1	K
2	J
3	C
4	N
5	Y
6	P
7	M
8	R
9	S