In the quadratic probing hash table, suppose that instead of inserting a new item into the location suggested by findPos, we insert it into the ?rst inactive cell on the search path (thus, it is possible to reclaim a cell that is marked deleted, potentially saving space).
a. Rewrite the insertion algorithm to use this observation. Do this by having findPos maintain, with an additional variable, the location of the ?rst inactive cell it encounters.
b. Explain the circumstances under which the revised algorithm is faster than the original algorithm. Can it be slower?