I think that your suggestion and my post can coëxist happily.

From the perspective of the interviewer, I would worry about the interviewee who asks me this question. Do the feel the need to ask permission every time they want to explore the problem space? How often will they have a concern, but wanting to not appear confrontational or difficult, they don't even ask for permission to raise the concern? This may be good for workplace harmony and short-term image maintenance, but it sucks as a long-term strategy for corporate success and personal fulfillment and advancement. I realize this is in a person's socialization, and habits they form from interactions with past management. I also realize that other potential future employers would view this entirely differently; this is a sign this person is capable of fitting into a corporate culture where people just do things. This is a warning sign that this candidate would not work out well in any culture I could see myself hiring people into.

It seems a better strategy to just behave for the corporate culture you would want to be hired into, and let the ones that dislike your approach kick you to the curb. You’d probably be unhappy there once you were hired on anyway.

I'd be doing the latter, so why should I have to behave differently during an interview?

If this is not what the interviewer wanted, they'd be better served by asking a slightly more fantastical question that would still show problem-solving skills. Also, the interviewer should qualify the question by saying that "this isn't a real world situation, I just want an algorithm". I don't know how someone would react to that situation.

It is.

Even more astonishing, at least to me, is that it is what some, maybe even a lot of, employees are looking for as well. Without an employer, or someone who they can submit to the authority of, to tell them what to work on when, they would be miserable and directionless. They crave structure, but need someone else to define it for them. They also become quite incensed when someone wants to remove that same structure because it gets in their way.

Some jobs allow or require a certain amount of this. Generally, it is jobs that are part of an established process, like manufacturing, that just needs someone to repetitively perform a particular step with reasonably consistently. This might be true of most jobs.

Other jobs do very poorly being treated as part of an established process. But people will select candidates for that anyway, because it works in the average case. The result of this is attempting to swaddle process around something inherently without process, just so the people involved can feel comfortable with the structure that guides their work. It does mean that productivity tends to suffer as a result of all of the process requirements, but many employers and employees consider it a worthwhile trade-off.

I get the sense that it's not that the line is fine, but that so many people toe it so tightly that, to someone who doesn't, it looks fine by comparison.