Tuesday, April 12, 2016

Swap without temporary space

There is a really bad technical interview question which appears now and then.
It goes like this: “how would you exchange the value of two variables without
using temporary space?” Whenever I hear about this question I cringe. It is one of those questions that does not measure anything other than: have you seen this before? or did you read Hacker's Delight?, which, by the way, I wholeheartedly recommend. And you may be a fine developer and human being and be just unlucky enough to not have seen this trick before.

It gets better, because the question is voided in some programming languages with tuple literals or multiple assignment. For example in go, the solution is trivial,

a, b = b, a

And you are done with it. Even better, the compiler may generate a swap of registers, which is as efficient as it gets.

In any case, I was chatting about this question with a friend and I remembered some  ideas I thought I had read somewhere, maybe in Hacker's Delight, maybe
somewhere else. After checking, apparently, I hadn't read it in any of them, so maybe I have come up with them myself. In any case, the gist of it is, if you are ever asked this question, you can use matrices to go completely overboard with the answer.

So, say you want to swap two variables and you want to do it without temporary storage. One of the classic ways to do this is,

a = a + b
b = a - b
a = a - b

So how can we describe this in terms of matrices?
Well, each of the assignments is actually the multiplication of the vector
$\begin{bmatrix}a\\ b\end{bmatrix}$ by a matrix and as long as the matrix determinant is not zero, you
don't lose any information.

For example, the first assignment may be written in math,

$a' = a + b$
$b' = 0 + b$

or in matrix form:
$$\begin{bmatrix}a'\\ b'\end{bmatrix} = \begin{bmatrix}1 & 1\\0 & 1\end{bmatrix}\begin{bmatrix}a\\ b\end{bmatrix}$$

So, the three matrices describing the previous assignments are,

$$M = \begin{bmatrix}1 & 1\\0 & 1\end{bmatrix}$$
$$N = \begin{bmatrix}1 & 0\\1 & -1\end{bmatrix}$$
$$R = \begin{bmatrix}1 & -1\\0 & 1\end{bmatrix}$$
The multiplication of these matrices (be careful, the order has to be right)
$$RNM = \begin{bmatrix}1 & -1\\0 & 1\end{bmatrix}\begin{bmatrix}1 & 0\\1 & -1\end{bmatrix}\begin{bmatrix}1 & 1\\0 & 1\end{bmatrix} = \begin{bmatrix}0 & 1\\1 & 0\end{bmatrix}$$

which is a reverse identity i.e. a swap.

This already works (even if it overflows). In all truth any N factors of the
reverse identity do the trick. You may even rescale them, for example, multiply the first by 2 and the second by 1/2, if you are in floating point, for more obscurity. Or use reciprocals for integers (another trick from Hacker's Delight).

We can go even further and work in $GF2$, i.e. binary bit by bit operations.
In this space, the addition is the xor (^) and each number is its own inverse,
so the above equation can be written,

a = a ^ b
b = a ^ b
a = a ^ b

You can also write this code in terms of factors of the reverse identity with binary matrices.

The three assignments with the xor is probably what the (now completely stunned) interviewer was aiming for.

No comments:

Post a Comment