I started by explaining a hash table to store elements along with a list to maintain insertion order. This would allow for O(1) insertions and deletions.

I stumbled over a few details about handling duplicates, which threw me off a bit. The interviewer seemed to appreciate my thought process but pressed me further on edge cases.

I had to think on my feet, and I could feel my nerves creeping in, especially when it came to random access.