The questions was interesting, Designing a phone number regirstry with some functionality.

interface NumberRegistry {
   boolean isAdded(long phoneNumber);
   void add(long phoneNumber);  // register a given number
   void delete(long phoneNumber);
   long getRandomUnregisteredNumber(); // get a number which is not registered currently 
}

Interviewer didn't provided much info at the begining, I asked lot of questions.
For storage I proposed Hash base data structure, Hash Set. Proposed pre generated numbers for getting a random number. Initialy discusseed about use of a random number generatior(0-1 * max range), discussed some of the disadvanteges, like when most of the free slots in the range start and end is taken then it will take more time to find a random number which is not registered, also it will be a combination of generate_random_number() + check_if_registered + regenerate_if_already_registered

Then asked me to tackel that and any new ideas. Then I proposed range base number generation, We will have interval/max number per generation: The idea was to keep track of start and stop of last generation, then use the end of the last regeration to generate new numbers

Max numbers = n
Generation at T1: [start_t1, end_t1],  // end-start = n
Generation at T2: [end_t1+1, end_t1+1+n]

Numbers are sequential and increasing order, and it will regenerate when available number in current generation is less than 20% (20% of n). Interviewer focused another point that people may come and ask for desired number, if available the system should allow it. This will create problem with range base generation. Consider someone is asking for number 100, 100 is avaiable, but our current generation end is at 90, that means it will generate n number starting for 91, for n>10 will consider 100 as available and put in the pool of available number. Then I said we can do a check for each number in the generation process, will be using another Hash Set for storing currently generated numbers(avaiable). But it will be check for each number generation in the range, although we store in hash but hash comparison is also take some time. Then I proposed that we will keep track of the custom/user expected numbers in a list, And during the generation process I split the generation in smaller generation by spliting the generation range by the custom/user expected numbers. Lets say current generation range is

generation range: [1000, 2000]
user expected registered number: [1111, 1234,1235, 1516]  // keep it in priority queue/min-heap

Split the generation:
Generations: [1000,1110], [1112,1233], [1236, 1515], [1517-2000]
Generation is same as = [1000, 2000] - [1111, 1234,1235, 1516]

Didn't get much time to code fully as I dig a lot the corner cases, did wrote the isAdded, add, delete and generation process fully but can't complete get random number form the generation list.