Apparently the correct answer is to use "Robert W. Floyd's tortoise and hare algorithm", which is trivial to explain and code.
The catch?
It took a decade of computer science research between the original statement of the problem and Floyd discovering the solution.
So... no worries, you have an hour, a marker, and a whiteboard. Your time starts: now.
"So we specifically asked for linear time."
"Uh, yeah, I did it in log(n). That's better."
"It doesn't match what's on this paper they gave me. Thanks for your time. We'll be in touch."
You’re expecting the mechanical engineer to recall something they learned about kinematics, not derive it on the spot. It’s a test of knowledge, rather than cleverness. The equations of motion are also more central to physics and engineering.
A decent programmer should know that linked lists exist, their general properties, pros and cons, etc. However, cycle detection is not a particularly common operation, so not knowing Floyd’s algorithm tells you very little—-and their failure to do years of research in 45 minutes even less.
The tortoise and hare algorithm is not the foundational skill required to make software work the way an understanding of motion is for building structures. That's why it's often omitted from educational material yet these people are able to produce usable software after even something like a bootcamp (which I guarantee basically no bootcamps ever touched this algorithm).
I'm not sure I approve of asking even more well known algorithms like Djikstra's algorithm or A* in a job interview, unless the role was something that specifically required that area of knowledge like building pathfinders for video games or robots or something.
Also, it took around 13.8 billion years for Newton to do what he did.
If they actually aren't looking for people who just cram CTCI or leetcode, coming to this answer from first principles is demonstrably far more difficult than you'd expect achieved in an interview.
These sort of questions have an incredible recency bias, and have zero relevance to engineering competence.
Of course; how else do you do back-door age discrimination?
No such avail. In fact, unless these algorithms and problem solving methodologies are baked into your memory there's no way you are white boarding a Leetcode hard level problem in an interview.
What I was impressed at an Uber interview was their system design interview process - which basically boiled down to 'how do I abstract retrying a 429 - rate limit exceeded.
What I take is that - the interviewer is expecting a very specific solution even in an open ended system design question. It's like throwing a needle in a haystack at you and expect you to get to the needle in like an hour :).
They're probably looking for some sort of variable refilling leaky bucket implementation, which is funny because I believe this is exactly what they do internally. It was probably the task the interview had in front of them in their day-to-day and wanted you to do it for them!
This is a fair design question for a senior role (which this sounds like) that promotes disccussion, but expecting a specific solution is really only testing "does this person match my preconceived ideal for what a <dev> is?" which is really dangerous and has very little value.
You could solve all these questions as long as you are good at problem solving, *given enough time*.
However, with tight time constraints and perfomance pressure, the only way you could solve all these questions is memorizing and practicing all these algorithms.