Computer Science Canada

Interviewing problem

Author:	Aange10 [ Mon Jan 30, 2012 8:18 pm ]
Post subject:	Interviewing problem
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?

Author:

Beastinonyou [ Mon Jan 30, 2012 8:52 pm ]

Post subject:

Re: Interviewing problem

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

Author:

d310 [ Mon Jan 30, 2012 11:16 pm ]

Post subject:

Re: Interviewing problem

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

Author:	Aange10 [ Mon Jan 30, 2012 11:26 pm ]
Post subject:	RE:Interviewing problem
I thought XOR meant if one but not both.... What does XOR do in this situation?

Author:	d310 [ Mon Jan 30, 2012 11:46 pm ]
Post subject:	Re: Interviewing problem
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

Author:	Tony [ Tue Jan 31, 2012 12:12 am ]
Post subject:	RE:Interviewing problem
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).

Author:	mirhagk [ Tue Jan 31, 2012 9:22 am ]
Post subject:	RE:Interviewing problem
@Tony, well actually for a linked list it perhaps could be important, if the list is big enough, and the memory is small enough.

Author:	md [ Tue Jan 31, 2012 9:59 am ]
Post subject:	Re: RE:Interviewing problem
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.

Author:	mirhagk [ Tue Jan 31, 2012 10:34 am ]
Post subject:	RE:Interviewing problem
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

Author:	RandomLetters [ Tue Jan 31, 2012 10:56 am ]
Post subject:	RE:Interviewing problem
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

Author:	mirhagk [ Tue Jan 31, 2012 11:02 am ]
Post subject:	RE:Interviewing problem
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.

Author:	RandomLetters [ Tue Jan 31, 2012 11:05 am ]
Post subject:	RE:Interviewing problem
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

Author:	mirhagk [ Tue Jan 31, 2012 12:44 pm ]
Post subject:	RE:Interviewing problem
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.

Author:	mirhagk [ Tue Jan 31, 2012 12:51 pm ]
Post subject:	RE:Interviewing problem
Unless for some reason your using pointers and then dereferencing them and XORing the values rather than just XORing the pointers themselves.

Author:	RandomLetters [ Tue Jan 31, 2012 7:03 pm ]
Post subject:	RE:Interviewing problem
I'm working with theory here, not practice! Hey, it is possible!

Author:	mirhagk [ Tue Jan 31, 2012 7:41 pm ]
Post subject:	RE:Interviewing problem
Well theory doesn't ignore logic.

Author:	RandomLetters [ Tue Jan 31, 2012 9:49 pm ]
Post subject:	RE:Interviewing problem
How does it ignore logic? If two variables are stored at the same location, XOR swap or arithmetic swap will destroy its information.

Author:	md [ Tue Jan 31, 2012 10:31 pm ]
Post subject:	Re: RE:Interviewing problem
RandomLetters @ 2012-01-31, 9:49 pm wrote: How does it ignore logic? If two variables are stored at the same location, XOR swap or arithmetic swap will destroy its information. I think it's safe to assume that if you're resorting to using xor to swap two values you're going to also be using it somewhere where you're not swapping the values of two pointers which point to the same location. I mean, if you really need the space savings of not using a temporary variable you're likely not using dynamically allocated memory or even C. And once you're dealing with assembly the problem tends to go away (registers are your friend).

Author:	mirhagk [ Wed Feb 01, 2012 8:39 am ]
Post subject:	RE:Interviewing problem
No I mean that even if you use pointers, you'd XOR the pointers themselves, not what they are pointing to. The only way it'd happen is if you dereferenced the pointers, and XOR'd the values. That is what ignores logic, as you introduce problems, and lose the ability to swap large objects, and for absolutely no gain.

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy