I have a CS degree, I focused quite a bit on distributed systems. I also deal with it day to day. But if you asked me what the CAP theorem is, I'd have to look it up. Same for bubble sort. If we first establish how it works I can figure out the complexity, but why memorize stuff I can look up on wikipedia if I need it?
"CAP theorem" is a pretentious name for the idea that in the event of network partition you have to give up availability or consistency. Or both ;)
And yes, I too keep forgetting this name but I could talk about the issue if they explained what real problem they have.
As for bubble sort, I'd just write
for (i=1; i<n; i++)
for (j=i; j>0; j--)
if (X[j-1] > X[j])
swap(j-1,j);
and see if they notice that it actually is insertion sort, my personal favorite O(n²) algo. If they still want to reject me then well, I probably don't want to know them anyway.
And insertion sort actually is better. It can be made to work online, keeping all elements seen so far sorted before receiving the next element. And I think it ought to be more cache friendly than bubble sort.
