> And for all of this I still blunder my way through an exercise to write a function which returns a boolean in response to the question of whether sequence A is a sub-sequence of sequence B. I still draw a blank when asked what the magnitude of complexity is for the guests function I just wrote (damnit, of course calculating the permutations of a list is n-squared, but this is an interrogation of the random trivia I can manage to recall and I feel like a deer in the headlights).
That does, to me, sound like you do, in fact, have a problem with interviewing. The article is light on concrete facts to build off of, but if you're the kind of person who represent yourself to me (interviewing you) as having such an impressive toolbox as you certainly do seem to have in your possession, and then go on to fail to write a simple function and answer one of the most basic analytical (and, opposed to many other stupid gotchas/shibboleths, actually important) questions in computer science, then my "talker, not doer" red flag goes up, and you're going to have an uphill battle from there.
Basically, it's a case of over-promise and under-deliver.
Again, there is precious little concreteness to build off of, so this is very speculative: try to "modesty-fy" your CV and make sure you don't come off as bragging in any way in the beginning of the interview: under-promise. Also, do some whiteboard code katas. Then do the simple task, ask for help if you black out, and then put in the punch-line: "Actually, there's a really neat way to do this in Lisp".