Most challenging algo interviews (onsite) are really about "solve it by hook or by crook" regardless of efficiency. (Usually there isn't, but if there's an obvious brute-force solution it gives you no credit anyway.)
In the toughest algo questions, usually there's no memory capacity issue to worry about.
Occasionally, interviewer stipulates O(N logN) or O(1)
Once we solve it we can improve efficiency. It's a second phase. Can be easier than first phase.
In that case threading, sorting ... are unimportant. Instead we need judicious use of trees, recursions, pattern recognition... and very clear thinking.
See [[EPI300]] and the green book by Zhou Xinfeng
