The hard thing about this problem is to neutralize the "random data" that can pass whatever error-checking you want to enforce. I don't remember all the detail

The hard thing about this problem is to neutralize the "random data" that can pass whatever error-checking you want to enforce. I don't remember all the details but the trick is (substantial hint) SPOILER SPOILER SPOILER to use indirection. Let the data at location i in the array not be the actual value but an index to another array that we continue to fill as we get new set() calls to previously unvisited places. When someone says set(i,v), we look at location i in the first array and see an index into the second. Suppose we can tell if the index is genuine (previously put there by us) or random junk; then everything's easy - when it's junk, allocate a new cell in the second array for the value and update the index. get() with default value also becomes easy. So the problem remains, how to tell random junk from a genuine index we stored before, and I've remembered the rest by now but I'd better stop here.