And let's not forget, there are plenty of CS graduates who conversely aren't very good at programming.
Now, once you can code your way out of a paper bag, then the question is do you have the CSCI fundamentals to apply the best known solutions to difficult problems. Facebook has their pick of the litter, so it makes sense that they might spend more time validating CSCI knowledge, but for most companies that are hiring this would be a very poor metric to go by.
It's surprisingly easy to google for solutions once you know what you're looking for instead of searching descriptively :)
Technically, a homeless person could dig in at a terminal in the library and teach themselves anything they needed to learn about computers. However, first they'd need to know what to look for and by God that was difficult before I spent 4 years talking to people who worked with computers all day. I think my time on Reddit actually enriched me there a bit, too.
I propose a new interview question: How would you code your way out of a paper bag? You will be given several constants, such as the strength of the paper bag, difficulty of tearing, etc, and will be expected to write your own Tear() function and call it properly.
The best part is that when the recruiters/headhunters ask why you rejected a candidate, you can honestly say "he couldn't code his way out of a wet paper bag."
Everything I know about theoretical computer science I picked up from books, at a price far below the tuition of a typical university.
Anyway, college was a boost, yes, but my main point was that one doesn't need a CS degree (and, honestly, there aren't many CS degrees out there anymore -- just Java-programming degrees masquerading as CS) to be able to do this stuff. Any sort of good liberal-arts background, even one not involving an actual piece of sheepskin from a four-year institution, should be all anyone needs to pick up CS or just about any other subject.
But the merits of a real liberal-arts education are a whole 'nother thread.
The candidate looked confused and replied, "What's an operating system?"
The candidate was a 2nd-year CS major at a college in Silicon Valley.
Needless to say, we hired another candidate--the 16-year-old kid who built Linux boxes at home for fun. :)
Whether you're an expert or not is irrelevant. Its that statistically you're probably more likely to be humble about what you don't know, so that way you can go and hunt down the solution if you need to when those problem situations occur.
Incidentally that's why CS undergrads "waste" their time learning all the sorts, not 'cos you'll ever need to write one from scratch ever, it's just a good way to introduce ideas about time and space complexity.