Interview Question #1: In-Place Shuffle

Problem:

We will write a function that shuffles the list in-place. What shuffle means is that the list will be re-arranged randomly while each index will have the same possibility of containing an element.

---

Process:

What we have to keep in mind:
1. Each index should have the same possibility of getting a particular element.
2. The shuffle will happen in-place. The advantage of in-place functions is that they use less space compared to other functions. Therefore, it is not recommended to allocate extra memory.

---

Solution:

Attempt #1: Iterate through each element and swap them randomly

• Time Complexity: O(n)
• Space Complexity: O(1)

How it works:
While we are iterating through each index(current index) of the list,
1. Get a random number in the range of the length of the list. This will be our target index which its value will be swapped with the value of current index.
2. Swap the value of current index with the value of target index.

Logic behind this decision:
Let's try to vaildate that our function grants equal possibility of having a value at each index.

Assume that we are discussing an input list of [1,2,3,4,5] , n=5.

For the 1st index,
Random number will be generated from the range of [0,4], so if we were to have 1 in our 1st index, the possibility would be $1 \over n$.

For the 2nd index,
if we were to have 1 in our 2nd index, the 1st index should not have 1 in it which is $(n-1) \over n$. Also, we will be choosing 1 from n-1 for our 2nd index which is $1 \over n-1$.
The possibility would be $(n-1) \over n$ * $1 \over n-1$ = $1 \over n$.
Therefore, there are same possibility for 1 to be in the 1st index and to be in the 2nd index.

The same calculation happens for all the rest of the index, so all the index should have $1 \over n$ possibility of having a particular value in it.

def get_random(floor, ceiling):
    return random.randrange(floor, ceiling + 1)

def shuffle(the_list):

    last_index_in_the_list = len(the_list)-1
    
    for i in range(len(the_list)-1):
        swap_index = get_random(i, last_index_in_the_list)
        if swap_index != i:
            the_list[i], the_list[swap_index] = \
            the_list[swap_index], the_list[i]
    pass

Time Complexity Analysis

1. Iteration through the list - O(n)
   We are iterating through the list once. That is O(n).

2. Getting random number from the range - O(1)
   Random number is created using random.randrange
   According to the source code,

• randrange uses randbelow
• randbelow uses getrandbits
• getrandbits uses urandom
• os.urandom generates random string with the input size byte. Although I was not able to find the specific runtime of os.urandom but it seems reasonable to assume that the runtime for the function is O(1).
  Therefore, we will assume that the runtime for random.randrange is O(1).

As a conclusion, the runtime of this code can be represented as O(n).

Limitations
1. As a common disadvantage of all in-place functions, the function is destructive. It destroys the original input which makes us lose the original information permanently.