You can't solve these equations (at least in the general case, maybe there's some clever way in this specific case I'm not getting), because the ring of 64-bit integers is not a factorial ring, meaning not every multiplication can be undone. That is, if xy = z, there might be multiple y's for a given x and z. (Edit--previously I had said it's because it's not a field, but that's a stronger condition than we need.) If the sum is 2 and the sum of squares is 0, then (1, -1) and (2^63 + 1, 2^63 - 1) are both solutions.
You could do this solution using the field of bitfields modulo a 64-bit irreducible polynomial, but I expect that's over the heads of most interviewers :P
(edit: just realized that you can do the neccesary field multiplication and addition very quickly in constant time and space. It's even linear in the number of bits you have to process. This looks very close to an ideal solution, so I posted a link on the blog. There may be a clever solution that is better.)
(edit #2: the clever solution is just to use bigints. The sum of squares is guaranteed to fit in 192 bits. This might be what the parent poster meant all along. This works because integers are a factorial ring, so the equations are guaranteed to have a unique solution.)
Simpler to do the arithmetic modulo a prime just smaller than 2^64 if you ignore the case where n is very close to 2^64 (which should be fine in real life). In case you leave your code will be easier to maintain than if you bring Galois Fields into it.
It seems like you'd be IO bound when scanning the array so using larger than machine precision integers shouldn't slow things down. Particularly since you know the number of bits you'll need beforehand.
Since you didn't put SPOILER ALERT, I guess it's okay to say that I was going for a similar approach, except that I was going to use sum of elements and the XOR of all elements. I guess the only advantage is that computing the XOR should be faster/smaller space than summing squares.
Your solution won't work because you can't solve for a and b if you are given (a xor b) and (a - b), consider an extra 3 and missing 2 will give 1 for both values, as will extra 5 and missing 4.
I gave a similar solution in the blog comments, but instead of sum of squares I used the product of the numbers. We used to give similar puzzles to candidates on job interviews.
You could do this solution using the field of bitfields modulo a 64-bit irreducible polynomial, but I expect that's over the heads of most interviewers :P
(edit: just realized that you can do the neccesary field multiplication and addition very quickly in constant time and space. It's even linear in the number of bits you have to process. This looks very close to an ideal solution, so I posted a link on the blog. There may be a clever solution that is better.)
(edit #2: the clever solution is just to use bigints. The sum of squares is guaranteed to fit in 192 bits. This might be what the parent poster meant all along. This works because integers are a factorial ring, so the equations are guaranteed to have a unique solution.)