A friend of mine didn't understand how he could have done better than me in a "write a quick sort" interview (we were still students) when I knew the algo and he never heard of it (and obviously struggled more).

Well, in one case (me), all the information the interviewer had was "this guy happens to know how to implement a quick sort by heart. K.".

In the other case (my friend), he got "this guy is able to understand and implement an algo he never saw before in a reasonable time", which is much more impressive

Errr in the set of numbers that complete the rationals wrt to standard metric? I guess you have to show it’s not rational so you probably did a proof of upper/lower converging bounds always having nonzero difference for 1/n increments or something? I would definitely not get this in a pressure interview situation.

Here's the proof from Baby Rudin:

> We now show that the equation (1) p^2=2 is not satisfied by any rational p. If there were such a p, we could write p=m/n where m and n are integers that are not both even. Let us assume this is done. Then (1) implies (2) m^2=2n^2. This shows m^2 is even. Hence m is even (if m were odd, m^2 would be odd), and so m^2 is divisible by 4. It follows that the right side of (2) is divisible by 4, so that n^2 is even, which implies that n is even. > The assumption that (1) holds leads to the conclusion that both m and n are even, contrary to our choice of m and n. Hence (1) is impossible for rational p.

From what I remember, it's simpler than that:

Assume sqrt(2) is rational and has the reduced form (x/y). Thus we are assuming that x and y are integers and that gcd(x,y) is 1. You square it and get x^2/y^2 which are somehow simultaneously coprime integers and also reducible to 2/1...

I think here they just meant, show that no rational number is the square root of 2. Not rational = not expressible as a ratio. You assume that sqrt(2) = p/q for some integers p and q, then derive a contradiction.