Asking to work somewhere without demonstrating that you can do the work is asking a lot. Unfortunately, job history alone is not enough to weed out people that cannot program (let alone well.)
> they are very time-consuming for the company.
Not if you implement a simple test spec or scoring system. We're engineers!
> the point of asking graph-traversals and similar algorithms questions is not that they are the relevant job skill.
So don't ask the generic questions. Ask someone to implement something that they would need to do on the job. Obviously don't ask them to implement a feature that takes 12 hours, but a basic screen that is a snapshot of 45 minutes of on-the-job experience isn't crazy.
We also do a take-home exercise first to see how you think without us staring at you. Day-to-day at Seneca Systems we aren't staring at you, so it feels more relevant.