[bearmf]

> 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.

If you can't solve this really fast it means you haven't practiced enough for the interviews.

> of course calculating the permutations of a list is n-

> squared

If I understand you correctly, it is actually n!, because there are n! permutations of n objects.

Basically, your problem seems to be lack of preparation. You study a lot but you haven't studied things that are asked in the interviews well enough.

I would recommend "Cracking the Coding Interview" book. Of course you need to actually solve problems from it. There is lots of valuable advice there. Courses on algorithms on Coursera are also pretty good.

[virgi1]

This. I can't believe nobody else pointed out that it's not n-squared. (but, lots of people pointed out that complexity is really about reasoning not about memorisation - and you have to be good at reasoning in order to be a good programmer).

And this is not an "esoteric question" - you should really have a good grasp on complexity in order to understand the limitations of your system, and when you can use certain algorithms/data structures, and when you can't.

See this write-up: http://www.infoarena.ro/blog/numbers-everyone-should-know - but don't memorize the numbers, that would be pointless - the idea is to get a feel of why complexity is important. (you'll notice for instance that between O(n!) and O(n^2) there is a 2-3 orders of magnitude difference in the acceptable input data size... so your confusion between factorial and n-squared is actually quite big)