Really it was just write code to verify whether it can be done or not (return boolean) based on the N input (integer). Without having to write code it would return true for N >= 4, but I didn't know that. I was just trying to get an initial solution down with recursion, not thinking about backtracking yet or worst case time (which was probably 2^N).
I made another comment on this thread [1]. I wish instead of having to prep for interviews like this, I could just present a portfolio of clean code I made myself (non-proprietary of course) or my github. Unfortunately most of the grads they're hiring have no serious code to show for themselves.
For my Facebook interview for an internship, I was given a simple string manipulation problem which I solved quickly. Then I was given the N-Queens problem (a more generalized version of this one http://en.wikipedia.org/wiki/Eight_queens_puzzle). Needless to say I didn't solve that with my remaining time, since the interviews are only 45 minutes. I didn't feel it was a fair assessment of my skills.
Someone should just modify the StackSort algorithm that was posted yesterday (made up by xkcd) to search for Square Root functions instead and run them.