Interviewing problem

[Aange10]

I was reading a site (http://www.codinghorror.com/blog/2007/02/why-cant-programmers-program.html) and noticed one of the comments said to solve this problem :


Very very common, alas. I once interviewed a candidate for a VBA job (yes, you can stop booing for the peanut gallery) whom I asked to swap two variable contents without using a temp variable. It's the standard a=a+b, b=a-b, a=a-b problem.



I read the little formula, but, in pseudo code, how would you solve this?

[Beastinonyou]

Aange10 wrote:

It's the standard a=a+b, b=a-b, a=a-b problem.


I read the little formula, but, in pseudo code, how would you solve this?

That, and this formula will also work...

pseudo:

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

to test it, just substitute the values.

Example when A > B:

pseudo:

a = 34 b = 20 a = 20 - 34 = -14 b = 20 - (-14) = 34 a = -14 + 34 = 20 // End Result:  a = 20, b = 34

Example when A < B:

pseudo:

a = 15 b = 38 a =  38 - 15 = 23 b = 38 - 23 = 15 a = 23 + 15 = 38 // End Result:  a = 38, b = 15

[d310]

I actually would use bitwise XOR, in order to avoid arithmetic overflow.

code:

a = a XOR b b = a XOR b a = a XOR b

An example:

code:

a = 36 b = 20 a = a XOR b = 48 b = a XOR b = 36 a = a XOR b = 20

[Aange10]

I thought XOR meant if one but not both....


What does XOR do in this situation?

[d310]

Basic XOR rules:
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 0 = 0
What makes XOR useful in this case is that knowing two of the three values, one can easily determine the value of the third value.
Now let's through the previous example in binary:


a = 36 -> 100100
b = 20 -> 010100

100100
010100
---------
110000 -> a = 48



a = 48 -> 110000
b = 20 -> 010100

110000
010100
---------
100100 -> b = 36



a = 48 -> 110000
b = 36 -> 100100

110000
100100
---------
010100 -> a = 20

[Tony]

Keep in mind that this question is more about "are you interested enough in the field to read (and remember!) random interview trivia?"... as this is a well known trivia question, but not something you would ever want to write in a production system (I suppose with an exception of an embedded device where 4 bytes of memory matter).

[mirhagk]

@Tony, well actually for a linked list it perhaps could be important, if the list is big enough, and the memory is small enough.

[md]

mirhagk @ 2012-01-31, 9:22 am wrote:

@Tony, well actually for a linked list it perhaps could be important, if the list is big enough, and the memory is small enough.

Um... what? Please explain how swapping two integers is different then changing the order of two elements in a linked list in terms of memory...

I've never had a question like this in an interview, but if I did I'd definitely have to go with xor for my solution. It works on anything (doubles, complex numbers, structs!), where the addition/subtraction solutions would not.

[mirhagk]

well it uses the same concept. Instead of the previous and next element, each element stores just the xor of those two. If you come from the previous element and xor it with that value, you get the next, and vice versa

[RandomLetters]

I dont see why you would ever use XOR swap at all, since if the two variables actually point to the same item, you end up losing that information

a = a XOR b
b = a XOR b
a = a XOR b

but if a and b point to the same thing, it becomes

a = 1010
a = a XOR a = 1010 XOR 1010 = 0
a = a XOR a = 0
a = a XOR a = 0

[mirhagk]

what's 1010 XOR 0? It works just fine if they point to the same thing, the XOR'd value is 0, and XORing anything with 0 makes it itself.

[RandomLetters]

a = 1010
a = a XOR a = 1010 XOR 1010 = 0
a = a XOR a = 0 XOR 0 = 0
a = a XOR a = 0 XOR 0 = 0

[mirhagk]

a=b=1010

a = a XOR b = 1010 XOR 1010 = 0
b = a XOR b = 0 XOR 1010 = 1010
a = a XOR b = 0 XOR 1010 = 1010


there ya go.

[mirhagk]

Unless for some reason your using pointers and then dereferencing them and XORing the values rather than just XORing the pointers themselves.

[tedbean]