A geek with a hat » Google sent me a “what to know in on-site interviews” email. Here it is.: "You need to know Big-O complexity analysis really well → it’s OK to quickly come up with a brute force solution, but that’s never going to be the answer → always look for an O(n*logn) solution or ideally a linear one."