Here we are again, discussing the secrets of every technical interview for programmers.

This time I will share the most common question in an interview session wherein most programmers fail to answer.

Again, this kind of question is used to test the analytical skills of a candidate to make sure that he is qualified for the job.

Problem

PROBLEM 3: Swap the values of two variables without using a third variable.

Analysis

I'll be using a Ruby script for this one, just for the simple reason that I'm currently working for a project with this language. Well, ruby is almost the same as C based programming language anyway, so I guess there would be no issue with it.

So for our problem, usually a developer would approach this by giving another variable that will serve as a temporary variable, something similar to this:

a=2
b=3
temp=0

temp = a
a = b
b = temp

puts "a is " + a.to_s
puts "b is " + b.to_s

Unfortunately, we are not allowed (as given) to use another variable.

To solve it, there is actually three basic ways to approach this: two of it is by using Arithmetic Operations while the other one is by using Bitwise Operation.

Arithmetic Operation - Add and Subtract Method

a=2
b=3

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

# just to display the value
puts "a is " + a.to_s
puts "b is " + b.to_s

What we have done is we simply store the sum of two variables in the first one (a) while preserving the value of the other (b). Then we subtract the preserved value (b) to the sum (which is now on a) and assign it to the second variable (b). With that, we already changed the value of the second variable (b should now be equal to the original value of a) to the first one.

Doing the same approach, we can get the value of the other variable and thus making them swap their values.

Arithmetic Operation - Multiply and Divide Method

a=2
b=3

a = a*b
b = a/b
a = a/b

# just to display the value
puts "a is " + a.to_s
puts "b is " + b.to_s

The flow of logic is just the same as the add and subtract method. The only difference is that we are using different operators.

Bitwise Operation - Using Bitwise XOR

a=2
b=3

# ^ is the bitwise XOR for Ruby
a = a^b
b = a^b
a = a^b

# just to display the value
puts "a is " + a.to_s
puts "b is " + b.to_s

A Bitwise Exclusive OR (XOR) is used to perform logical XOR operation to two set of bit patterns. An XOR operation will result to 1 if two bits are different while get 0 if not.

Though we have used bitwise XOR, the flow of logic goes the same way with the arithmetic approach.

Which of these methods is most advisable?

The arithmetic approach, though correct, has a limitation. When we deal with two big numbers chances are the result will cause an overflow since we have limits for integers. Therefore, it is more advisable to use the bitwise operation rather than the arithmetic to avoid overflow.

UPDATE: Correction on the code, for the second approach (arithmetic via multiplication and division) would actually throw an error if the value of b is 0 (thanks ColinWright for pointing this out)

2 comments :

  1. My first time encountering this question. Really simple but yet tricky!! :)

    ReplyDelete
  2. Christian winther5/30/12, 3:07 PM

    a, b = b, a

    ReplyDelete