interviewhelp.io

Grow into top tier organizations

Join us on Slack

Swap Items in an Array

☰ Table of Content

Swap Two Variables

In Python, swapping two variables is a one-liner: a, b = b, a.

In languages such as Java, swapping requires the use of a temporary variable:

1
2
3
temp = a;
a = b;
b = temp;

If we know the two variables are integers, can we swap them without using a temporary variable?

1
2
3
4
5
6
>>> a, b = 5, 20
>>> a ^= b
>>> b ^= a
>>> a ^= b
>>> a, b
(20, 5)

It’s a fun little exercise to convince yourself that the above procedure indeed works. Keep in mind that the XOR operator is commutative and that x ^ x = 1.

Another way is to use the plus and minus operators:

1
2
3
4
5
6
>>> a, b = 5, 20
>>> a = a + b
>>> b = a - b
>>> a = a - b
>>> a, b
(20, 5)

Note that the above two procedures only work when a and b are integers.

Swap Two Items in an Array

Given a list L and two indices i and j, we can swap the L[i] and L[j] in one-line: L[i], L[j] = L[j], L[i].

Shuffle an Array

Given an array, write a program to generate a random permutation of array elements.

The Fisher–Yates shuffle is a well-known algorithm to solve this problem. In pseudocode, the algorithm works as follows

for i from n−1 down to 1 do
     j ← random integer such that 0 ≤ j ≤ i
     swap a[j] and a[i]

Here’s the Python implementation:

1
2
3
4
5
6
import random

def shuffle_list(L):
    for i in range(len(L) - 1, 0, -1):
        j = random.randint(0, i)
        L[i], L[j] = L[j], L[i]

Note that random.randint(a, b) returns a random integer n such that a <= n <= b.

Let’s see the function in action:

1
2
3
4
5
6
7
>>> L = list(range(10))
>>> shuffle_list(L); L
[4, 8, 3, 0, 7, 6, 5, 9, 2, 1]
>>> shuffle_list(L); L
[3, 5, 6, 0, 7, 8, 4, 2, 1, 9]
>>> shuffle_list(L); L
[0, 7, 8, 4, 1, 2, 5, 3, 9, 6]

Exercises

Update: 2021-10-19