[Google Interview] Shuffle the Array

[toc]

Company Tags: Google, Adobe, Apple, Bloomberg, Microsoft

Problem Description

Given the array nums consisting of 2n elements in the form [x1, x2,…,xn, y1, y2,…, yn].

Return the array in the form [x1, y1, x2, y2,…, xn, yn].

Constraints:

1. 1 <= n <= 500
2. nums.length == 2n
3. 1 <= nums[i] <= 10^3

Examples

Let’s have a look at some examples to improve our understanding of this problem.

Now that you have a clear understanding of the problem, let’s dive into the various methods to solve it.

Video Solution:

Naïve Solution: Brute Force Method

Approach: In this method, we will use two nested loops where loop 1 is used to store the numbers in the second half of the array and loop 2 is used to bring back those numbers to the first half of the array.

Algorithm:

1. Initialize i, j, and k as 0, 1, and n respectively. 
2. For the initial half array (x), Initialize q as the value of k at the start of the loop.
3. In the next loop, rotate the number at (q – 1)’th position by moving it q positions towards left.
4. Decrement the q value and keep looping till the value of q becomes less than (i + j)
5. Decrement i, j, and k
6. Initialize an empty array and for number in the range of the length of the array, append the number
7. Return the array.

Solution:

def shuffle_array(a, n):
    i, j, k = 0, 1, n
    while(i < n):    
        q = k 
        while(q > (i + j)):
            a[q - 1], a[q] = a[q], a[q - 1]
            q = q - 1
        i = i + 1
        k = k + 1
        q = q + 1
    shuffled = []
    for no in range(0, len(a)):
        shuffled.append(a[no])
    return shuffled

Test Case Analysis: Let’s run this solution on the given test cases/examples to verify if the solution works.

As expected this approach has successfully passed all the test cases.

Complexity Analysis: Since you have to use two nested loops to solve this problem using this approach, the time complexity of this approach is O(n²), i.e. it has a quadratic time complexity.

Discussion: A quadratic time complexity isnt the best when it comes to arriving at solutions. The queston here is: “Is it necessary to use a nested loop to solve this problem?” The answer to this is NO! There’s always a better way and the next solution will help you to solve this question with a more efficient runtime complexity.

Divide and Rule [Efficient Solution]

Approach: In this approach the idea is to divide the given array/list into two parts. Store the initial half of the array in another list (let’s say x) and the latter part of the array in another list (let’s say y). Further, you will need the help of another empty array/list that will store the shuffeled output. Then, append the values from both the arrays x and y respectively to the shuffled array simultaneously to ensure that the elements at the same index of arrays x and y get populated within the resultant array one after the other at the same point of time. Once you have traversed through all the elements of both the arrays and populated the resultant array accordingly, you can return the shuffled array as an output.

The following diagram is a simple illustration of the above approach:

Solution:

def shuffle_array(nums, n):
    x = nums[:n]
    y = nums[n:]
    shuffled = []
    for i in range(n):
        shuffled.append(x[i])
        shuffled.append(y[i])
    return shuffled

Test Case Analysis:

Let’s run this solution on our examples:

Hurrah! The divide and conquer method works more often than not in questions like these and it worked here as well to yield us the correct output in every test case.

Complexity Analysis: In this case you have to traverse the given array only once whcih ensures that this solution has a linear time complexity, i.e. a time complexity of O(n).

Optimal Solution: Using Two Pointers

Approach: The idea here is to use couple of pointers i and j such that i will initially point at index zero while j will pont at the index which denotes exactly the half way mark of the given array. Now, with the help of these pointers keep populating the resultant array such that the element at every index and the element at its successive index will store the value pointed by i and i+j.

Let’s have a look at the following illustration to understand the approach that is being followed in this case.

Dry run of the above illustration:

Solution:

def shuffle_array(nums, n):
    i = 0
    j = n
    shuffled = []
    for i in range(i, j):
        shuffled.append(nums[i])
        shuffled.append(nums[i+j])
    return shuffled

Note: You can further simplify the above piece of code as shown below. The purpose of the above code is to help you visualize the concept of the approach being followed here. However you can further optimize it by eliminiting the pointers that have been initialized. This is because, the for loop itself helps you keep track of the pointer ‘i’ while ‘j’ is nothing but the value of ‘n’.

Further Optimization:

def shuffle_array(nums, n):
    shuffled = []
    for i in range(n):
        shuffled.append(nums[i])
        shuffled.append(nums[i+n])
    return shuffled

Test Case Analysis:

Complexity Analysis: With the help of the two pointers you only have traverse the given array which has a length of 2n halway as the pointers takes care of each half simultaneously in the same iterations. Thus, you have to undergo only n iterations which ensures that the time complexity of this method is linear, i.e., O(n).

Discussion: With the help of two pointers you can eliminate the requirement of creating separate arrays as done in the previous method. Hence, this approach qualifies to be the optimal solution when compared to the other solutions proposed here.

👉 Recommended Tutorial: How to Shuffle Two Arrays in Unison in Python?

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Recommended: Finxter Computer Science Academy

• One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
• So, do you want to master the art of web scraping using Python’s BeautifulSoup?
• If the answer is yes – this course will take you from beginner to expert in Web Scraping.