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.
Getting the feel of it
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 c, set a to the value from b, and then set b to the former value of a, now found in c.
Upping the ante
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 a getting bs old value.
Conclusion
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!
Cheers!
-Morten
Top comments (30)
What if summing a and b leads to a number that is larger than the maximum integer? This would cause an overflow.
I’d hate for an interview trick like this to lead to real world problems. This is the same issue that was present in every incorrect binary search function (see “implementation issues”).
Totally agree. Interview tricks should never find their way into production code. In fact, I think that's one of the worst problems in software development technical interviews today - the fact that the problems asked and the solutions expected are in no way applicable in real world situations.
Couldn't agree more, but because they do, and because we love Code Wars and similar code quiz sites, discussing these tricks are still needed, and for me at least, fun 😊
Yeah, it is fun.
That's why you usually use XOR for the swap trick :)
Yeah, but not in real code! I'd prefer it were readable over assigning one extra variable. You've got to find some specific conditions to make this the better code to use!
I actually used this in real code once, in an assembly inner loop where I was really running out of registers :), but you're right of course.
Related question: Did anyone here ever have to reverse a string? :D
Not in an interview, but in a quiz somewhere. It was an entry level one so only restriction was to not use the built in functions.
Cool way of doing that 🙂
I was immediately thinking about this in JavaScript specifically. You could also use array destructuring to get the same result:
Ruby, too! It's been possible at least since 1.8
Oh dear...
The task was to do this "without extra space" and not "don't use an extra variable". Both your solutions fail that. Constructing two arrays is definitely extra space used, you just won't see it in your code.
I don't know what Ruby does, but I can imagine, that this will create some variable 'behind the scene' or will also have to arrays constructed.
I am very sorry, but you both failed the test.
This is not very bad though. In real life you only need to know this kind of 'tricks' when you have very limited hardware like small chips in small devices such as smart lamps or smoke detectors. Also in most applications you probably won't need to switch the values of two variables.
As always, this is why it's important to understand what the language is doing before calling somebody wrong 🙂
Y'see, no variable in Ruby ever holds the object in question, but instead holds a reference to the object.
a, b = b, atells Ruby to place a reference to whatever is referenced bybat the time of invocation inside of the referencea, and whatever is referenced byaat the time of invocation inside of the referenceb. No array construction, no invisible intermediary variable, just happy-go-lucky references, reassigning themselves to the underlying addressed memory locations.Thx 4 the patronization tho! 💖💖😘
As I said, I am not sure what Ruby does and how this parallel assignment really works under the hood.
For the python example (and this was the main focus), my statement holds :-). It's a construction of an array (list), that is assigned to another list and afterwards deconstructed.
Good try, but no. "You both fail" is geared quite equally toward two intended audiences. Again, understand what the language is doing before you call someone wrong 😊
Why don't u use XOR operator?
a = a XOR b
b = a XOR b
a = a XOR b
Cool trick!
In js u can use ^ as xor
Swapping two objects, w/o a temp variable
Hmm… what if the variables are of other data types? Just making a guess tho, do people convert those data into bytes then perform the same math?
I wouldn't expect people to actually do this, it's more of a puzzle to see if you are able to think outide the box I think.
To be honest we were teached this in the first week of high school in our c++ class:)
Well, I guess it varies from country to country, and school to school, plus, a lot of us does not have a Bachelor or better in anything 😊 We still lovez us some codez tho! 😉
Yeah, i said it as a fun fact:)
If someone asked me this in an interview, I'd ask them for an example of where they used it in their production code.
Nice trick!
Thanks!
Python
a, b = b, a
Cool!
Seems to work perfectly fine 🤔