The problem is that they still want that optimal solution in the 30 minutes given to you. There’s no point in thinking about it unless you already know what they are looking for.
Whoever thought up that alghorithm the first time certainly didn’t do it in 30 minutes during an interview.
This is only half true in my opinion. A lot of the interview questions I've gotten are pretty straightforward, for example given two lists of length M and N, brute force searching their product space is O(M*N), but if you sort one list the complexity reduces to O(NlogN + MlogN). I get the impression that the interviewer did expect me to sort, and writing code to do that was good enough.
On the other hand everyone shares stories about the really hard "gotcha" problems with clever optimal solutions. I've only been given one of those[0], and I did not come up with the optimal solution but I still passed the interview. I wrote a halfway solution that was better than bruteforce and I explained why any attempt I'd make to remove terms from the big O expression wouldn't work (obviously I could remove more if I was clever enough or given unlimited time).
So I would sum up my experience with they expect you to do better than brute force within 30 minutes, and to give them an intelligent conversation. I don't think this is easy, but it's not as impossible as you make it out to be.
[0] https://techdevguide.withgoogle.com/resources/former-intervi...
How fast are you going to come up with sorting one or two lists if you don’t already know this is an option?
If I ever run into a situation where I need to do it in real life, it takes me all of two seconds to find, so the only thing being tested is if I’ve ever done that before (and still remember).
Why would I not know this is an option? The word "sorting" appears in every single study guide I've seen. It's used as part of a solution in a large number of practice problems. I'm legitimately curious about what study materials you've used that leaves you uncomfortable with sorting.
EDIT: I might've misunderstood your question. When Amazon asked me this interview question, I'd never seen it before and didn't know beforehand what to do to solve it. I thought to try sorting a list within the first minute of working on it, because that's what you do with Leetcode style problems. I had prepared before the interview, so "let's try sorting" was not a stroke of brilliance it was a basic attempt to use a common tool.
There are many things which are easier for you but others take more time to do the same. This doesn't mean the person who does it within 30min is any better than the other who does the same in 2h.