1.

Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?(a) All keys hash to same index(b) All keys hash to different indices(c) All keys hash to an even-numbered index(d) All keys hash to different even-numbered indicesThe question was posed to me in an internship interview.I'd like to ask this question from Hashing techniques topic in division Indexing and Hashing of Database Management

Answer»

The correct choice is (a) All KEYS hash to same index

Easiest EXPLANATION - If all keys hash to the same location then the i-th inserted KEY WOULD need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you KNOW some probability it’s trivial to show that such lookups have linear time.



Discussion

No Comment Found

Related InterviewSolutions