I interview for my company, too, and don't ask these kinds of algorithm questions because the reality is these problems aren't typical of day-to-day work for the positions we are hiring for.
I'm interested to know what your interview process is. If you wouldn't mind sharing, how does the interview process work at your company?
We have the candidate sit at a workstation and write a functioning program to solve a relatively realistic but self-contained problem using the language of their choice. It usually involves extracting and working with some data from a few big CSV files -- we have pretty legitimate datasets set aside just for the interview. There really aren't any restrictions during this: the candidate can use any resources they would normally use, including Google or Stack Overflow.
We don't have the interviewer watch everything they're doing over their shoulder. They're allowed to just work on the problem on their own.
>>You mention diff(1), but who's to say the author(s) of that tool would've necessarily solved this problem on the spot?
I think this is the gist of the all problems facing the current interview process.
There is a big difference between inventing a solution to a problem, and learning the solution to a problem which some one invented.
The latter shows nothing about the ability or even the way in which a person thinks or even works. It just shows the person was able to scale multiplication table memorization skills to other things as they grew up.
I have a degree in pure mathematics from a highly ranked institution. I published research as an undergraduate. I went to multiple REUs. I participated in the Putnam and similar competitions. I read CLRS in 9th grade and didn't even bother taking an algorithms course in college. But even I find that these sorts of questions are more gatekeeping than anything else. That's not a perspective that I had when I was coming straight out of college.
The revelation for me came from working at a successful company that manages to hire great developers and build great teams without needing to ask these sorts of questions. It turns out that these sorts of problems are relatively rare in real software development work, and many developers who wouldn't necessarily ace them in 40 minutes under tightly controlled conditions can nevertheless come up with perfect solutions in a normal work context, should the problem actually arise.
The reality is this sort of question selects for personality just as much as it does programming ability. It selects for the sort of person who likes puzzles and brainteasers and spends a lot of time immersing themselves in that culture. It reinforces a lot of cultural stereotypes deeply embedded in the programming world.
There's also a lot of perspective to be gained by working outside of a major technology hub. If developers are rarer to come by, if you're in any sort of hiring position you realize just how careless it would be for you to throw away a candidate because they didn't ace this sort of question. It'd sort of be like a family without much food throwing out all their bread because they saw a fly land on it. Relying 100% on this sort of question reflects an overabundance of applicants more than it does any underlying universal quality in the interviewing strategy.
Beyond this, I think there's a little irony in your comment. You mention diff(1), but who's to say the author(s) of that tool would've necessarily solved this problem on the spot? You're actually making that assumption, which I find to be unjustified. There's an entire class of thinker and problem solver you're ignoring -- the deep thinkers, the great ponderers who soak their mind so thoroughly in a problem that they come out with something wonderful. But you might need to give them some space and a day or two.