Seriously, in a phone interview? Anyways, I had done this problem on Leetcode, so was able to write code that passed interviewers test code. Before even hearing what I wanted to achieve with the code, The Genius, shoved his own idea. Initially he said, "more than optimized code, we are looking for correctness" (yeah, right!). O(1) for add function O(1) for lookup was expected. I did it using unordered_map, list and a pair to store position and value. I don't think there was any intent to hire, so got rejected the next day.