Given 400 million 32-bit integers, where each individual integer is repeated at most two time, how can you sort them?
This in an interview questions. I proposed using a counting table with 2^32 entries -- each possible value has an entry, and each entry takes 2 bits. One would just go through the integers and set bits in the corresponding entry as needed.
The interviewer further asked what if the set/clear-bit operation is really expensive, say, takes 1ms. I didn't have a great answer to that. I considered using 11 instead 10 to represent 2 -- so that when increasing the occurrence from 1 to 2, one only needs to set another bit instead of having to set one bit/clear one bit. That does not seem like the answer the interviewer is looking for.
Do you have a more efficient solution?