Hashing Interview Question Part 1

1. A function that maps keys to integers, usually to get an even distribution on a smaller set of values is called ______
Ans: Hash function
2. A dictionary in which keys are mapped to array positions by hash functions is called
a.hash table
b.view table
c.Both
d.none
Ans:a
3.A hash function f defined as f(key) = key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,11,56,into a table indexed from 0 to 6. 11 will be stored in the location
a.3 b.4 c.5 d.6
Ans:c
f(37)=37 mod 7 =2.
So,37 will be put in location 2.f(38)=3.
So,38 will be in third location.
F(72)=2. This results in a collision. With linear probing as the collision resolving strategy, the alternate location for 72 will be the location 4. Continuing this way, the final configuration will be 98,56,37,38,72,11,48.
Hence the answer.

4. Having the keys of more than one item map to the same position is called a __________
Ans: collision.
5. A hash function that maps each different key to a distinct integer is called
a.perfect hashing
b.internal hashing
c.external hashing
d.none
Ans:a
6. Usually all possible keys must be known beforehand in perfect hashing.(T/F)
Ans:True
7. A hash table that uses a perfect hash has
a. 1 collision
b.no collisions
c.Multiple collisions
d.none
Ans:b
8.Perfect hashing is also called
a.optimal hashing
b.dynamic hashing
c.cuckoo hashing
d.none
Ans:a
9. A perfect hashing function that maps each different key to a distinct integer and has the same number of possible integers as keys is called
a.optimal hashing
b.dynamic hashing
c.minimal perfect hashing
d.none
Ans:c
10. A minimal perfect hashing function for keys in S such that if k1, k2 ∈ S and k1 > k2, then f(k1) > f(k2) is called ____
Ans:Order preserving minimal perfect hashing