Top Array Interview Questions and Answers（2025）

Question: What is the time complexity of array insertion and deletion?

Answer:

The time complexity of insertion and deletion operations in an array depends on the location where the operation is performed (beginning, middle, or end of the array) and the underlying data structure. Let’s break this down:

1. Insertion in an Array:

• Insertion at the End (Appending):

  • Time Complexity: O(1) (constant time)

  • Inserting an element at the end of an array (assuming there is space available) is typically O(1) because we can directly insert the element at the next available index.

  • Example (Appending in Python):

    arr = [1, 2, 3]
    arr.append(4)  # O(1)

• Insertion at the Beginning or Middle:

  • Time Complexity: O(n) (linear time)

  • Inserting an element at the beginning or in the middle of an array requires shifting all subsequent elements one position to the right to make space for the new element. Since the number of shifts is proportional to the number of elements after the insertion point, the time complexity is O(n).

  • Example (Insertion at the Beginning in Python):

    arr = [1, 2, 3]
    arr.insert(0, 0)  # O(n)

  • Example (Insertion in the Middle in Python):

    arr = [1, 2, 3]
    arr.insert(1, 5)  # O(n) - Inserting at index 1, shift elements to the right

2. Deletion in an Array:

• Deletion at the End:

  • Time Complexity: O(1) (constant time)

  • Deleting an element from the end of the array is O(1), as it simply involves removing the last element (no shifting is required).

  • Example (Deleting from the End in Python):

    arr = [1, 2, 3]
    arr.pop()  # O(1)

• Deletion at the Beginning or Middle:

  • Time Complexity: O(n) (linear time)

  • Deleting an element from the beginning or middle of an array requires shifting all subsequent elements one position to the left to fill the gap left by the deleted element. This results in O(n) time complexity, where n is the number of elements after the deletion point.

  • Example (Deletion from the Beginning in Python):

    arr = [1, 2, 3]
    arr.pop(0)  # O(n) - Deleting the first element, shift elements to the left

  • Example (Deletion from the Middle in Python):

    arr = [1, 2, 3]
    del arr[1]  # O(n) - Deleting element at index 1, shift elements to the left

Summary of Time Complexity for Insertion and Deletion in Arrays:

Operation	Best Case (End)	Worst Case (Beginning or Middle)
Insertion	O(1)	O(n)
Deletion	O(1)	O(n)

Space Complexity:

• Space Complexity: O(1) for insertion and deletion (since only a few variables are used during the operations).

Conclusion:

• Insertion at the end of the array and deletion from the end are O(1) operations.
• Insertion at the beginning or in the middle and deletion from the beginning or in the middle are O(n) operations because elements need to be shifted.
• The performance of insertion and deletion is highly affected by the position of the operation in the array.

Question: How do you find the intersection of two arrays?

Answer:

The intersection of two arrays consists of the elements that appear in both arrays. To find the intersection efficiently, there are several approaches you can take, depending on the use case and the data structure of the arrays.

1. Using Hashing (Set-Based Approach):

The most efficient way to find the intersection of two arrays is to use a set (or hash set). This method takes advantage of the fact that sets provide O(1) average-time complexity for lookup operations.

Steps:

1. Convert one of the arrays into a set.
2. Iterate through the second array and check if each element exists in the set.
3. If it does, add it to the result.

Example in Python:

def intersection(arr1, arr2):
    set1 = set(arr1)  # Convert arr1 to a set
    result = [elem for elem in arr2 if elem in set1]  # Check if each element in arr2 is in set1
    return result

# Example usage:
arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
print(intersection(arr1, arr2))  # Output: [2, 2]

Example in JavaScript:

function intersection(arr1, arr2) {
    const set1 = new Set(arr1);  // Convert arr1 to a set
    return arr2.filter(item => set1.has(item));  // Check if each element in arr2 is in set1
}

// Example usage:
let arr1 = [1, 2, 2, 1];
let arr2 = [2, 2];
console.log(intersection(arr1, arr2));  // Output: [2, 2]

Time Complexity:

• Time Complexity: O(n + m), where n is the length of arr1 and m is the length of arr2.
  • O(n) for converting arr1 to a set.
  • O(m) for iterating through arr2 and checking membership in the set.
• Space Complexity: O(n) for storing arr1 in a set.

2. Sorting and Two Pointer Approach:

If you don’t want to use additional space, you can sort both arrays and then use a two-pointer approach to find the intersection. This method works well when the arrays are relatively small or when additional space is a concern.

Steps:

1. Sort both arrays.
2. Use two pointers, one for each array, and compare elements at the current pointer positions.
3. If the elements match, add it to the result and move both pointers forward.
4. If the element in the first array is smaller, move the first pointer forward.
5. If the element in the second array is smaller, move the second pointer forward.

Example in Python:

def intersection(arr1, arr2):
    arr1.sort()
    arr2.sort()
    i, j = 0, 0
    result = []
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] == arr2[j]:
            result.append(arr1[i])
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
            
    return result

# Example usage:
arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
print(intersection(arr1, arr2))  # Output: [2, 2]

Example in JavaScript:

function intersection(arr1, arr2) {
    arr1.sort((a, b) => a - b);  // Sort arr1
    arr2.sort((a, b) => a - b);  // Sort arr2
    
    let i = 0, j = 0;
    let result = [];
    
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] === arr2[j]) {
            result.push(arr1[i]);
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
}

// Example usage:
let arr1 = [1, 2, 2, 1];
let arr2 = [2, 2];
console.log(intersection(arr1, arr2));  // Output: [2, 2]

Time Complexity:

• Time Complexity: O(n log n + m log m), where n is the length of arr1 and m is the length of arr2, due to the sorting step. The two-pointer traversal is O(n + m).
• Space Complexity: O(1), if we exclude the space used by the input arrays (as the result array is the only extra space required).

3. Brute Force Approach:

A brute force method involves comparing each element of the first array with every element of the second array. This approach has poor time complexity but is easy to implement.

Example in Python:

def intersection(arr1, arr2):
    result = []
    for elem in arr1:
        if elem in arr2 and elem not in result:  # Check if element is in both arrays and not already in result
            result.append(elem)
    return result

# Example usage:
arr1 = [1, 2, 2, 1]
arr2 = [2, 2]
print(intersection(arr1, arr2))  # Output: [2]

Example in JavaScript:

function intersection(arr1, arr2) {
    let result = [];
    for (let i = 0; i < arr1.length; i++) {
        if (arr2.includes(arr1[i]) && !result.includes(arr1[i])) {
            result.push(arr1[i]);
        }
    }
    return result;
}

// Example usage:
let arr1 = [1, 2, 2, 1];
let arr2 = [2, 2];
console.log(intersection(arr1, arr2));  // Output: [2]

Time Complexity:

• Time Complexity: O(n * m), where n is the length of arr1 and m is the length of arr2. This is because for each element in arr1, we are checking if it exists in arr2, which takes O(m) time.
• Space Complexity: O(n), to store the result array.

Summary of Methods:

Method	Time Complexity	Space Complexity	Maintains Order
Hashing (Set-based)	O(n + m)	O(n)	No
Sorting and Two Pointers	O(n log n + m log m)	O(1)	No
Brute Force	O(n * m)	O(n)	Yes

Conclusion:

• The most efficient approach is using hashing (set-based) with O(n + m) time complexity and O(n) space complexity.
• If space is a concern, the sorting and two-pointer approach is an alternative with O(n log n + m log m) time complexity and O(1) space complexity.
• The brute force method is simple but inefficient, especially for large arrays, with a time complexity of O(n * m).

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.