I had not known this question before and I came up with hashing based implementation . The interviewer asked me to write it down, and once done he asked me for alternative implementations. I suggested two other methods all with O(n) extra space - but he wanted with O(1) extra space.