Google Interview Question: Can You Make This Lookup O(1)?

Tiny interval problem, three working approaches, and the memory bill hiding behind constant...