Skip to content
Get started

Probes in a colliding hash table

You insert the keys 21, 31, 41, 15, 2521,\ 31,\ 41,\ 15,\ 25 in that order into an initially empty hash table of size 1010. The hash is h(k)=k mod 10h(k)=k \bmod 10, and collisions are resolved by linear probing (if a slot is taken, try the next slot to the right, wrapping around). Count a probe as each slot the insertion inspects, so landing in an empty home slot costs 11 probe. What is the total number of probes across all five insertions?

Show hints (2)+
  1. Three of the keys share home slot 11; two share slot 55. Simulate the table and watch each cluster grow.
  2. The home slot counts as probe 11; a run of kk colliding keys costs 1+2+⋯+k1+2+\cdots+k probes.

Answer

Reveal answer →

9

Create a free account to see the full worked solution and track your progress.

Interview format: Numerical Reasoning Tests, ETF Trading

Related questions