TAOCP 6.4 Exercise 29
Working
Exercise 29. [M21] [M21] (The parking problem.) A certain one-way street has m parking spaces in a row, numbered 1 through m. A man and his dozing wife drive by, and suddenly she wakes up and orders him to park immediately. He dutifully parks at the first available space; but if there are no places left that he can get to without backing up (that is, if his wife awoke when the car approached space k, but spaces k, k +1, ..., m are all full), he expresses his regrets and drives on.
Suppose, in fact, that this happens for n different cars, where the jth wife wakes up just in time to park at space a;. In how many of the sequences a1... an will all of the cars get safely parked, assuming that the street is initially empty and that nobody leaves after parking? For example, when m = n = 9 and ai...a9 = 314159265, the cars get parked as follows:
Ca o£ Ee Se SB Se SO Ee CE
[Hint: Use the analysis of linear probing.]
6.4 HASHING 553
Verified: no
Solve time: 47s
Working