This is a great article. As someone who just interviewed 100 engineers for my startup, the lessons resonate with me, and can be generalised beyond PhDs:

Come up with any solution, no matter how bad or inefficient, and then improve it. That's better than trying to find an optimal solution and not being able to come up with any solution at all before you're out of time. Then, you've demonstrated an inability to solve the problem. To put it in black and white terms, you've failed. An inefficient solution is much better than no solution at all. And it may be good enough if the data set is small.

Also, if you give me an answer in 10 seconds, efficient or not, you will impress me as someone able to make rapid progress. You can then improve it, putting you in a better position than someone who ended up with the same final answer but took longer to give me any solution at all. Working code is critical.

Discussion is important. If you've chosen an array over an ArrayList, I want to know why, such as an ArrayList of a primitive type being inefficient, or that we know the size ahead of time. Conveying that you know what you're doing is more important than a specific choice. Because if you know what you're doing, I'm confident that you can handle a different problem that turns up if I hire you.