Recently I came cross an interview question where the ask was to store phone numbers in a data structure such that we would know:

1. which number is allocated or which is not
2. if a user asks for a phone number, we shold be able to allocate the phone number to the user if the number is available, if number is not available allocate any other phone number.

No need to maintain which phone number belongs to which user. Use minimum possible memory.

what will be the best memory efficient DS we can use in this scenerio?