I too got this problem, though not at google. White-boarded it and came up with the n^2 solution.