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/
(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/