As jerf has pointed out, this is Impostor Syndrome. It is present in men as well. Ironically, the better programmer I've become, the stronger it has gotten. The thing is, while scary, it's perfectly normal. The only advise I can offer is just to ignore it. So what if it is true and you "don't belong" or you're a bad programmer: so what? It's still something that you enjoy and can make a career, a rare luxury for most…
So what would you recommend someone self-taught who just bombed his past couple of interviews do? Nothing like failing on elementary math questions to make you feel like a class A idiot, especially if your title is 'Senior Software Engineer', and here I go, bombing on freaking word problems in a numeracy test. I feel like a total fraud, like I'm in the wrong field, I could have done those easily straight out of high…
For brain teaser type problems, I like Martin Gardner books.