Project ForgeUsing the same hash table setup (length 10, h(k)=k mod 10, linear probing, final state slot2:42,slot3:23,slot4:34,slot5:52,slot6:46,slot7:33), how many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown?
Explanation
33 must be inserted last (its probe path requires slots 3,4,5,6 already full, i.e. 23,34,52,46 already present, and 52 itself requires 42,23,34 already present). Among the remaining 5 keys {42,23,34,52,46}: 52 must come after all of 42,23,34 (which can be ordered among themselves in 3!=6 ways, with 52 fixed right after them), while 46 has no ordering constraint and can be inserted into any of the 5 possible positions relative to that 4-element sequence. Total = 6 × 5 = 30 valid insertion sequences.
Source: GATE CS 2010 (2010)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.