Doubts in mcq questions

#1

Q4. Number Of Collision
If ‘h’ is the hashing function and is used to hash n keys into a table of size s, where n<=s, the expected number of collision involving a particular key X is

less than n/2

less than s

less than n

less than 1

#2

Q7. Remove Characters From A String Give the space complexity for removing the specified characters in a string which are given in another string using the concept of Hashing (Consider the length of both strings to be n) O(n) O(logN) O(1)

#3

Q10. Guess the location Consider a hash table of size m = 10000, and the hash function h(K) = floor (m(KA mod 1)) for A = ( √(5) – 1)/2. The key 123456 is mapped to location . 45 41 43 48

#4

@Akshita99
Q4
Ans. Option A - less than 1.
This is a theorem in Universal Hashing -
"If h is chosen from a universal collection of hash functions and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1.
Q10
Given hash function: h(K) = floor (m (K*A mod 1))
where A = ( √(5) – 1)/2
h(123456) = floor(10000 * (123456 * (√5 − 1) / 2) mod 1)
= floor(10000 * (76300.004115 mod 1)
= floor(10000 * (.004115))
= 41.15
= 41
So, option (B) is correct.
also whats the answer for Q7 given?

#5

for Q7 the answer given is O(1)

#6

it shouldn’t be o(1) as using hashing o(n) space will be used

#7

so the answer given is wrong?

#8

@Akshita99 yes i will report to the team to get this fixed