[tomsmeding]

Asking if the list is sorted was also the very first question that popped up in my head, because it makes the difference between a linear and a quadratic algorithm. Contrary to, for example, having the choice between an n log n algorithm and a linear algorithm, when given the choice between a quadratic and a linear algorithm, it is very rare that the right choice is the quadratic algorithm. (Semi-related: [1])

(EDIT: after thinking about this more than two seconds, the quadratic algorithm for unsorted input can become n log n by sorting the list, though that takes linear space. This would certainly be a clarifying question.)

The other questions would be less obvious to me, though I'd encounter them while thinking more than 2 seconds about the problem, I suppose.

Or maybe this just outs me as an ex-amateur competitive programmer :)

[1]: https://accidentallyquadratic.tumblr.com/

[yankjenets]

And if you had a magical oracle that spat out the two numbers if a solution exists, and otherwise told you no solution exists, you would have an O(1) solution.

Just because you can ask a question whose answer makes a drastic difference between the best algorithm involved, doesn't mean it is a good question.

(and note I said "_almost_ make me dock points...". And if the answer to the question was "yes, the list is sorted", I would _certainly_ dock points off of the interviewer/company if I were the interviewee for not giving that context).

[wetmore]

Fairly sure you can do it in linear time and space without sorting.