I didn't know about approximate implementation using second chance or nth chance algorithm. I answered that it could be done in constant time using a hash table and a doubly linked list.