"What is the big O time of heap sort?" vs "Would you mind writing a function that returns true if any two numbers in the list sum to zero? For example, it would return false for [2,3,5] and true for [-3,5,3]"

Are completely different questions. The first is useless: It tests if someone remembers how a heap sort works, and whether or not they use the term "worst case" in the answer.

The second one is much better. Some could sort the list, (nlogn time, constant memory) then walk through it. They could use a hash table (idealy n time, assuming no collisions, but more memory). You also get to see if their solution handles the 0 case. If they answer it very quickly, you can move on to the three sum problem. If they recognize the question from university or something you can do a different one.

If someone doesn't know the big-O time of iterating through a list of integers once for every integer, then I seriously doubt their dedication to the field of software. This is not some pie in the sky doubt, it is of legitimate concern whether someone knows how to properly approach a problem of this nature with the right data structures, code, and communication.

Good interviewers put the interviewee at complete ease before they bring out the technical questions. From an economics point of view, it is better to hire the person that is in all other ways identical, yet interviews poorly, since they are less likely to want to leave.