[itissid]

I always wonder if odd(and perhaps pointless) interview Q like this have been contorted from the original(much useful) problem like pollard's rho or it just happened to reduce to more useful ones.

Digging deeper into such questions yields fun observations which may be the only useful thing that comes from questions like these. Like the length of the Longest Increasing Subsequence of a sequence A, has a fun fact to do with the Chromatic Number of a graph derived formed from a matching between A and sorted(A).

Theoretical Math is beautiful and the answer to so many things.