If I give you a description of what a BFS is, you as a programmer should be able to write one. A BFS is rather trivial. You shouldn't have to know how to write it, you should be able to figure it out. The same goes for implementing a linked list or the FizzBuzz problem.
As a programmer, you need to make up algorithms on the spot to solve business problems. You don't know the solution beforehand, you figure it out, that's your job. It's the key skill that basically separates you from a typist.
> There are more productive ways to interview someone; for example take a bug in your product and see if the candidate can fix it.
This is a different skill. It's an important skill, but finding errors in an existing structure and fixing it is different from being able to create that structure in the first place.