I'd fear that you may be missing the point of such questions. While the question may be asking for an algorithm at the end, there can be some discussion and communication that is what is really being tested here. How well are the requirements defined? Is error handling covered properly? Which complexity is more important of space or time?
Often with these there isn't just one correct solution. There are numerous good solutions and I'd be surprised if more than 1% could give an answer that couldn't be changed in some way over the following 6 months if someone put up a $1,000,000 to find some improvement or enhancement to the allegedly optimal solution. The question is how well can you explain why your solution is good, what are its shortcomings and strengths. How maintainable, scalable, flexible, customizable, and other -ables is it?
In a phone interview situation, I'd likely check that I do have the correct understanding and start to look for anything missing or vague in the description that I'd want to get more specific in terms of modeling and visualizing the model. From there I would likely think of a few different strategies and compare them out loud so that it is clear I do know how to analyze and pick a good solution then explain what I'd do to get that up and running. Course that is all hypothetical and in reality I'd probably be close to that most of the time as that is the kind of script I'd want to use though it may have various detours as there may be a joke to give in there or some piece of trivia that may help demonstrate competence to some degree.