I am not sure I chose a suitable title for the question, so please feel free to edit as you see fit.
I've done several interviews with some major software companies around the world, in North America and in Europe. However, due to the fact that my degree is not in Computer Science or Software Engineering, I am often asked a question whose premise is that I am not qualified for the job.
For example: an interviewer once asked me: "Your level of knowledge is somewhere here" (puts hand around waist-line) "while a computer science graduate's level of knowledge is here" (lifts other hand high above his head). "How are you going to close this gap?".
I was taken aback by the question, given that it was the final round of interviews, and I explained that I disagree with the premise of the question, given that I've made it past the first few rounds, where other computer science graduates haven't. In any case, I didn't get the job.
Now, a few years (of experience) later at a different company, I'm in a similar situation, where the interviewer indicated that "Self taught programmers are not familiar with concepts such as recursion and Big-Oh", which is certainly understandable, but not true in my case. For that particular instance, I simply offered to explain those concepts, and did so successfully (as indicated by an offer for a second round).
Needless to say, this issue seems like it is going to follow me for the foreseeable future. So, my question is: what is the best way, during an interview, to tackle those questions? How do I reassure an interviewer who assumes that I am unqualified, due to having an apparently incompatible degree, that I am fit for the job? Is there anything I should indicate on or point out?
Clarification
I have a Masters degree in Engineering, just not Computer Science or Software Engineering