Given an array of integers, how would you remove all duplicates in linear time, i.e. O(n)?
Sigiloso
I now recognize this as a classic interview question, where the "correct" answer is to create an array of flags for every allowable value in the array, and then remove any value that already has its flag set. I think I made a mistake by trying to perform an analysis of the problem as I would if it were a real-world requirement. What I suspect the interviewer was looking for was to check a box when I gave the expected answer. I suspect that the real purpose of the question was not so much to test the applicants problem solving abilities, but to see if they had prepared for the interview well enough to know the "right" answer.