I feel like they don't realize that this is the goal they're calibrating these questions toward, though. If they did, they wouldn't require the "from memory" component—instead, they'd break the question into two parts:
1. tell me what algorithm you would use to solve this problem; or, failing that, tell me what criteria you'd use to select the best algorithm for solving this problem out of a set of candidate algorithms.
2. Here's a journal paper, explaining a particular data structure + set of algorithms that can† be used to solve the problem we're talking about. All the algorithms in the journal paper are in that sort of declarative, math-proof-phrased pseudo-pseudo-code form. Now take this journal paper and turn it into an implementation in your language of choice. Explain your thinking as you go.
† The paper chosen is not the one corresponding to the algorithm the candidate chose; nor is it the one corresponding to the algorithm that's "right" to pick for solving the problem. It is, in fact, randomly-chosen from the pool of sub-optimal solutions to the problem, filtered for the ones that get rarely used in practice and so have no easy non-journal-paper presentations of a reference impl laying about on the web to study. Alternately—if the interviewer has enough time to explain a second problem—it could even be a paper randomly-chosen from the pool of all algorithms papers!
Benefits:
• Both task 1 and task 2 are things "senior" engineers do every day in the real world.
• There's no component of memorization; the step "between" step 1 and step 2, where you'd look up the journal paper corresponding to the algorithm you thought of, is dropped.
• You can't really "burn" either task.