Computer puzzles in job interviews

Yesterday, I went to a job interview. I was asked some difficult problems and ways to solve them. One of them was: We have a list of a million phone numbers on the standard input and we have a reduced memory pc which we want to use it to sort them and use to check later if any number given is in that list or not. The solution offered was to use an array of bits and use the number as an index, so if b[1234 ] == 0 would mean that the phone number 1234 wasn’t on the input list and 1 would mean that we had it.