I was asked this in a recent interview.

Given a list of social security numbers, you are allowed to store only half of these numbers in memory(You can query the database to see if a number exists anytime). A person comes to you and asks for a new SSN. Write a program to assign a unique SSN to this person.