One thing that I always see in these threads is how these interviews are not really a good indicator. I work for a company that does these interviews, and most of us acknowledge that the interviews result in sizable false negatives, but the ones that do come through the process are usually very competent ones.

Also, complexity analysis/algorithm questions that are asked in the interview setting is not rocket science...