Todays post will be a short one, but one that covers a really simple algorithm that still might stump you in an interview setting if you don't have a background in math, or if you haven't been doing code puzzles on your spare time.
Let's start with the easier version, just to get a feel for the task.
Write an algorithm that swaps two numbers.
Ok, that is easy enough. In pseudocode:
// The numbers a = 1 b = 2 // Let's swap c = a // c == 1 a = b // a == 2 b = c // b == 1 // result a == 2 b == 1
Ok, we just store the value of
a in temporary storage
a to the value from
b, and then set
b to the former value of
a, now found in
Let's remove the
c from the algorithm, not allowing temporary storage...
Write an algorithm that swaps two numbers, without using extra storage.
Wow, that one is a bit trickier. We can't use any more storage, but we need to swap the numbers. Luckily this involves numbers, and we can leverage math to help us.
// The numbers a = 1 b = 2 // lets swap a = a + b // 1 + 2 = 3 => a == 3, b == 2 b = a - b // 3 - 2 = 1 => a == 3, b == 1 a = a - b // 3 - 1 = 2 => a == 2, b == 1
Ok, we first set
a to be the sum of both numbers. Then we set
b to be the result of subtracting it from the sum, making it be the former value of
a. Lastly we set
a to be the result of subtracting the former value of
a, now stored in
b, from the sum, still stored in
a. This results in
bs old value.
Until I learned this trick the hard way myself in a coding quiz, I was baffled by this question, simply because I have been "trained" to think too much about variables, code, loops and other constructs, and too little in the math-department. This made me attempt to find clever ways of solving it using code, rather than the much simpler math.
I hope you can get some value from this little tip, saving you from the feeling of inadequacy that I felt. Getting stuck on quizzes like this, that are truly simple to solve, but that we tend to overcomplicate, really does not help us manage the impostor syndrome that most of us experience at times.
Good luck with your interviews!