This was my immediate reaction. It is very easy and common for an interviewer to make a subtle change to how a common data structure or algorithm would work and then ask for complexity. Ex: Changing the quicksort pivot selection method.