Top Array Interview Questions and Answers

Question: How do you rotate an array?

Answer:

Rotating an array means shifting its elements in a circular manner, either to the left or to the right. There are different ways to perform this operation, and the exact method depends on whether you’re rotating to the left or the right.

Types of Rotation:

1. Left Rotation: All elements of the array are shifted to the left by a certain number of positions, and the elements that go past the start of the array are moved to the end.
2. Right Rotation: All elements of the array are shifted to the right by a certain number of positions, and the elements that go past the end of the array are moved to the front.

Approach for Rotation:

To rotate an array by d positions:

• Left Rotation: Move the first d elements to the end of the array, and shift the rest of the array forward.
• Right Rotation: Move the last d elements to the beginning of the array, and shift the rest of the array backward.

Key Observations:

• The array size is n.
• A left rotation by d is equivalent to a right rotation by n - d.
• If d >= n, you can take d % n because rotating more than n times will cycle back to the same position.

Efficient Solution (Using Reverse Approach):

The most efficient way to rotate an array in O(n) time complexity is using a reverse-based approach, where:

1. Reverse the entire array.
2. Reverse the first part (up to index d-1 for left rotation).
3. Reverse the second part (from index d to the end of the array).

Algorithm for Left Rotation by d:

1. Reverse the entire array.
2. Reverse the first d elements.
3. Reverse the remaining n-d elements.

Code Example (Left Rotation in Python):

def rotate_left(arr, d):
    n = len(arr)
    d = d % n  # Handle cases where d >= n
    
    # Helper function to reverse part of the array
    def reverse(arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1

    # Step 1: Reverse the entire array
    reverse(arr, 0, n - 1)

    # Step 2: Reverse the first d elements
    reverse(arr, 0, d - 1)

    # Step 3: Reverse the remaining n-d elements
    reverse(arr, d, n - 1)
    
    return arr

# Example usage:
arr = [1, 2, 3, 4, 5, 6, 7]
d = 3
rotated_array = rotate_left(arr, d)
print(rotated_array)  # Output: [4, 5, 6, 7, 1, 2, 3]

Algorithm for Right Rotation by d:

To rotate right, you can follow the same steps as left rotation, but instead reverse the last d elements and the first n-d elements.

Time Complexity:

• Time Complexity: O(n), where n is the number of elements in the array. The array is reversed three times, each of which takes O(n) time.
• Space Complexity: O(1) for the in-place operation (no extra space needed, except for variables).

Example:

For array [1, 2, 3, 4, 5, 6, 7] and d = 3:

• After left rotation by 3, the result will be: [4, 5, 6, 7, 1, 2, 3].
• After right rotation by 3, the result will be: [5, 6, 7, 1, 2, 3, 4].

Question: What is the difference between a 1D array and a 2D array?

Answer:

A 1D array (one-dimensional array) and a 2D array (two-dimensional array) are both linear data structures that store multiple elements, but they differ in the way they organize and access the data.

1. 1D Array (One-Dimensional Array):

• A 1D array is a simple, linear collection of elements. It can be thought of as a list of items arranged in a single row or a single line.
• Accessing elements: The elements are accessed by a single index. For example, arr[i] where i is the index.

Example:

arr = [1, 2, 3, 4, 5]  # 1D array with 5 elements

In the above example, arr[0] will give 1, arr[1] will give 2, and so on.

Characteristics:

• Structure: A 1D array has only one dimension (length).
• Shape: The array is a list of elements arranged linearly.
• Access Time: Access to an element in a 1D array is O(1), i.e., constant time.

2. 2D Array (Two-Dimensional Array):

• A 2D array is essentially an array of arrays. It can be thought of as a grid or matrix with rows and columns.
• Accessing elements: To access an element, you need two indices: one for the row and another for the column. For example, arr[i][j] where i is the row index and j is the column index.

Example:

arr = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]  # 2D array with 3 rows and 3 columns

In the above example:

• arr[0][0] gives 1
• arr[1][2] gives 6
• arr[2][1] gives 8

Characteristics:

• Structure: A 2D array is a collection of 1D arrays, arranged in rows and columns.
• Shape: The array has two dimensions: rows and columns.
• Access Time: Access to an element in a 2D array is also O(1), but you need two indices to specify the element’s position.

Key Differences:

Feature	1D Array	2D Array
Structure	Linear (single row)	Grid-like (rows and columns)
Number of Indices	1 index (single dimension)	2 indices (row and column)
Size Representation	Length (e.g., 5 elements)	Rows × Columns (e.g., 3x3 matrix)
Element Access	arr[i]	arr[i][j]
Use Cases	Simple collections of data	Matrices, tables, grids, images

Visual Representation:

1. 1D Array: A simple list:

   [1, 2, 3, 4, 5]

2. 2D Array: A matrix (rows and columns):

   [
     [1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]
   ]

Time Complexity:

• 1D Array: Accessing an element is O(1) because it requires only one index.
• 2D Array: Accessing an element is also O(1), but it requires two indices.

Conclusion:

• A 1D array is a simple, linear collection of elements, while a 2D array is a collection of arrays, organized in rows and columns (like a table or matrix).
• The 2D array provides more complexity and flexibility for representing data that has two dimensions (e.g., images, grids).

Read More

If you can’t get enough from this article, Aihirely has plenty more related information, such as Array interview questions, Array interview experiences, and details about various Array job positions. Click here to check it out.