I suggested a combination of a hash map and a dynamic array. The hash map would store the elements and their indices in the array, allowing for O(1) access, while the array would support O(1) insertion and deletion by swapping elements when removing them. The interviewer seemed intrigued when I illustrated this with a quick code sketch. However, I stumbled a bit when asked how to handle duplicate values, which led to some back and forth that I felt could have been handled better.