Not to rain on anyone's parade, but this looks like a bog-standard interview-style question. It wouldn't be unusual to ask a candidate to "invent" and implement

Not to rain on anyone's parade, but this looks like a bog-standard interview-style question. It wouldn't be unusual to ask a candidate to "invent" and implement both data structures in a 45 minute session. Not saying up this sort of thing makes for a good interview, just saying it's a cute little problem that has probably been solved a thousand times by a thousand different people.